Tree acceptors and some of their applications. (English) Zbl 0212.02901


68Q70 Algebraic theory of languages and automata


Full Text: DOI


[1] Buchi, J. R., Weak second-order arithmetic and finite automata, Z. Math. Logik Grundlagen Math., 6, 66-92 (1960) · Zbl 0103.24705
[2] Buchi, J. R., On a decision method in restricted second-order arithmetic, (Logic, Methodology, and Philosophy of Science. Logic, Methodology, and Philosophy of Science, Proc. 1960 Int. Congress, Stanford University Press, Stanford, Calif. (1962)) · Zbl 0215.32401
[4] Buchi, J. R., Decision methods in the theory of ordinals, Bull. Amer. Math. Soc., 71, 767-770 (1965) · Zbl 0207.30904
[5] Buchi, J. R.; Elgot, C. C., Decision problems of weak second-order arithmetic and finite automata, Abstract No. 553-112, Notices Amer. Math. Soc., 5, 834 (1958)
[6] Chomsky, N.; Miller, G. A., Finite state languages, Information and Control, 1, 91-112 (1958) · Zbl 0081.14503
[7] Doner, J. E., Decidability of the weak second-order theory of two successors, Abstract No. 65T-468, Notices Amer. Math. Soc., 12, 819 (1965)
[8] Doner, J. E., Decidability of locally free algebras with unary operations, Abstract No. 66T-384, Notices Amer. Math. Soc., 13, 634-635 (1966)
[9] Ehrenfeucht, A., An application of games to the completeness problem for formalized theories, Fund. Math., 49, 129-141 (1960-1961) · Zbl 0096.24303
[10] Elgot, C. C., Decision problems of finite automata design and related arithmetics, Trans. Amer. Math. Soc., 98, 21-51 (1961) · Zbl 0111.01102
[11] Eršov, Ju. L., Decidability of certain non elementary theories (in Russian), Algebra i Logika Sem., 3, No. 2, 45-47 (1965)
[12] Feferman, S.; Vaught, R. L., The first-order properties of algebraic systems, Fund. Math., 47, 57-103 (1959) · Zbl 0088.24803
[13] Ginsburg, S., (An Introduction to Mathematical Machine Theory (1962), Addison-Wesley: Addison-Wesley Reading, Mass.) · Zbl 0102.33804
[14] Ginsburg, S., (The Mathematical Theory of Context-Free Languages (1966), McGraw-Hill: McGraw-Hill New York) · Zbl 0184.28401
[15] Ginsburg, S.; Rice, H. G., Two families of languages related to ALGOL, J. Assoc. Comput. Mach., 9, 350-371 (1962) · Zbl 0196.01803
[16] Ginsburg, S.; Rose, G. F., Operations which preserve definability in languages, J. Assoc. Comput. Mach., 10, 175-195 (1963) · Zbl 0192.07201
[17] Mal’cev, A. I., Axiomatizable classes of locally free algebras of certain types (in Russian), Sibirsk. Mat. ., 3, 729-743 (1962)
[18] Medvedev, I. T., On a Class of Events Representable in a Finite Automaton, M.I.T. Lincoln Laboratory Report 34-73 (June 30, 1958), (translated from the Russian by J. Schorr-Kon)
[19] Mezei, J.; Wright, J. B., Generalized ALGOL-Like Languages, IBM Research Paper RC-1528 (December 20, 1965)
[20] Myhill, J., Finite Automata and the Representation of Events, Wright Air Development Command Technical Report 57-624, 112-137 (1957)
[21] Rabin, M. O.; Scott, D., Finite automata and their decision problems, IBM J. Res. Develop., 3, 114-125 (1959) · Zbl 0158.25404
[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
[23] Robinson, R. M., Restricted set theoretic definitions in arithmetic, Proc. Amer. Math. Soc., 9, 238-242 (1958) · Zbl 0112.00702
[24] Tarski, A., Some decision problems for locally free commutative algebras, Abstract No. 66T-383, Notices Amer. Math. Soc., 13, 634 (1966)
[25] Tarski, A.; Mostowski, A.; Robinson, R. M., (Undecidable Theories (1953), North Holland: North Holland Amsterdam) · Zbl 0053.00401
[26] Thatcher, J. W., A further generalization of finite automata and an application to a decision problem, Abstract No. 67T-385, Notices Amer. Math. Soc., 14, 534 (1967)
[27] Thatcher, J. W.; Wright, J. B., Generalized finite automata, Abstract No. 65T-649, Notices Amer. Math. Soc., 12, 820 (1965)
[28] Thatcher, J. W.; Wright, J. B., Generalized finite Automata with an Application to a Decision Problem of Second-Order Logic, IBM Research Report RC-1713 (November 16, 1966)
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.