On the Accepting Power of 2-Tape Büchi Automata
| dc.creator | Finkel, Olivier | |
| dc.date | 2007-12-02 | |
| dc.date.accessioned | 2026-07-07T08:46:48Z | |
| dc.date.available | 2026-07-07T08:46:48Z | |
| dc.description | We show that, from a topological point of view, 2-tape Büchi automata have the same accepting power than Turing machines equipped with a Büchi acceptance condition. In particular, we show that for every non null recursive ordinal alpha, there exist some Sigma^0_alpha-complete and some Pi^0_alpha-complete infinitary rational relations accepted by 2-tape Büchi automata. This very surprising result gives answers to questions of W. Thomas [Automata and Quantifier Hierarchies, in: Formal Properties of Finite automata and Applications, Ramatuelle, 1988, LNCS 386, Springer, 1989, p.104-119], of P. Simonnet [Automates et Théorie Descriptive, Ph. D. Thesis, Université Paris 7, March 1992], and of H. Lescow and W. Thomas [Logical Specifications of Infinite Computations, In: "A Decade of Concurrency", LNCS 803, Springer, 1994, p. 583-621]. | |
| dc.identifier | https://arxiv.org/abs/0712.0165 | |
| dc.identifier | http://arxiv.org/abs/0712.0165 | |
| dc.identifier | 23rd International Symposium on Theoretical Aspects of Computer Science, STACS 2006, France (2006) | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/143375 | |
| dc.subject | Computational Complexity | |
| dc.subject | Logic in Computer Science | |
| dc.subject | Logic | |
| dc.title | On the Accepting Power of 2-Tape Büchi Automata | |
| dc.type | text |