Elimination of quantifiers from arithmetical formulas defining recursively enumerable sets

DOI10.1016/J.MATCOM.2004.05.013zbMATH Open1073.68898DBLPjournals/mcs/Matiyasevich04OpenAlexW2031689412WikidataQ56896664 ScholiaQ56896664MaRDI QIDQ1887829FDOQ1887829

Yu. 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 of theories and sets of sentences (03B25) Recursively (computably) enumerable sets and degrees (03D25) Quantifier elimination, model completeness, and related topics (03C10) Decidability (number-theoretic aspects) (11U05)

Cites Work

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

Cited In (1)

• Quantifier elimination for infinite terms

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1887829)