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
DOI: https://doi.org/10.1090/S0002-9947-1969-0246760-1
MathSciNet review: 0246760
Full-text PDF

References | Similar Articles | Additional Information

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

  • [1] J. R. Büchi, On a decision method in restricted second order arithmetic, Proc. Internat. Congr. Logic, Method. and Philos. Sci. 1960, Stanford Univ. Press, Stanford, California, 1962, pp. 1-11. MR 0183636 (32:1116)
  • [2] -, Decision methods in the theory of ordinals, Bull. Amer. Math. Soc. 71 (1965), 767-770. MR 0189997 (32:7413)
  • [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] D. Gale and F. M. Stewart, ``Infinite games with perfect information,'' in Contributions to the theory of games. II, Ann. of Math. Studies, No. 28, Princeton Univ. Press, Princeton, N. J., 1953, pp. 245-266. MR 0054922 (14:999b)
  • [8] A. Grzegorczyk, Undecidability of some topological theories, Fund. Math. 38 (1951), 137-152. MR 0047583 (13:898e)
  • [9] H. Läuchli, ``A decision procedure for the weak second order theory of linear order'' in Contributions to mathematical logic, K. Schutte, editor, North-Holland, Amsterdam, 1968, pp. 189-197. MR 0244026 (39:5343)
  • [10] R. McNaughton, Testing and generating infinite sequences by a finite automaton, Information and Control 9 (1966), 521-530. MR 0213241 (35:4105)
  • [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] M. O. Rabin, Mathematical theory of automata, Proc. Sympos. Appl. Math., Vol. 19, Amer. Math. Soc., Providence, R. I., 1968, pp, 153-175. MR 0239886 (39:1243)
  • [13] M. O. Rabin and D. Scott, Finite automata and their decision problems, IBM J. Res. Develop. 3 (1959), 114-125; reprinted in Sequential machines, selected papers, edited by E. F. Moore, Addison-Wesley, Reading, Mass., 1964. MR 0103795 (21:2559)
  • [14] R. Sikorski, Boolean algebras, 2nd ed., Ergebnisse der Math., Vol. 25, Springer-Verlag, Berlin, 1964. MR 0126393 (23:A3689)
  • [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] P. Wolfe, The strict determinateness of certain infinite games, Pacific J. Math. 5 (1955), 841-847. MR 0073909 (17:506f)

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

American Mathematical Society