Definability and decidability issues in extensions of the integers with the divisibility predicate
From MaRDI portal
Publication:4894724
DOI10.2307/2275673zbMath0868.11061OpenAlexW2030664340WikidataQ56896689 ScholiaQ56896689MaRDI QIDQ4894724
Yu. V. Matiyasevich, Patrick Cégielski, Denis Richard
Publication date: 24 November 1996
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2275673
Decidability (number-theoretic aspects) (11U05) Decidability of theories and sets of sentences (03B25) Interpolation, preservation, definability (03C40) Model theory (number-theoretic aspects) (11U09)
Related Items
A list of arithmetical structures complete with respect to the first-order definability ⋮ Definability, decidability, complexity ⋮ Undecidable extensions of Skolem arithmetic
Cites Work
- A uniform method for proving lower bounds on the computational complexity of logical theories
- All arithmetical sets of powers of primes are first-order definable in terms of the successor function and the coprimeness predicate
- Answer to a problem raised by J. Robinson: The arithmetic of positive or negative integers is definable from successor and divisibility
- Recognition and parsing of context-free languages in time n3
- Definability and decision problems in arithmetic
This page was built for publication: Definability and decidability issues in extensions of the integers with the divisibility predicate
