Two-Way Cost Automata and Cost Logics over Infinite Trees

Prelegent(ci)

Paweł Parys

Afiliacja

Uniwersytet Warszawski

Termin

18 grudnia 2013 14:15

Pokój

p. 5870

Tytuł w języku angielskim

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

Seminarium

Seminarium „Teoria automatów”

---

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.

---