You are not logged in |
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
- 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.
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.
