Definability, decidability, complexity

DOI10.1007/BF02127802zbMath0865.03007MaRDI QIDQ1817073

Patrick Cégielski

Publication date: 1 July 1997

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

surveycomputational complexityfirst-order logicdecidabilitydefinabilityHilbert's tenth problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability (number-theoretic aspects) (11U05) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

On the ‘definability of definable’ problem of Alfred Tarski, Part II ⋮ Some new results in monadic second-order arithmetic ⋮ Unnamed Item ⋮ On arithmetical first-order theories allowing encoding and decoding of lists ⋮ Decidability of the theory of the natural integers with the Cantor pairing function and the successor ⋮ A list of arithmetical structures complete with respect to the first-order definability

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Collected papers. Volume 1: 1921--1934. Volume 2: 1935--1944. Volume 3: 1945--1957. Volume 4: 1958--1979. Ed. by Steven R. Givant and Ralph N. McKenzie
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• Contribution à l'étude d'une conjecture de théorie des nombres par le codage ZBV. (Contribution to the study of a conjecture of number theory by ZBV coding)
• All arithmetical sets of powers of primes are first-order definable in terms of the successor function and the coprimeness predicate
• Definability in terms of the successor function and the coprimeness predicate in the set of arbitrary integers
• On the complexity of models of arithmetic
• Answer to a problem raised by J. Robinson: The arithmetic of positive or negative integers is definable from successor and divisibility
• Universal diophantine equation
• Hilbert's Tenth Problem and the Independence of Recursive Difference
• Diophantine Representation of the Set of Prime Numbers
• Hilbert's Tenth Problem is Unsolvable
• Reduction of an arbitrary diophantine equation to one in 13 unknowns
• Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
• Über die Nicht-charakterisierbarkeit der Zahlenreihe mittels endlich oder abzählbar unendlich vieler Aussagen mit ausschliesslich Zahlenvariablen
• On the independence of undefined ideas
• Definability and decidability issues in extensions of the integers with the divisibility predicate
• Contributions to the Theory of Optimal Control. A General Procedure for the Computation of Switching Manifolds
• Extensions of some theorems of Gödel and Church
• On Computable Numbers, with an Application to the Entscheidungsproblem
• A problem concerning the notion of definability
• Definability and decision problems in arithmetic
• Recursive Predicates and Quantifiers
• Unsolved problems in number theory

This page was built for publication: Definability, decidability, complexity