Weak monadic second order theory of succesor is not elementary-recursive
作者： Albert R. Meyer
DOI: 10.1007/BFB0064872
关键词:
摘要:
springer.com
sci-hub.se 参考文章(13)
Andrzej Grzegorczyk, Some classes of recursive functions Państwowe Wydawn. Naukowe. ,(1964)
Derek C. Oppen, Elementary bounds for presburger arithmetic Proceedings of the fifth annual ACM symposium on Theory of computing - STOC '73. pp. 34- 37 ,(1973) , 10.1145/800125.804033
L. J. Stockmeyer, A. R. Meyer, Word problems requiring exponential time(Preliminary Report) Proceedings of the fifth annual ACM symposium on Theory of computing - STOC '73. pp. 1- 9 ,(1973) , 10.1145/800125.804029
Robert W. Ritchie, CLASSES OF PREDICTABLY COMPUTABLE FUNCTIONS Transactions of the American Mathematical Society. ,vol. 106, pp. 139- 173 ,(1963) , 10.1090/S0002-9947-1963-0158822-2
A. R. Meyer, L. J. Stockmeyer, The equivalence problem for regular expressions with squaring requires exponential space 13th Annual Symposium on Switching and Automata Theory (swat 1972). pp. 125- 129 ,(1972) , 10.1109/SWAT.1972.29
Jeanne Ferrante, Charles Rackoff, A Decision Procedure for the First Order Theory of Real Addition with Order SIAM Journal on Computing. ,vol. 4, pp. 69- 76 ,(1975) , 10.1137/0204006
M. O. Rabin, D. Scott, Finite automata and their decision problems Ibm Journal of Research and Development. ,vol. 3, pp. 114- 125 ,(1959) , 10.1147/RD.32.0114
Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions Journal of the ACM. ,vol. 14, pp. 322- 336 ,(1967) , 10.1145/321386.321395
Manuel Blum, On Effective Procedures for Speeding Up Algorithms Journal of the ACM. ,vol. 18, pp. 290- 305 ,(1971) , 10.1145/321637.321648
Calvin C. Elgot, Michael O. Rabin, Decidability and Undecidability of Extensions of Second (First) Order Theory of (Generalized) Successor Journal of Symbolic Logic. ,vol. 31, pp. 169- 181 ,(1966) , 10.2307/2269808