The complexity of logical theories
From MaRDI portal
Cites work
- A \(2^{2^{2^{pn}}}\) upper bound on the complexity of Presburger arithmetic
- A Decision Procedure for the First Order Theory of Real Addition with Order
- scientific article; zbMATH DE number 3501006 (Why is no real title available?)
- scientific article; zbMATH DE number 3560737 (Why is no real title available?)
- On time-space classes and their relation to the theory of real addition
Cited in
(61)- Real addition and the polynomial hierarchy
- On the complexity of theories of permutations
- The complexity of elementary algebra and geometry
- The complexity of linear problems in fields
- A bibliography of quantifier elimination for real closed fields
- Subclasses of Presburger arithmetic and the polynomial-time hierarchy
- Dominoes and the complexity of subclasses of logical theories
- Complexity, convexity and combinations of theories
- On time-space classes and their relation to the theory of real addition
- The complexity of Presburger arithmetic with bounded quantifier alternation depth
- Complexity of logical theories involving coprimality
- Complexity of Presburger arithmetic with fixed quantifier dimension
- The complexity of query evaluation in indefinite temporal constraint databases
- A canonical form of vector machines
- Well-abstracted transition systems: Application to FIFO automata.
- Linear problems in valued fields
- Real computations with fake numbers
- Solving quantified linear arithmetic by counterexample-guided instantiation
- A logic for reasoning about probabilities
- Probabilistic game automata
- The complexity of verifying population protocols
- Automata-theoretical regularity characterizations for the iterated shuffle on commutative regular languages
- Emptiness problems for integer circuits
- A complete and terminating approach to linear integer solving
- Erratum to: ``Analyzing restricted fragments of the theory of linear arithmetic
- Equivalence between model-checking flat counter systems and Presburger arithmetic
- Alternating complexity of counting first-order logic for the subword order
- Colors Make Theories Hard
- Double-exponential inseparability of Robinson subsystem \(Q_{+}\)
- The role of rudimentary relations in complexity theory
- More about Exact Slow $k$-Nim
- Equivalence between model-checking flat counter systems and Presburger arithmetic
- Safe recursive set functions
- WORD EQUATIONS OVER GRAPH PRODUCTS
- Classifying the computational complexity of problems
- On the complexity of quantified linear systems
- Presburger arithmetic with unary predicates is Π11 complete
- On the complexity of team logic and its two-variable fragment
- Climbing up the elementary complexity classes with theories of automatic structures
- scientific article; zbMATH DE number 7577569 (Why is no real title available?)
- Model-Checking Counting Temporal Logics on Flat Structures
- Analyzing restricted fragments of the theory of linear arithmetic
- Presburger arithmetic with algebraic scalar multiplications
- LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE
- Regularity Conditions for Iterated Shuffle on Commutative Regular Languages
- On Presburger arithmetic extended with non-unary counting quantifiers
- Quantifier elimination for counting extensions of Presburger arithmetic
- Reasoning about reversal-bounded counter machines
- Exact complexity bounds for ordinal addition
- Artificial intelligence and inherent mathematical difficulty
- Two-way one-counter nets revisited
- An introduction to the theory of linear integer arithmetic (invited paper)
- The complexity of one-agent refinement modal logic
- The complexity of almost linear diophantine problems
- Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
- Deciding Boolean algebra with Presburger arithmetic
- A mathematical framework for the semantics of symbolic languages representing periodic time
- Computational complexity of logical theories of one successor and another unary function
- A uniform method for proving lower bounds on the computational complexity of logical theories
- Weak quantifier elimination for the full linear theory of the integers
- Proof synthesis and reflection for linear arithmetic
This page was built for publication: The complexity of logical theories
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1159661)
