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

DOI10.1007/S00153-006-0031-1zbMATH Open1110.03025OpenAlexW2160473480MaRDI QIDQ868664FDOQ868664

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

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

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)

Cites Work

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

Cited In (3)

• Spectra and satisfiability for logics with successor and a unary function
• Complexity of logical theories involving coprimality
• Title not available (Why is that?)

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)