Decision problems of finite automata design and related arithmetics

Author:
Calvin C. Elgot

Journal:
Trans. Amer. Math. Soc. **98** (1961), 21-51

MSC:
Primary 02.80

Erratum:
Trans. Amer. Math. Soc. **103** (1962), 558-559.

MathSciNet review:
0139530

Full-text PDF Free Access

References | Similar Articles | Additional Information

**[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. MR**0129523****[4]**Calvin C. Elgot and Jesse B. Wright,*Quantifier elimination in a problem of logical design*, Michigan Math. J.**6**(1959), 65–69. MR**0104534****[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. MR**0077478****[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. MR**0078059****[8]**Hilary Putnam,*Decidability and essential undecidability*, J. Symb. Logic**22**(1957), 39–54. MR**0089154****[9]**M. O. Rabin and D. Scott,*Finite automata and their decision problems*, IBM J. Res. Develop.**3**(1959), 114–125. MR**0103795****[10]**Raphael M. Robinson,*Restricted set-theoretical definitions in arithmetic*, Proc. Amer. Math. Soc.**9**(1958), 238–242. MR**0093479**, 10.1090/S0002-9939-1958-0093479-4

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
02.80

Retrieve articles in all journals with MSC: 02.80

Additional Information

DOI:
http://dx.doi.org/10.1090/S0002-9947-1961-0139530-9

Article copyright:
© Copyright 1961
American Mathematical Society