scientific article; zbMATH DE number 3501006

Michael J. Fischer, Michael O. Rabin

Publication date: 1974

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Analysis of algorithms and problem complexity (68Q25) Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25)

Related Items

Equational theories of tropical semirings ⋮ Formulation of linear problems and solution by a universal machine ⋮ Computation in networks of passively mobile finite-state sensors ⋮ Complexity of Subcases of Presburger Arithmetic ⋮ Linear Integer Arithmetic Revisited ⋮ The complexity of elementary algebra and geometry ⋮ Computer algebra: Past and future ⋮ Generic complexity of Presburger arithmetic ⋮ On the computational complexity of the theory of Abelian groups ⋮ Complexity of modal logics with Presburger constraints ⋮ The complexity of linear problems in fields ⋮ A bibliography of quantifier elimination for real closed fields ⋮ Complexity of Presburger arithmetic with fixed quantifier dimension ⋮ Short Presburger Arithmetic Is Hard ⋮ XML schema, tree logic and sheaves automata ⋮ The complexity of query evaluation in indefinite temporal constraint databases ⋮ Subclasses of Presburger arithmetic and the polynomial-time hierarchy ⋮ Dominoes and the complexity of subclasses of logical theories ⋮ Quantifier elimination for the reals with a predicate for the powers of two ⋮ A class of algorithms which require nonlinear time to maintain disjoint sets ⋮ An undecidability theorem for lattices over group rings ⋮ THE RECOGNITION COMPLEXITY OF DECIDABLE THEORIES ⋮ Size-based termination of higher-order rewriting ⋮ Programming in metric temporal logic ⋮ Tautology testing with a generalized matrix reduction method ⋮ Temporal Specifications with Accumulative Values ⋮ Unnamed Item ⋮ Complexity, convexity and combinations of theories ⋮ More about Exact Slow $k$-Nim ⋮ Parametric Presburger arithmetic: complexity of counting and quantifier elimination ⋮ On Presburger arithmetic extended with non-unary counting quantifiers ⋮ The complexity of the equivalence problem for two characterizations of Presburger sets ⋮ Modal logics and local quantifiers: a zoo in the elementary hierarchy ⋮ On time-space classes and their relation to the theory of real addition ⋮ Remarks on recursion versus diagonalization and exponentially difficult problems ⋮ The complexity of logical theories ⋮ A decidable theory involving addition of differentiable real functions ⋮ The complexity of Presburger arithmetic with bounded quantifier alternation depth ⋮ A uniform method for proving lower bounds on the computational complexity of logical theories ⋮ Number of quantifiers is better than number of tape cells ⋮ Upper Bounds on the Automata Size for Integer and Mixed Real and Integer Linear Arithmetic (Extended Abstract) ⋮ Upper and lower bounds for first order expressibility ⋮ Complexity of computations in Commutative Division of the USSR Academy of Sciences ⋮ An approach to multicore parallelism using functional programming: a case study based on Presburger arithmetic ⋮ Out of order quantifier elimination for standard quantified linear programs ⋮ Proving inequalities and solving global optimization problems via simplified CAD projection ⋮ Exact complexity bounds for ordinal addition ⋮ Weak quantifier elimination for the full linear theory of the integers ⋮ Proof synthesis and reflection for linear arithmetic ⋮ Towards exact geometric computation ⋮ An improved lower bound for the elementary theories of trees ⋮ Target counting with Presburger constraints and its application in sensor networks ⋮ “Helping”: several formalizations ⋮ A practical approach to model checking duration calculus using Presburger arithmetic ⋮ Complexity of logical theories involving coprimality ⋮ On the complexity of finite, pushdown, and stack automata ⋮ Multitree automata that count ⋮ The complexity of verifying population protocols ⋮ A universally hard set of formulae with respect to non-deterministic Turing acceptors ⋮ Complexity-class-encoding sets ⋮ A $2^{2^{2^{pn}}}$ upper bound on the complexity of Presburger arithmetic ⋮ Some lower bounds for the complexity of the linear programming feasibility problem over the reals ⋮ A technique for proving decidability of containment and equivalence of linear constraint queries ⋮ Complexity of deciding Tarski algebra ⋮ A logic for reasoning about probabilities ⋮ The complexity of almost linear diophantine problems ⋮ Towards efficient verification of population protocols ⋮ A complete and terminating approach to linear integer solving ⋮ On the parallel complexity of the polynomial ideal membership problem ⋮ Effective Quantifier Elimination for Presburger Arithmetic with Infinity ⋮ Logical Theory of the Additive Monoid of Subsets of Natural Integers ⋮ Cancellativity in finitely presented semigroups ⋮ Unnamed Item ⋮ Decidability and modules over Bézout domains ⋮ The Value-Passing Calculus ⋮ Unnamed Item ⋮ On the definability of properties of finite graphs ⋮ Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories ⋮ Natural limitations of decision procedures for arithmetic with bounded quantifiers ⋮ Definability and fast quantifier elimination in algebraically closed fields ⋮ Symbolic model checking of timed guarded commands using difference decision diagrams ⋮ The max-plus algebra of the natural numbers has no finite equational basis