The complexity of linear problems in fields

DOI10.1016/S0747-7171(88)80003-8zbMATH Open0646.03005MaRDI QIDQ1103602FDOQ1103602

Volker Weispfenning

Publication date: 1988

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

zbMATH Keywords

ordered fieldsComplexity bounds for decision problemslinear sentencesspace and time complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Decidability of theories and sets of sentences (03B25) Decidability and field theory (12L05) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• A Decision Procedure for the First Order Theory of Real Addition with Order
• Complexity of Boolean algebras
• Definability and fast quantifier elimination in algebraically closed fields
• The complexity of logical theories
• Elimination of quantifiers in algebraic structures
• The computational complexity of logical theories
• Presburger arithmetic with bounded quantifier alternation
• The complexity of Presburger arithmetic with bounded quantifier alternation depth
• Bounds on transfer principles for algebraically closed and complete discretely valued fields
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (77)

• An Algebraic Study of Affine Real Ultrafilters
• Supporting Global Numerical Optimization of Rational Functions by Generic Symbolic Convexity Tests
• A Folding Algorithm for Eliminating Existential Variables from Constraint Logic Programs
• Effective Quantifier Elimination for Presburger Arithmetic with Infinity
• Parametric Qualitative Analysis of Ordinary Differential Equations: Computer Algebra Methods for Excluding Oscillations (Extended Abstract) (Invited Talk)
• Multiple object semilinear motion planning
• Sets of Linear Forms Which Are Hard to Compute
• Erratum to: ``Analyzing restricted fragments of the theory of linear arithmetic
• Verification of data-aware process models: checking soundness of Data Petri nets
• Title not available (Why is that?)
• Verified Quadratic Virtual Substitution for Real Arithmetic
• Faster one block quantifier elimination for regular polynomial systems of equations
• Positive existential Definability with unit, addition and coprimeness
• Applying term rewriting methods to finite groups
• On the complexity of quantified linear systems
• Relationships of properties of piecewise affine maps over ordered fields
• On Hierarchical Reasoning in Combinations of Theories
• A proof of Bel'tyukov-Lipshitz theorem by quasi-quantifier elimination. I: Definitions and GCD-lemma
• Complexity of the satisfiability problem for multilinear forms over a finite field
• A decision algorithm for linear sentences on a PFM
• Algorithmic methods for investigating equilibria in epidemic modeling
• An Exact Correspondence of Linear Problems and Randomizing Linear Algorithms
• Better answers to real questions
• Solution formulas for cubic equations without or with constraints
• A bibliography of quantifier elimination for real closed fields
• Decidable \({\exists}^*{\forall}^*\) first-order fragments of linear rational arithmetic with uninterpreted predicates
• Testing binomiality of chemical reaction networks using comprehensive Gröbner systems
• On the parallel complexity of the polynomial ideal membership problem
• A decision procedure for linear ``big O equations
• Tropical effective primary and dual Nullstellensätze
• A representation of convex semilinear sets
• A survey of some methods for real quantifier elimination, decision, and satisfiability and their applications
• On quantified linear implications
• SMT-RAT: An Open Source C++ Toolbox for Strategic and Parallel SMT Solving
• Sur la complexité du principe de Tarski-Seidenberg
• Model-theoretic methods in combined constraint satisfiability
• Title not available (Why is that?)
• A logic based approach to finding real singularities of implicit ordinary differential equations
• Dines-Fourier-Motzkin quantifier elimination and an application of corresponding transfer principles over ordered fields
• Automatic generation of bounds for polynomial systems with application to the Lorenz system
• Polynomial Bell Inequalities
• Reachability relations of timed pushdown automata
• Applied Algebraic Geometry in Model Based Design for Manufacturing
• Some lower bounds for the complexity of the linear programming feasibility problem over the reals
• Efficiently and effectively recognizing toricity of steady state varieties
• Algorithmic reduction of biological networks with multiple time scales
• An effective implementation of symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
• A geometric method for model reduction of biochemical networks with polynomial rate functions
• Adapting Real Quantifier Elimination Methods for Conflict Set Computation
• Virtual Substitution for SMT-Solving
• Classical numerical methods in engineering: a note on existential quantifier elimination under parametric inequality constraints
• Identifying the parametric occurrence of multiple steady states for some biological networks
• Proof synthesis and reflection for linear arithmetic
• On sets of linear forms of maximal complexity
• Algorithmic global criteria for excluding oscillations
• Some formal tools for analyzing quantum automata.
• Linear Programs and Convex Hulls Over Fields of Puiseux Fractions
• Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields
• Quantifier elimination in automatic loop parallelization
• The complexity of almost linear diophantine problems
• On Interpolation and Symbol Elimination in Theory Extensions
• Title not available (Why is that?)
• Quantifier elimination for a class of exponential polynomial formulas
• Counting and Gröbner bases
• A complexity perspective on entailment of parameterized linear constraints
• Convex polarities over ordered fields
• Detection of Hopf bifurcations in chemical reaction networks using convex coordinates
• Linear problems in valued fields
• Formulation of linear problems and solution by a universal machine
• A symbolic-numeric approach to multi-objective optimization in manufacturing design
• Weak quantifier elimination for the full linear theory of the integers
• Title not available (Why is that?)
• Automatic derivation of positivity conditions inside boundary elements with the help of the REDLOG computer logic package.
• Analyzing restricted fragments of the theory of linear arithmetic
• Solving and visualizing nonlinear parametric constraints in control based on quantifier elimination
• Computing Hopf Bifurcations in Chemical Reaction Networks Using Reaction Coordinates
• Linear quantifier elimination

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• The computational complexity of some problems of linear algebra 👍 👎
• STACS 2005 👍 👎
• The proof complexity of linear algebra 👍 👎
• Complexity of the satisfiability problem for multilinear forms over a finite field 👍 👎
• The complexity of almost linear diophantine problems 👍 👎
• Linear problems in valued fields 👍 👎
• The computational complexity of some problems of linear algebra 👍 👎

This page was built for publication: The complexity of linear problems in fields

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