Weak cost automata over infinite trees
<p>Cost automata are traditional finite state automata enriched with a finite set of counters that can be manipulated on each transition. Based on the evolution of counter values, a cost automaton defines a function from the set of structures under consideration to the natural numbers extended...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
2012
|
| Subjects: |
| _version_ | 1797055460295049216 |
|---|---|
| author | Vanden Boom, M |
| author2 | Ong, C |
| author_facet | Ong, C Vanden Boom, M |
| author_sort | Vanden Boom, M |
| collection | OXFORD |
| description | <p>Cost automata are traditional finite state automata enriched with a finite set of counters that can be manipulated on each transition. Based on the evolution of counter values, a cost automaton defines a function from the set of structures under consideration to the natural numbers extended with infinity, modulo a boundedness relation that ignores exact values but preserves boundedness properties.</p><p>Historically, variants of cost automata have been used to solve problems in language theory such as the star height problem. They also have a rich theory in their own right as part of the theory of regular cost functions, which was introduced by Colcombet as an extension to the theory of regular languages. It subsumes the classical theory since a language can be associated with the function that maps every structure in the language to 0 and everything else to infinity; it is a strict extension since cost functions can count some behaviour within the input.</p><p>Regular cost functions have been previously studied over finite words and trees. This thesis extends the theory to infinite trees, where classical parity automata are enriched with a finite set of counters. Weak cost automata, which have priorities {0,1} or {1,2} and an additional restriction on the structure of the transition function, are shown to be equivalent to a weak cost monadic logic. A new notion of quasi-weak cost automata is also studied and shown to arise naturally in this cost setting. Moreover, a decision procedure is given to determine whether or not functions definable using weak or quasi-weak cost automata are equivalent up to the boundedness relation, which also proves the decidability of the weak cost monadic logic over infinite trees.</p><p>The semantics of these cost automata over infinite trees are defined in terms of cost-parity games which are two-player infinite games where one player seeks to minimize the counter values and satisfy the parity condition, and the other player seeks to maximize the counter values or sabotage the parity condition. The main contributions and key technical results involve proving that certain cost-parity games admit positional or finite-memory strategies.</p><p>These results also help settle the decidability of some special cases of long-standing open problems in the classical theory. In particular, it is shown that it is decidable whether a regular language of infinite trees is recognizable using a nondeterministic co-Büchi automaton. Likewise, given a Büchi or co-Büchi automaton as input, it is decidable whether or not there is a weak automaton recognizing the same language.</p> |
| first_indexed | 2024-03-06T19:11:03Z |
| format | Thesis |
| id | oxford-uuid:16c6de98-545f-4d2d-acda-efc040049452 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T19:11:03Z |
| publishDate | 2012 |
| record_format | dspace |
| spelling | oxford-uuid:16c6de98-545f-4d2d-acda-efc0400494522022-03-26T10:33:17ZWeak cost automata over infinite treesThesishttp://purl.org/coar/resource_type/c_db06uuid:16c6de98-545f-4d2d-acda-efc040049452Computer science (mathematics)EnglishOxford University Research Archive - Valet2012Vanden Boom, MOng, C<p>Cost automata are traditional finite state automata enriched with a finite set of counters that can be manipulated on each transition. Based on the evolution of counter values, a cost automaton defines a function from the set of structures under consideration to the natural numbers extended with infinity, modulo a boundedness relation that ignores exact values but preserves boundedness properties.</p><p>Historically, variants of cost automata have been used to solve problems in language theory such as the star height problem. They also have a rich theory in their own right as part of the theory of regular cost functions, which was introduced by Colcombet as an extension to the theory of regular languages. It subsumes the classical theory since a language can be associated with the function that maps every structure in the language to 0 and everything else to infinity; it is a strict extension since cost functions can count some behaviour within the input.</p><p>Regular cost functions have been previously studied over finite words and trees. This thesis extends the theory to infinite trees, where classical parity automata are enriched with a finite set of counters. Weak cost automata, which have priorities {0,1} or {1,2} and an additional restriction on the structure of the transition function, are shown to be equivalent to a weak cost monadic logic. A new notion of quasi-weak cost automata is also studied and shown to arise naturally in this cost setting. Moreover, a decision procedure is given to determine whether or not functions definable using weak or quasi-weak cost automata are equivalent up to the boundedness relation, which also proves the decidability of the weak cost monadic logic over infinite trees.</p><p>The semantics of these cost automata over infinite trees are defined in terms of cost-parity games which are two-player infinite games where one player seeks to minimize the counter values and satisfy the parity condition, and the other player seeks to maximize the counter values or sabotage the parity condition. The main contributions and key technical results involve proving that certain cost-parity games admit positional or finite-memory strategies.</p><p>These results also help settle the decidability of some special cases of long-standing open problems in the classical theory. In particular, it is shown that it is decidable whether a regular language of infinite trees is recognizable using a nondeterministic co-Büchi automaton. Likewise, given a Büchi or co-Büchi automaton as input, it is decidable whether or not there is a weak automaton recognizing the same language.</p> |
| spellingShingle | Computer science (mathematics) Vanden Boom, M Weak cost automata over infinite trees |
| title | Weak cost automata over infinite trees |
| title_full | Weak cost automata over infinite trees |
| title_fullStr | Weak cost automata over infinite trees |
| title_full_unstemmed | Weak cost automata over infinite trees |
| title_short | Weak cost automata over infinite trees |
| title_sort | weak cost automata over infinite trees |
| topic | Computer science (mathematics) |
| work_keys_str_mv | AT vandenboomm weakcostautomataoverinfinitetrees |