Linear problems in valued fields

DOI10.1006/JSCO.1999.0303MaRDI QIDQ1582303zbMATH OpenOpenAlexFDO

Authors Thomas Sturm

Publication date 6 February 2001

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/6a89c418316491806a83b3d539dcbee04367366c

zbMATH Keywords

complexitydecision problemselimination setslinear formulasquantifier elimination proceduressubstructure completenessvalued fields

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Quantifier elimination, model completeness, and related topics (03C10) Model-theoretic algebra (03C60) Valued fields (12J10) Model theory of fields (12L12) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Review text

Extending the Skolem sets introduced by Weispfenning in 1988, the author gives quantifier elimination procedures of comparatively moderate complexity for linear problems in various classes of valued fields. Some consequences concerning the complexity of the decision problems and substructure completeness w.r.t. linear formulas for the considered classes of valued fields are also obtained.

Recommendations

• The complexity of linear problems in fields
• scientific article; zbMATH DE number 3935016
• Applying Linear Quantifier Elimination
• SEPARABLY CLOSED VALUED FIELDS: QUANTIFIER ELIMINATION
• Quantifier elimination on some pseudo-algebraically closed valued fields

Cites work

• A new approach for automatic theorem proving in real geometry
• Applying Linear Quantifier Elimination
• Diophantine Problems Over Local Fields I
• Diophantine problems over local fields. III: Decidable fields
• scientific article; zbMATH DE number 3935016 (Why is no real title available?)
• scientific article; zbMATH DE number 1189070 (Why is no real title available?)
• scientific article; zbMATH DE number 1302474 (Why is no real title available?)
• scientific article; zbMATH DE number 1744775 (Why is no real title available?)
• scientific article; zbMATH DE number 3430641 (Why is no real title available?)
• On definable subsets of p-adic fields
• Reasoning over networks by symbolic methods
• Simplification of quantifier-free formulae over ordered fields
• The complexity of linear problems in fields
• The complexity of logical theories
• The computational complexity of logical theories

Cited in

(5)

• The complexity of linear problems in fields
• Effective Quantifier Elimination for Presburger Arithmetic with Infinity
• Positive existential Definability with unit, addition and coprimeness
• Better answers to real questions
• Weak quantifier elimination for the full linear theory of the integers

Describes a project that uses

Uses Software

• REDLOG

This page was built for publication: Linear problems in valued fields

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