Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

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

The 2024 MCQ for Transactions of the American Mathematical Society is 1.48 .

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Decidability of second-order theories and automata on infinite trees.
HTML articles powered by AMS MathViewer

by Michael O. Rabin
Trans. Amer. Math. Soc. 141 (1969), 1-35
DOI: https://doi.org/10.1090/S0002-9947-1969-0246760-1
PDF | Request permission
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
    • J. E. Doner, Decidability of the weak second-order theory of two successors, Notices Amer. Math. Soc. 12 (1965), 819. A. Ehrenfeucht, Decidability of the theory of one function, Notices Amer. Math. Soc. 6 (1959), 268. —, Decidability of the theory of one linear ordering relation, Notices Amer. Math. Soc. 6 (1959), 268-269. 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.
  • 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
  • Andrzej Grzegorczyk, Undecidability of some topological theories, Fund. Math. 38 (1951), 137–152. MR 47583, DOI 10.4064/fm-38-1-137-152
  • 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
  • Robert McNaughton, Testing and generating infinite sequences by a finite automaton, Information and Control 9 (1966), 521–530. MR 213241, DOI 10.1016/S0019-9958(66)80013-X
    • D. E. Muller, Infinite sequences and finite machines, AIEE Proc. Fourth Annual Symp. Switching Circuit Theory and Logical Design, 1963, pp. 3-16.
  • 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
  • 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
  • Roman Sikorski, Boolean algebras, Ergebnisse der Mathematik und ihrer Grenzgebiete, (N.F.), Heft 25, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1960. MR 0126393
    • A. Tarski, Arithmetical classes and types of Boolean algebras, Bull. Amer. Math. Soc. 55 (1949), 64. J. W. Thatcher and J. B. Wright, Generalized finite automata, Notices Amer. Math. Soc. 12 (1965), 820.
  • Philip Wolfe, The strict determinateness of certain infinite games, Pacific J. Math. 5 (1955), 841–847. MR 73909, DOI 10.2140/pjm.1955.5.841
Similar Articles
  • Retrieve articles in Transactions of the American Mathematical Society with MSC: 02.32
  • Retrieve articles in all journals with MSC: 02.32
Bibliographic Information
  • © Copyright 1969 American Mathematical Society
  • 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