Definability, decidability, complexity
DOI10.1007/BF02127802zbMath0865.03007MaRDI QIDQ1817073
Publication date: 1 July 1997
Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)
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)
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