Complexity of deciding Tarski algebra

DOI10.1016/S0747-7171(88)80006-3zbMath0689.03021OpenAlexW2102074804MaRDI QIDQ1264143

Publication date: 1988

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

Full work available at URL: https://doi.org/10.1016/s0747-7171(88)80006-3

zbMATH Keywords

polynomial time Tarski algebra decision algorithm truth value of a formula

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Finding irreducible components of some real transcendental varieties, Parametric toricity of steady state varieties of reaction networks, Testing binomiality of chemical reaction networks using comprehensive Gröbner systems, Formulation of linear problems and solution by a universal machine, Characterizing positively invariant sets: inductive and topological methods, Recent Advances in Real Geometric Reasoning, Discrete semantics for hybrid automata. Avoiding misleading assumptions in systems biology, Local rules for pentagonal quasi-crystals, Complexity of stratifications of semi-Pfaffian sets, Real quantifier elimination for the synthesis of optimal numerical algorithms (case study: square root computation), A bibliography of quantifier elimination for real closed fields, Polar varieties, real equation solving, and data structures: the hypersurface case, Nearly sharp complexity bounds for multiprocessor algebraic computations, Complexity lower bounds for computation trees with elementary transcendental function gates, Lower bounds for arithmetic networks. II: Sum of Betti numbers, Illumination by floodlights, A transfer method from bounded existential Diophantine equations to Tarski algebra formulas, An Elementary Recursive Bound for Effective Positivstellensatz and Hilbert’s 17th problem, Variant quantifier elimination, Phenotype space and kinship assignment for the simpson index, A survey of some methods for real quantifier elimination, decision, and satisfiability and their applications, Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations, The complexity of planar compliant motion planning under uncertainty, A decidable theory involving addition of differentiable real functions, Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem, Unnamed Item, Homogeneous multivariate polynomials with the half-plane property, Effective Łojasiewicz inequalities in semialgebraic geometry, Topological complexity of the range searching, On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, On information invariants in robotics, The complexity of deciding consistency of systems of polynomials in exponent inequalities, Lower bound on testing membership to a polyhedron by algebraic decision and computation trees, A search-based procedure for nonlinear real arithmetic, Analyzing probabilistic pushdown automata, A numerical algorithm for zero counting. I: Complexity and accuracy, Grid methods in computational real algebraic (and semialgebraic) geometry, Elementary recursive quantifier elimination based on Thom encoding and sign determination, Counting connected components of a semialgebraic set in subexponential time, Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets, Stochastic game logic, Improved projection for cylindrical algebraic decomposition, Unnamed Item, Efficiently and effectively recognizing toricity of steady state varieties, A logic based approach to finding real singularities of implicit ordinary differential equations, Inclusion dynamics hybrid automata, Floodlight illumination of infinite wedges, Computing the homology of semialgebraic sets. I: Lax formulas, Lower bounds for arithmetic networks, Algorithmic reduction of biological networks with multiple time scales, Sur la complexité du principe de Tarski-Seidenberg, Finding connected components of a semialgebraic set in subexponential time, On the number of sets definable by polynomials, Unnamed Item, Complexity of computing the local dimension of a semialgebraic set, A complexity theory of constructible functions and sheaves, Special algorithm for stability analysis of multistable biological regulatory systems, Construction of roadmaps in semi-algebraic sets, Description of the connected components of a semialgebraic set in single exponential time, Decidable verification for reducible timed automata specified in a first order logic with time

Cites Work