zbMATH — the first resource for mathematics

An axiom system for the weak monadic second order theory of two successors. (English) Zbl 0397.03009

03B25 Decidability of theories and sets of sentences
03D05 Automata and formal grammars in connection with logical questions
Full Text: DOI
[1] J. R. Buchi;Weak second order arithmetic and finite automata, Z. Math. Logik Grundlagen Math.6 (1960), 66–92. · Zbl 0103.24705 · doi:10.1002/malq.19600060105
[2] J. R. Buchi,On a decision method in restricted second order arithmetic, inLogic Meth. Phil. Sc., Proc. 1960 Stanford Int. Congr., Stanford, 1962, pp. 1–11.
[3] J. R. Buchi and D. Siefkes,Axiomatization of the monadic second order theory of \(\omega\) 1, Lect. Notes Math., vol. 328, Springer-Verlag, Berlin-Heidelberg-New York, 1973, pp. 129–217.
[4] J. Doner,Tree acceptors and some of their applications, J. Comput. System Sci.4 (1970), 406–451. · Zbl 0212.02901 · doi:10.1016/S0022-0000(70)80041-1
[5] M. Magidor and G. Moran,Finite automata over finite trees, Tech. Rep. No. 30, Dept. Math., The Hebrew University, Jerusalem, 1969.
[6] M. O. Rabin,Decidability of second-order theories and automata on infinite trees, Trans. Amer. Math. Soc.141 (1969), 1–35. · Zbl 0221.02031
[7] M. O. Rabin,Weakly definable relations and special automata, inMathematical Logic and Foundations of Set Theory, (Y. Bar-Hillel, ed.), Amsterdam, 1970, pp. 1–23.
[8] D. Siefkes,Decidable theories I; Buchi’s monadic second order successor artimetic, Lect. Notes Math., Vol. 120, Springer-Verlag, Berlin-Heidelberg-New York, 1970. · Zbl 0213.01901
[9] J. W. Thatcher and J. B. Wright,Generalized finite automata theory with an application to a decision problem of second-order logic, Mat. Systems Theory2 (1968), 57–81. · Zbl 0196.01901 · doi:10.1007/BF01691346
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.