Decision problems of finite automata design and related arithmetics

Decision problems of finite automata design and related arithmetics
HTML articles powered by AMS MathViewer

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

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

PDF | Request permission

References

The non-existence of certain algorithms of finite automata theory

Application of recursive arithmetic in the theory of computers and automata

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 129523, DOI 10.1145/320924.320931
Calvin C. Elgot and Jesse B. Wright, Quantifier elimination in a problem of logical design, Michigan Math. J. 6 (1959), 65–69. MR 104534
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

On a class of events representable in a finite automaton

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
Hilary Putnam, Decidability and essential undecidability, J. Symbolic Logic 22 (1957), 39–54. MR 89154, DOI 10.2307/2964057
M. O. Rabin and D. Scott, Finite automata and their decision problems, IBM J. Res. Develop. 3 (1959), 114–125. MR 103795, DOI 10.1147/rd.32.0114
Raphael M. Robinson, Restricted set-theoretical definitions in arithmetic, Proc. Amer. Math. Soc. 9 (1958), 238–242. MR 93479, DOI 10.1090/S0002-9939-1958-0093479-4