Weak monadic second order theory of succesor is not elementary-recursive
- 1 January 1975
- book chapter
- Published by Springer Nature in Lecture Notes in Mathematics
- p. 132-154
- https://doi.org/10.1007/bfb0064872
Abstract
No abstract availableKeywords
This publication has 8 references indexed in Scilit:
- Elementary bounds for presburger arithmeticPublished by Association for Computing Machinery (ACM) ,1973
- Word problems requiring exponential time(Preliminary Report)Published by Association for Computing Machinery (ACM) ,1973
- On Effective Procedures for Speeding Up AlgorithmsJournal of the ACM, 1971
- A Machine-Independent Theory of the Complexity of Recursive FunctionsJournal of the ACM, 1967
- Decidability and undecidability of extensions of second (first) order theory of (generalized) successorThe Journal of Symbolic Logic, 1966
- Hierarchies of memory limited computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1965
- Classes of predictably computable functionsTransactions of the American Mathematical Society, 1963
- Weak Second‐Order Arithmetic and Finite AutomataMathematical Logic Quarterly, 1960