Computational complexity of logical theories of one successor and another unary function

DOI10.1007/s00153-006-0031-1zbMath1110.03025OpenAlexW2160473480MaRDI QIDQ868664

Pascal Michel

Publication date: 6 March 2007

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00153-006-0031-1

zbMATH Keywords

computational complexitylogical theoriesEhrenfeucht-Fraïssé games

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Simplifying the solution of Ljunggren's equation \(x^ 2+1=2y^ 4\)
• Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
• A uniform method for proving lower bounds on the computational complexity of logical theories
• On the computational complexity of the theory of Abelian groups
• The complexity of logical theories
• Complexity of logical theories involving coprimality
• The computational complexity of logical theories
• A new solution of the diophantine equation \(X^ 2+1=2Y^ 4\)
• An application of games to the completeness problem for formalized theories
• LOGICAL THEORIES OF ONE-PLACE FUNCTIONS ON THE SET OF NATURAL NUMBERS
• A note on undecidable extensions of monadic second order successor arithmetic
• Decidability and undecidability of extensions of second (first) order theory of (generalized) successor
• A list of arithmetical structures complete with respect to the first-order definability

This page was built for publication: Computational complexity of logical theories of one successor and another unary function