×

Theory of \(\omega\)-languages. I: Characterizations of \(\omega\)-context- free languages. (English) Zbl 0363.68113


MSC:

68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Buchi, J.R., On a decision method in restricted second order arithmetic, () · Zbl 0215.32401
[2] Buchi, J.R., Dcision methods in the theory of ordinals, Bull. amer. math. soc., 71, 767-770, (1965) · Zbl 0207.30904
[3] Buchi, J.R.; Landweber, L.H., Definability in the monadic second order theory of successor, J. symbolic logic, 34, 166-170, (1969) · Zbl 0209.02203
[4] Choueka, Y., Finite automata on infinite structures, ()
[5] Choueka, Y., Theories of automata on ω-tapes: A simplified approach, J. comput. system sci., 8, 117-141, (1974) · Zbl 0292.02033
[6] Cohen, R.S.; Gold, A.Y., Theory of ω-languages. II: A study of various models of ω-type generation and recognition, Comput. system sci., 15, 185-208, (1977) · Zbl 0363.68114
[7] Cohen, R.S.; Gold, A.Y., Complexity of ω-computations on deterministic pushdown machines, () · Zbl 0382.03025
[8] Cohen, R.S.; Gold, A.Y., Ω-computations on Turing machines, () · Zbl 0368.68057
[9] Cohen, R.S.; Gold, A.Y., “the ω-Kleene closure of families of languages” abstract 74T-C47, Notices amer. math. soc., 21, 7, (1974)
[10] Elgot, C.C.; Rabin, M.O., Decidability and undecidability of extensions of second (first) order theory of (generalized) successor, J. symbolic logic, 31, 169-181, (1966) · Zbl 0144.24501
[11] Eilenberg, S., ()
[12] Fischer, P.C.; Meyer, A.R.; Rosenberg, A.L., Time restricted sequence generation, J. comput. system sci., 4, 50-73, (1970) · Zbl 0191.18301
[13] Ginsburg, S., ()
[14] Hopcroft, E.J.; Ullman, J.D., ()
[15] Hartmanis, J.; Stearns, R.E., Sets of numbers defined by finite automata, Amer. math. monthly, 74, 539-542, (1967) · Zbl 0149.01002
[16] Hartmanis, J.; Stearns, R.E., On the computational complexity of algorithms, Trans. amer. math. soc., 117, 275-306, (1965) · Zbl 0131.15404
[17] Hosseley, R., Finite tree automata and ω-automata, ()
[18] Landweber, L.H., Decision problems for ω-automata, Math. systems theory, 3, 376-384, (1969) · Zbl 0182.02402
[19] McNaughton, R., Testing and generating infinite sequences by a finite automaton, Inform. contr., 9, 521-530, (1966) · Zbl 0212.33902
[20] Muller, D.E., Infinite sequences and finite machines, (), 3-16
[21] Trakhtenbrot, B.A.; Barzdin, Y.M., ()
[22] Rabin, M.O., Decidability of second-order theories and automata on infinite trees, Trans. amer. math. soc., 141, 1-35, (1969) · Zbl 0221.02031
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.