zbMATH — the first resource for mathematics

The recursive sets in certain monadic second order fragments of arithmetic. (English) Zbl 0325.02033

03B25 Decidability of theories and sets of sentences
03D05 Automata and formal grammars in connection with logical questions
03D25 Recursively (computably) enumerable sets and degrees
Full Text: DOI EuDML
[1] Büchi, J.R.: On a decision method in restricted second-order arithmetic. In: Logic Meth. Phil. Sc., Proc. 1960 Stanford Inter. Congr. Stanford 1962, 1–11. · Zbl 0147.25103
[2] Büchi, J.R., Landweber, L.H.: Definability in the monadic second-order theory of successor. J. Symb. Logic34 (1969), 166–170. · Zbl 0209.02203 · doi:10.2307/2271090
[3] Büchi, J.R., Siefkes, D.: Decidable theories II: The monadic second order theory of all countable ordinals. Lect. Notes Math. 328. Springer-Verlag, Berlin-Heidelberg-New York 1973. · Zbl 0298.02050
[4] Hanf, W.: Model theoretic methods in the study of elementary logic. In: The theory of models, Proc. 1963 Int. Symp. Berkeley (Ed. Addison, Henkin, Tarski). Amsterdam 1965, 132–145.
[5] McNaughton, R.: Testing and generating infinite sequences by a finite automaton. Information and Control9 (1966), 521–530. · Zbl 0212.33902 · doi:10.1016/S0019-9958(66)80013-X
[6] Myhill, J.: Creative sets. Z. Math. Logik Grundl. Math.1 (1955), 97–108. · Zbl 0065.00105 · doi:10.1002/malq.19550010205
[7] Rabin, M.O.: A simple method for undecidability proofs and some applications. In: Logic Meth. Phil. Sc., Proc. 1964 Jerusalem Inter. Congr. Amsterdam 1965, 58–68. · Zbl 0192.05502
[8] Rabin, M.O.: Decidability of second-order theories and automata on infinite trees. Transactions AMS141 (1969), 1–35. · Zbl 0221.02031
[9] Rabin, M.O.: Automata on infinite objects and Church’s problem. Conference Board Math. Sc., Regional Conf. Series in Math., No. 13, AMS, Providence, 1972. · Zbl 0315.02037
[10] Robinson, J.: Definability and decision problems in arithmetic. J. Symb. Logic14 (1949), 98–114. · Zbl 0034.00801 · doi:10.2307/2266510
[11] Robinson, R.M.: Restricted set-theoretical definitions in arithmetic. Proc. AMS9, (1958), 238–242. · Zbl 0112.00702 · doi:10.1090/S0002-9939-1958-0093479-4
[12] Siefkes, D.: Decidable monadic second order theories of arithmetic. Ph.D. thesis Heidelberg 1969. · Zbl 0213.01901
[13] Siefkes, D.: Decidable theories I: Büchi’s monadic second order successor arithmetic. Lect. Notes Math. 120, Springer-Verlag, Berlin-Heidelberg-New York 1970. · Zbl 0399.03011
[14] Specker, E.: Eine Verschärfung des Unvollständigkeitssatzes des Zahlentheorie. Bull. Acad. Pol. Sci., Cl. III, Vol.5 (1957), 1041–1045. · Zbl 0078.24601
[15] Tarski, A., Mostowski, A., Robinson, R.M.: Undecidable theories. Amsterdam 1953. · Zbl 0053.00401
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.