Weak monadic second order theory of successor is not elementary- recursive. (English) Zbl 0326.02036
Logic Colloq., Symp. Logic Boston 1972-73, Lect. Notes Math. 453, 132-154 (1975).
MSC:
| 03B25 | Decidability of theories and sets of sentences |
| 03D05 | Automata and formal grammars in connection with logical questions |
| 03D10 | Turing machines and related notions |
| 68Q25 | Analysis of algorithms and problem complexity |
