Elimination of quantifiers from arithmetical formulas defining recursively enumerable sets

DOI10.1016/J.MATCOM.2004.05.013MaRDI QIDQ1887829zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

Davis conjectureDiophantine equationsDPRM-theoremHilbert's tenth problemQuantifier elimination

Mathematics Subject Classification ID

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

Cites work

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

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)