joint work with Achim Blumensath, Thomas Colcombet, Denis Kuperberg and Michael Vanden Boom

Speaker(s)

Paweł Parys

Affiliation

Uniwersytet Warszawski

Date

Dec. 18, 2013, 2:15 p.m.

Room

room 5870

Title in Polish

Two-Way Cost Automata and Cost Logics over Infinite Trees

Seminar

Seminar Automata Theory

---

This work is a step towards solving regular cost functions on infinite trees (which is already done for words - finite and infinite - and for finite words).

We consider cost functions over infinite trees defined by an extension of weak monadic second-order logic with a new fixed-point-like operator. We show this logic to be decidable, improving previously known decidability results for cost logics over infinite trees. The proof relies on an equivalence with a form of automata with counters called quasi-weak cost automata, as well as results about converting two-way alternating cost automata to one-way alternating cost automata.

---