Elimination of quantifiers from arithmetical formulas defining recursively enumerable sets

DOI10.1016/j.matcom.2004.05.013zbMath1073.68898OpenAlexW2031689412WikidataQ56896664 ScholiaQ56896664MaRDI QIDQ1887829

Yu. V. Matiyasevich

Publication date: 22 November 2004

Published in: Mathematics and Computers in Simulation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.matcom.2004.05.013

zbMATH Keywords

Diophantine equationsHilbert's tenth problemQuantifier eliminationDavis conjectureDPRM-theorem

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Decidability (number-theoretic aspects) (11U05) Decidability of theories and sets of sentences (03B25) Recursively (computably) enumerable sets and degrees (03D25) Quantifier elimination, model completeness, and related topics (03C10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Power series solutions of algebraic differential equations
• The decision problem for exponential diophantine equations
• NP-complete decision problems for binary quadratics
• A direct method for simulating partial recursive functions by Diophantine equations
• Arithmetical representation of recursively enumerable sets
• A Diophantine Problem for Laurent Polynomial Rings
• Register machine proof of the theorem on exponential diophantine representation of enumerable sets
• Universal diophantine equation
• Proof of Recursive Unsolvability of Hilbert's Tenth Problem
• The model theory of ordered differential fields
• Reduction of an arbitrary diophantine equation to one in 13 unknowns
• Decision problems for differential equations
• The Undecidability of the Existence of Zeros of Real Elementary Functions
• Some undecidable problems involving elementary functions of a real variable
• On Canonical Forms and Simplification
• Some Recursively Unsolvable Problems in Analysis
• Zwei Unentscheidbare Probleme Der Analysis
• Some representations of Diophantine sets
• DIOPHANTINE SETS
• Arithmetical problems and recursively enumerable predicates
• Decidability of some Problems Pertaining to Base 2 Exponential Diophantine Equations

This page was built for publication: Elimination of quantifiers from arithmetical formulas defining recursively enumerable sets