Theories of automata on \(\omega\)-tapes: a simplified approach. (English) Zbl 0292.02033


03D05 Automata and formal grammars in connection with logical questions
68Q45 Formal languages and automata
Full Text: DOI


[1] Büchi, J.R., Weak second-order arithmetic and finite automata, Z. math. log. grundl. math., 6, 66-92, (1960) · Zbl 0103.24705
[2] Büchi, J.R., On a decision method in restricted second-order arithmetic, () · Zbl 0215.32401
[3] Büchi, J.R., Decision methods in the theory of ordinals, Bull. amer. math. soc., 71, 767-770, (1965) · Zbl 0207.30904
[4] Choueka, Y., Finite automata on infinite structures, ()
[5] Elgot, C.C., Decision problems of finite automata design and related arithmetics, Trans. amer. math. soc., 98, 21-51, (1961) · Zbl 0111.01102
[6] McNaughton, R., Testing and generating infinite sequences by a finite automaton, Information and control, 9, 521-530, (1966) · Zbl 0212.33902
[7] McNaughton, R.; Yamada, H., Regular expressions and state graphs for automata, Trans. IEEE, 9, 39-47, (1960) · Zbl 0156.25501
[8] Muller, D.E., Infinite sequences and finite machines, switching circuit theory and logical design, ()
[9] Rabin, M.; Scott, D., Finite automata and their decision problems, IBM J. research develop, 3, 114-125, (1959) · Zbl 0158.25404
[10] Rabin, M., Decidability of second-order theories and automata on infinite trees, Trans. amer. math. soc., 141, 1-35, (1969) · Zbl 0221.02031
[11] Rabin, M., Automata on infinite objects and Church’s problem, () · Zbl 0315.02037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.