Nie jesteś zalogowany |
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
- 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.
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.
