Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Bulletin of the American Mathematical Society
Bulletin of the American Mathematical Society
ISSN 1088-9485(online) ISSN 0273-0979(print)

 

Decidability of second-order theories and automata on infinite trees


Author: Michael O. Rabin
Journal: Bull. Amer. Math. Soc. 74 (1968), 1025-1029
MathSciNet review: 0231716
Full-text PDF

References | 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 (32 #1116)
  • 2. J. Richard Büchi, Decision methods in the theory of ordinals, Bull. Amer. Math. Soc. 71 (1965), 767–770. MR 0189997 (32 #7413), http://dx.doi.org/10.1090/S0002-9904-1965-11384-2
  • 3. A. Ehrenfeucht, Decidability of the theory of one function, Notices Amer. Math. Soc. 6 (1959), 268.
  • 4. A. Ehrenfeucht, Decidability of the theory of one linear ordering relation, Notices Amer. Math. Soc. 6 (1959), 268-269.
  • 5. 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.
  • 6. Andrzej Grzegorczyk, Undecidability of some topological theories, Fund. Math. 38 (1951), 137–152. MR 0047583 (13,898e)
  • 7. H. Laüchli, Decidability of the weak second-order theory of linear ordering, Kolloquium über Logik Grundlagen der Math., Hanover 1966 (to appear).
  • 8. A. Tarski, Arithmetical classes and types of Boolean algebras, Bull. Amer. Math. Soc. 55 (1949), 64.


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9904-1968-12122-6
PII: S 0002-9904(1968)12122-6