Generalized finite automata theory with an application to a decision problem of second-order logic. (English) Zbl 0157.02201

Full Text: DOI


[1] G. Birkhoff, On the structure of abstract algebras.Proc. Cambridge Phil. Soc. 31 (1938), 433–454. · JFM 61.1026.07 · doi:10.1017/S0305004100013463
[2] G. Birkhoff,Lattice Theory, Amer. Math. Soc. Colloq. Publ., Vol. 25, New York, 1948.
[3] J. R. Büchi andC. C. Elgot, Decision problems of weak second-order arithmetics and finite automata. Abstract 553-112,Notices Amer. Math. Soc. 5 (1958), 834.
[4] J. R. Büchi, ”Weak second-order arithmetic and finite automata”. University of Michigan, Logic of Computers Group Technical Report, September 1959;Z. Math. Logik Grundlagen Math. 6 (1960), 66–92. · Zbl 0103.24705 · doi:10.1002/malq.19600060105
[5] J. R. Büchi andJ. B. Wright, ”Mathematical Theory of Automata”. Notes on material presented by J. R. Büchi and J. B. Wright, Communication Sciences 403, Fall 1960, The University of Michigan. · Zbl 0092.00302
[6] J. R. Büchi, Mathematische Theorie des Verhaltens endlicher Automaten.Z. Angewandte Math. und Mech. 42 (1962), 9–16. · Zbl 0113.01401 · doi:10.1002/zamm.19620420104
[7] I. M. Copi, C. C. Elgot andJ. B. Wright, Realization of events by logical nets.J. Assoc. Comp. Mach. 5 (1958) 181–196. (Also in Moore [13].) · Zbl 0088.01901
[8] J. E. Doner, Decidability of the weak second-order theory of two successors. Abstract 65T-468,Notices Amer. Math. Soc. 12 (1965), 819; erratum,ibid. 13 (1966), 513.
[9] C. C. Elgot, ”Decision problems of finite automaton design and related arithmetics”. University of Michigan, Department of Mathematics and Logic of Computers Group Technical Report, June 1959;Trans. Amer. Math. Soc. 98 (1961), 21–51. · doi:10.1090/S0002-9947-1961-0139530-9
[10] S. Feferman andR. L. Vaught, The first-order properties of products of algebraic systems.Fund. Math. 47 (1959), 57–103. · Zbl 0088.24803
[11] S. C. Kleene, Representation of events in nerve nets and finite automata.Automata Studies pp. 3–42, Annals of Math. Studies, No. 34, Princeton University Press, Princeton, N. J., 1956.
[12] I. T. Medvedev, On a class of events representable in a finite automaton. Supplement to the Russian translation ofAutomata Studies (C. Shannon and J. McCarthy, eds.), published by the Publishing Agency for Foreign Literature, Moscow, 1956. Translated by Jacques J. Schorr-Kon for Lincoln Laboratory Report 34-73, June 1958. (Also in Moore [13].)
[13] E. F. Moore,Sequential Machines, Selected Papers. Addison-Wesley, Reading, Mass., 1964. · Zbl 0147.24107
[14] M. O. Rabin andDana Scott, Finite automata and their decision problems.IBM J. Res. Develop. 3 (1959), 114–125. (Also in Moore [13].) · doi:10.1147/rd.32.0114
[15] R. W. Ritchie, Classes of predictably computable functions.Trans. Amer. Math. Soc. 106 (1963), 139–173. · Zbl 0107.01001 · doi:10.1090/S0002-9947-1963-0158822-2
[16] Raphael M. Robinson, Restricted set-theoretic definitions in arithmetic.Proc. Amer. Math. Soc. 9 (1958), 238–242. · Zbl 0112.00702 · doi:10.1090/S0002-9939-1958-0093479-4
[17] J. W. Thatcher, ”Notes on Mathematical Automata Theory”. University of Michigan Technical Note, December, 1963.
[18] J. W. Thatcher, ”Decision Problems and Definability for Generalized Arithmetic”. Doctoral Dissertation, The University of Michigan; IBM Research Report RC 1316, November, 1964.
[19] J. W. Thatcher andJ. B. Wright, Generalized finite automata. Abstract 65T-469,Notices Amer. Math. Soc. 12 (1965), 820.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.