Definability, decidability, complexity
DOI10.1007/BF02127802zbMATH Open0865.03007MaRDI QIDQ1817073FDOQ1817073
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) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Decidability (number-theoretic aspects) (11U05)
Cites Work
- Title not available (Why is that?)
- Extensions of some theorems of Gödel and Church
- Title not available (Why is that?)
- Reduction of an arbitrary diophantine equation to one in 13 unknowns
- On Computable Numbers, with an Application to the Entscheidungsproblem
- The polynomial-time hierarchy
- Title not available (Why is that?)
- Title not available (Why is that?)
- Hilbert's Tenth Problem and the Independence of Recursive Difference
- Unsolved problems in number theory
- Über die Nicht-charakterisierbarkeit der Zahlenreihe mittels endlich oder abzählbar unendlich vieler Aussagen mit ausschliesslich Zahlenvariablen
- Title not available (Why is that?)
- Definability and decision problems in arithmetic
- Title not available (Why is that?)
- Hilbert's Tenth Problem is Unsolvable
- Universal diophantine equation
- Complete sets and the polynomial-time hierarchy
- Recursive Predicates and Quantifiers
- Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
- On the complexity of models of arithmetic
- A problem concerning the notion of definability
- 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
- Diophantine Representation of the Set of Prime Numbers
- Contributions to the Theory of Optimal Control. A General Procedure for the Computation of Switching Manifolds
- Answer to a problem raised by J. Robinson: The arithmetic of positive or negative integers is definable from successor and divisibility
- Definability and decidability issues in extensions of the integers with the divisibility predicate
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- On the independence of undefined ideas
Cited In (11)
- Complexity, decidability and completeness
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Tarski's theory of definability: Common themes in descriptive set theory, recursive function theory, classical pure logic, and finite-universe logic
- 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
- Some new results in monadic second-order arithmetic
- On the ‘definability of definable’ problem of Alfred Tarski, Part II
- A list of arithmetical structures complete with respect to the first-order definability
Recommendations
This page was built for publication: Definability, decidability, complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1817073)
