Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Blum, M. A machine-independent theory of the complexity of recursive functions, Jour. Assoc. Comp. Mach., 14, 2 (April, 1967), 322–336.
Blum, M. On effective procedures for speeding up algorithms, Jour. Assoc. Comp. Mach., 18, 2 (April, 1971), 290–305.
Büchi, J.R. and C.C. Elgot, Decision problems of weak second order arithmetics and finite automata, Part I, (abstract), AMS Notices, 5 (1959), 834.
Büchi, J.R. Weak second order arithmetic and finite automata, Zeit. f. Math. Log. and Grund. der Math., 6 (1960), 66–92.
Cooper, D.C. Theorem-proving in arithmetic without multiplication, Computer and Logic Group Memo. No. 16, U.C. of Swansea, April, 1972, to appear in Machine Intelligence 7.
Elgot, C.C. and M.O. Rabin, Decidability and undecidability of extensions of second (first) order theory of (generalized) successor, Jour. Symb. Logic, 31, 2 (June, 1966), 169–181.
Ferrante, J. and C. Rackoff, A decision procedure for the first order theory of real addition with order, Project MAC Tech. Memo 33, Mass. Inst. of Technology (May, 1973), 16pp., to appear SIAM Jour. Comp.
Grzegorczyk, A. Some classes of recursive functions, Rozprawy Matematyczne, 4 (1953), Warsaw, 1–45.
Meyer, A.R. Weak SIS cannot be decided (abstract 72T-E67), AMS Notices, 19, 5 (August, 1972), p. A-598.
Meyer, A.R. and L.J. Stockmeyer, The equivalence problem for regular expressions with squaring requires exponential space, 13 th Switching and Automata Theory Symp. (Oct. 1972), IEEE, 125–129.
Oppen, D.C. Elementary bounds for Presburger arithmetic, 5 th ACM Symp. Theory of Computing (April, 1973), 34–37.
Rabin, M.O. Decidability of second-order theories and automata on infinite trees, Trans. AMS, 141 (July, 1969), 1–35.
Rabin, M.O. and D. Scott, Finite automata and their decision problems, IBM Jour. Research and Development, 3 (1959), 115–125.
Ritchie, R.W. Classes of predictably computable functions, Trans. AMS, 106 (1963), 139–173.
Stearns, R.E., J. Hartmanis, and P.M. Lewis, III, Hierarchies of memory-limited computations, 6 th Switching Theory and Logical Design Symp. (1965), IEEE, 179–190.
Stockmeyer, L.J. and A.R. Meyer, Word problems requiring exponential time, 5 th ACM Symp. Theory of Computing (April, 1973), 1–9.
Editor information
Rights and permissions
Copyright information
© 1975 Springer-Verlag Berlin · Heidelberg
About this paper
Cite this paper
Meyer, A.R. (1975). Weak monadic second order theory of succesor is not elementary-recursive. In: Parikh, R. (eds) Logic Colloquium. Lecture Notes in Mathematics, vol 453. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0064872
Download citation
DOI: https://doi.org/10.1007/BFb0064872
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-07155-6
Online ISBN: 978-3-540-37483-1
eBook Packages: Springer Book Archive