The Diophantine Problem for Addition and Divisibility

DOI10.2307/1998219zbMath0374.02025OpenAlexW4249812585MaRDI QIDQ4152529

Leonard Lipshitz

Publication date: 1978

Full work available at URL: https://doi.org/10.2307/1998219

Mathematics Subject Classification ID

Decidability (number-theoretic aspects) (11U05) Decidability of theories and sets of sentences (03B25) Congruences; primitive roots; residue systems (11A07) Applications of computability and recursion theory (03D80)

Related Items (28)

On the solvability of a class of Diophantine equations and applications ⋮ Undecidable Existential Problems for Addition and Divisibility in Algebraic Number Rings. II ⋮ The laws of integer divisibility, and solution sets of linear divisibility conditions ⋮ On two-way FA with monotonic counters and quadratic Diophantine equations ⋮ Undecidable Existential Problems for Addition and Divisibility in Algebraic Number Rings ⋮ Reachability in Succinct and Parametric One-Counter Automata ⋮ Existential decidability for addition and divisibility in holomorphy subrings of global fields ⋮ NP-complete problems for systems of linear polynomial's values divisibilities ⋮ Solvable problems for transformers with reversal-bounded counters ⋮ A proof of Bel'tyukov-Lipshitz theorem by quasi-quantifier elimination. II: The main reduction ⋮ THE DIOPHANTINE PROBLEM FOR ADDITION AND DIVISIBILITY OVER SUBRINGS OF THE RATIONALS ⋮ INTERLEAVING LOGIC AND COUNTING ⋮ Simultaneous rigid E-unification and other decision problems related to the Herbrand theorem ⋮ Unnamed Item ⋮ The diophantine problem for addition and divisibility for subrings of rational functions over finite fields ⋮ Compositional satisfiability solving in separation logic ⋮ A proof of Bel'tyukov-Lipshitz theorem by quasi-quantifier elimination. I: Definitions and GCD-lemma ⋮ On parametric timed automata and one-counter machines ⋮ Decidability of the Existential Theory of the Set of Natural Numbers with Order, Divisibility, Power Functions, Power Predicates, and Constants ⋮ On an exponential predicate in polynomials over finite fields ⋮ Decidability of Sub-theories of Polynomials over a Finite Field ⋮ On two-way nondeterministic finite automata with one reversal-bounded counter ⋮ INTERPRETING ARITHMETIC IN THE FIRST-ORDER THEORY OF ADDITION AND COPRIMALITY OF POLYNOMIAL RINGS ⋮ Elliptic divisibility sequences and undecidable problems about rational points ⋮ The complexity of almost linear diophantine problems ⋮ Decidability questions for a ring of Laurent polynomials ⋮ A view of computability on term algebras ⋮ A note on Parikh maps, abstract languages, and decision problems

Cites Work

• On the Chinese Remainder Theorem
• Definability and decision problems in arithmetic
• Unnamed Item

This page was built for publication: The Diophantine Problem for Addition and Divisibility