×

zbMATH — the first resource for mathematics

Decision problems of finite automata design and related arithmetics. (English) Zbl 0111.01102
Trans. Am. Math. Soc. 98, 21-51 (1961); Errata 103, 558-559 (1962).

MSC:
03-XX Mathematical logic and foundations
68Qxx Theory of computing
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] J. R. Büchi, C. C. Elgot and J. B. Wright, The non-existence of certain algorithms of finite automata theory (Abstract), Notices Amer. Math. Soc. vol. 5 (1958) p. 98.
[2] A. Church, Application of recursive arithmetic in the theory of computers and automata, Lecture Notes, Summer Conference, University of Michigan, June, 1958.
[3] Irving M. Copi, Calvin C. Elgot, and Jesse B. Wright, Realization of events by logical nets, J. Assoc. Comput. Mach. 5 (1958), 181 – 196. · Zbl 0088.01901 · doi:10.1145/320924.320931 · doi.org
[4] Calvin C. Elgot and Jesse B. Wright, Quantifier elimination in a problem of logical design, Michigan Math. J. 6 (1959), 65 – 69. · Zbl 0085.34001
[5] S. C. Kleene, Representation of events in nerve nets and finite automata, Automata studies, Annals of mathematics studies, no. 34, Princeton University Press, Princeton, N. J., 1956, pp. 3 – 41.
[6] I. T. Medvedev, On a class of events representable in a finite automaton (translated from the Russian by J. Schorr-Kon), M.I.T. Lincoln Lab. Group Report, June 30, 1958, pp. 34-73.
[7] Edward F. Moore, Gedanken-experiments on sequential machines, Automata studies, Annals of mathematics studies, no. 34, Princeton University Press, Princeton, N. J., 1956, pp. 129 – 153.
[8] Hilary Putnam, Decidability and essential undecidability, J. Symb. Logic 22 (1957), 39 – 54. · Zbl 0078.24501
[9] M. O. Rabin and D. Scott, Finite automata and their decision problems, IBM J. Res. Develop. 3 (1959), 114 – 125. · Zbl 0158.25404 · doi:10.1147/rd.32.0114 · doi.org
[10] Raphael M. Robinson, Restricted set-theoretical definitions in arithmetic, Proc. Amer. Math. Soc. 9 (1958), 238 – 242. · Zbl 0112.00702
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.