The complexity of almost linear diophantine problems
From MaRDI portal
Publication:753494
DOI10.1016/S0747-7171(08)80051-XzbMath0716.68050MaRDI QIDQ753494
Publication date: 1990
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) First-order arithmetic and fragments (03F30)
Related Items (8)
Presburger liveness verification of discrete timed automata. ⋮ Quantifier elimination for the reals with a predicate for the powers of two ⋮ A quantifier-elimination based heuristic for automatically generating inductive assertions for programs ⋮ Quantifier elimination for counting extensions of Presburger arithmetic ⋮ Weak quantifier elimination for the full linear theory of the integers ⋮ Proof synthesis and reflection for linear arithmetic ⋮ A complete and terminating approach to linear integer solving ⋮ Effective Quantifier Elimination for Presburger Arithmetic with Infinity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
- The complexity of logical theories
- The complexity of Presburger arithmetic with bounded quantifier alternation depth
- The polynomial-time hierarchy
- The computational complexity of logical theories
- Complexity of Subcases of Presburger Arithmetic
- On the SUP-INF Method for Proving Presburger Formulas
- A Decision Procedure for the First Order Theory of Real Addition with Order
- The Diophantine Problem for Addition and Divisibility
- A Bound on Solutions of Linear Integer Equalities and Inequalities
- An NP-Complete Number-Theoretic Problem
- Presburger arithmetic with bounded quantifier alternation
- Contributions to the theory of Diophantine equations II. The Diophantine equation y 2 = x 3 + k
This page was built for publication: The complexity of almost linear diophantine problems
