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

DOI10.1007/s00153-006-0031-1zbMath1110.03025MaRDI 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 complexity; logical theories; Ehrenfeucht-Fraïssé games

Mathematics Subject Classification ID

03B25: Decidability of theories and sets of sentences

03D15: Complexity of computation (including implicit computational complexity)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

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