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

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

• 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?)
• 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
• DIOPHANTINE SETS
• Decidability of some Problems Pertaining to Base 2 Exponential Diophantine Equations
• Decision problems for differential equations
• Hilbert's Tenth Problem: What was done and what is to be done
• 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 Undecidability of the Existence of Zeros of Real Elementary Functions
• The decision problem for exponential diophantine equations
• The model theory of ordered differential fields
• 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)