Definability, decidability, complexity
DOI10.1007/BF02127802zbMATH Open0865.03007MaRDI QIDQ1817073FDOQ1817073
Authors: Patrick Cégielski 
Publication date: 1 July 1997
Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)
Recommendations
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 (13)
- Complexity, decidability and completeness
- Definability in the real universe
- 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
- The lattice of definability. Origins, recent developments, and further directions
- 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
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)
