Definability, decidability, complexity
type: Item
instance of: scholarly article
title: Definability, decidability, complexity
zbMATH Open document ID: 0865.03007
DOI: 10.1007/BF02127802
published in: Annals of Mathematics and Artificial Intelligence
publication date: 1997-07-01T00:00:00Z
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 03-02
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03B10
Mathematics Subject Classification ID: 11U05
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 951955
zbMATH Keywords: survey
zbMATH Keywords: definability
zbMATH Keywords: first-order logic
zbMATH Keywords: decidability
zbMATH Keywords: computational complexity
zbMATH Keywords: Hilbert's tenth problem
author: Patrick Cégielski
MaRDI profile type: Publication
cites work: Q5824680
cites work: Q4293543
cites work: Q3800030
cites work: Q4697160
cites work: Definability and decidability issues in extensions of the integers with the divisibility predicate
cites work: Hilbert's Tenth Problem is Unsolvable
cites work: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
cites work: Hilbert's Tenth Problem and the Independence of Recursive Difference
cites work: 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)
cites work: Unsolved problems in number theory
cites work: Universal diophantine equation
cites work: Diophantine Representation of the Set of Prime Numbers
cites work: Recursive Predicates and Quantifiers
cites work: Q4156744
cites work: Reduction of an arbitrary diophantine equation to one in 13 unknowns
cites work: On the complexity of models of arithmetic
cites work: On the independence of undefined ideas
cites work: Contributions to the Theory of Optimal Control. A General Procedure for the Computation of Switching Manifolds
cites work: Q4124795
cites work: Q3218118
cites work: All arithmetical sets of powers of primes are first-order definable in terms of the successor function and the coprimeness predicate
cites work: Answer to a problem raised by J. Robinson: The arithmetic of positive or negative integers is definable from successor and divisibility
cites work: Definability in terms of the successor function and the coprimeness predicate in the set of arbitrary integers
cites work: Definability and decision problems in arithmetic
cites work: Extensions of some theorems of Gödel and Church
cites work: Q5665241
cites work: Über die Nicht-charakterisierbarkeit der Zahlenreihe mittels endlich oder abzählbar unendlich vieler Aussagen mit ausschliesslich Zahlenvariablen
cites work: The polynomial-time hierarchy
cites work: A problem concerning the notion of definability
cites work: 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
cites work: On Computable Numbers, with an Application to the Entscheidungsproblem
cites work: Complete sets and the polynomial-time hierarchy
description: scientific article; zbMATH DE number 951955