×

zbMATH — the first resource for mathematics

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

MSC:
68Q70 Algebraic theory of languages and automata
Software:
ALGOL 60
PDF BibTeX XML Cite
Full Text: DOI
References:
[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, () · Zbl 0215.32401
[3] {\scJ.R.Buchi}, Transfinite automata recursions and weak second-order theory of ordinals “Logic, Methology and Philosophy of Science”, Proc. 1964 Int. Congress, North-Holland Amsterdam. · Zbl 0207.31001
[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)
[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., ()
[14] Ginsburg, S., ()
[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 {\scJ. 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., ()
[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.