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

DOI10.1007/S00153-006-0031-1MaRDI QIDQ868664zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Complexity of logical theories involving coprimality
• scientific article; zbMATH DE number 1148335
• scientific article; zbMATH DE number 849963
• On arithmetic complexity of some constructive logics
• scientific article; zbMATH DE number 1567841

Cites work

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

Cited in

(4)

• Spectra and satisfiability for logics with successor and a unary function
• Complexity of logical theories involving coprimality
• scientific article; zbMATH DE number 2144731 (Why is no real title available?)
• Computational complexity of theories of a binary predicate with a small number of variables

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q868664)