Decidability of second-order theories and automata on infinite trees
HTML articles powered by AMS MathViewer
- by Michael O. Rabin PDF
- Bull. Amer. Math. Soc. 74 (1968), 1025-1029
References
- 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
- J. Richard Büchi, Decision methods in the theory of ordinals, Bull. Amer. Math. Soc. 71 (1965), 767–770. MR 189997, DOI 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.
- Andrzej Grzegorczyk, Undecidability of some topological theories, Fund. Math. 38 (1951), 137–152. MR 47583, DOI 10.4064/fm-38-1-137-152 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
- Journal: Bull. Amer. Math. Soc. 74 (1968), 1025-1029
- DOI: https://doi.org/10.1090/S0002-9904-1968-12122-6
- MathSciNet review: 0231716