Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 

 

Decidability of second-order theories and automata on infinite trees.


Author: Michael O. Rabin
Journal: Trans. Amer. Math. Soc. 141 (1969), 1-35
MSC: Primary 02.32
MathSciNet review: 0246760
Full-text PDF Free Access

References | Similar Articles | Additional Information

References [Enhancements On Off] (What's this?)

  • [1] J. Richard Büchi, On a decision method in restricted second order arithmetic, Logic, Methodology and Philosophy of Science (Proc. 1960 Internat. Congr .), Stanford Univ. Press, Stanford, Calif., 1962, pp. 1–11. MR 0183636
  • [2] J. Richard Büchi, Decision methods in the theory of ordinals, Bull. Amer. Math. Soc. 71 (1965), 767–770. MR 0189997, 10.1090/S0002-9904-1965-11384-2
  • [3] J. E. Doner, Decidability of the weak second-order theory of two successors, Notices Amer. Math. Soc. 12 (1965), 819.
  • [4] A. Ehrenfeucht, Decidability of the theory of one function, Notices Amer. Math. Soc. 6 (1959), 268.
  • [5] -, Decidability of the theory of one linear ordering relation, Notices Amer. Math. Soc. 6 (1959), 268-269.
  • [6] Yu. L. Ershov, Decidability of the theory of relatively complemented distributive lattices and the theory of filters, Algebra i. Logika Sem. 3 (1964), 5-12.
  • [7] David Gale and F. M. Stewart, Infinite games with perfect information, Contributions to the theory of games, vol. 2, Annals of Mathematics Studies, no. 28, Princeton University Press, Princeton, N. J., 1953, pp. 245–266. MR 0054922
  • [8] Andrzej Grzegorczyk, Undecidability of some topological theories, Fund. Math. 38 (1951), 137–152. MR 0047583
  • [9] H. Läuchli, A decision procedure for the weak second order theory of linear order., Contributions to Math. Logic (Colloquium, Hannover, 1966) North-Holland, Amsterdam, 1968, pp. 189–197. MR 0244026
  • [10] Robert McNaughton, Testing and generating infinite sequences by a finite automaton, Information and Control 9 (1966), 521–530. MR 0213241
  • [11] D. E. Muller, Infinite sequences and finite machines, AIEE Proc. Fourth Annual Symp. Switching Circuit Theory and Logical Design, 1963, pp. 3-16.
  • [12] Michael O. Rabin, Mathematical theory of automata, Proc. Sympos. Appl. Math., Vol. XIX, Amer. Math. Soc., Providence, R.I., 1967, pp. 153–175. MR 0239886
  • [13] M. O. Rabin and D. Scott, Finite automata and their decision problems, IBM J. Res. Develop. 3 (1959), 114–125. MR 0103795
  • [14] Roman Sikorski, Boolean algebras, Ergebnisse der Mathematik und ihrer Grenzgebiete, N. F., Heft 25, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1960. MR 0126393
  • [15] A. Tarski, Arithmetical classes and types of Boolean algebras, Bull. Amer. Math. Soc. 55 (1949), 64.
  • [16] J. W. Thatcher and J. B. Wright, Generalized finite automata, Notices Amer. Math. Soc. 12 (1965), 820.
  • [17] Philip Wolfe, The strict determinateness of certain infinite games, Pacific J. Math. 5 (1955), 841–847. MR 0073909

Similar Articles

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

Retrieve articles in all journals with MSC: 02.32


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1969-0246760-1
Article copyright: © Copyright 1969 American Mathematical Society