The computational complexity of logical theories

Cited in

(87)

Stationary logic of ordinals
On the complexity of theories of permutations
Nonconvergence, undecidability, and intractability in asymptotic problems
On the computational complexity of the theory of Abelian groups
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
On time-space classes and their relation to the theory of real addition
Complexity of logical theories involving coprimality
An efficient decision procedure for the theory of rational order
Complexity of Presburger arithmetic with fixed quantifier dimension
The complexity of query evaluation in indefinite temporal constraint databases
Ehrenfeucht games and ordinal addition
Fixed point characterization of infinite behavior of finite-state systems
Queries with arithmetical constraints
Skolem functions of arithmetical sentences.
Linear problems in valued fields
Circuit satisfiability and constraint satisfaction around Skolem arithmetic
Solving quantified linear arithmetic by counterexample-guided instantiation
Multitree automata that count
The complexity of the word problems for commutative semigroups and polynomial ideals
On iterating linear transformations over recognizable sets of integers
On the complexity of decision using destinies in \(H\)-bounded structures
Fast theorem-proving and Wu's method
Decidable \({\exists}^*{\forall}^*\) first-order fragments of linear rational arithmetic with uninterpreted predicates
NP satisfiability for arrays as powers
Short proofs for slow consistency
Emptiness problems for integer circuits
A complete and terminating approach to linear integer solving
Alternating complexity of counting first-order logic for the subword order
Sharpened lower bounds for cut elimination
Vaught's theorem on axiomatizability by a scheme
The quantifier complexity of polynomial-size iterated definitions in first-order logic
Double-exponential inseparability of Robinson subsystem \(Q_{+}\)
Circuit satisfiability and constraint satisfaction around Skolem arithmetic
Complexity of Subcases of Presburger Arithmetic
Upper Bounds on the Automata Size for Integer and Mixed Real and Integer Linear Arithmetic (Extended Abstract)
Halting and equivalence of program schemes in models of arbitrary theories
Effective Quantifier Elimination for Presburger Arithmetic with Infinity
Model Checking FO(R) over One-Counter Processes and beyond
Classifying the computational complexity of problems
Strong reducibilities
On decidable varieties of Heyting algebras
Locality and modular Ehrenfeucht-Fraïssé games
A small reflection principle for bounded arithmetic
The theory of integer multiplication with order restricted to primes is decidable
The second incompleteness theorem and bounded interpretations
An improved lower bound for the elementary theories of trees
Quantifier Elimination and Provers Integration
Climbing up the elementary complexity classes with theories of automatic structures
Complexity of counting first-order logic for the subword order
The Cayley-graph of the queue monoid: logic and decidability
Uniformly Automatic Classes of Finite Structures
Emptiness problems for integer circuits
Truth definition for _0 formulas and PSPACE computations
A Generalization of Semenov’s Theorem to Automata over Real Numbers
Model-theoretic methods in combined constraint satisfiability
VON NEUMANN’S CONSISTENCY PROOF
Diophantine equations, Presburger arithmetic and finite automata
Decidability of the theory of the natural integers with the Cantor pairing function and the successor
The most nonelementary theory
Algorithmic uses of the Feferman-Vaught theorem
Finitely axiomatized theories lack self‐comprehension
The theory of hereditarily bounded sets
On Presburger arithmetic extended with non-unary counting quantifiers
On algebraic array theories
On the bounded theories of finite trees
Succinct ordering and aggregation constraints in algebraic array theories
Knowledgebase transformations
A decision algorithm for linear sentences on a PFM
The unprovability of small inconsistency. A study of local and global interpretability
A closed-form evaluation for Datalog queries with integer (gap)-order constraints
The 1982 ACM Turing Award lecture. An overview of computational complexity
Logical aspects of Cayley-graphs: the group case
An introduction to the theory of linear integer arithmetic (invited paper)
The complexity of almost linear diophantine problems
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
New formally undecidable propositions: Non-trivial lower bounds on proof complexity and related theorems
Deciding Boolean algebra with Presburger arithmetic
Computational complexity of logical theories of one successor and another unary function
Quantifier elimination for the reals with a predicate for the powers of two
A uniform method for proving lower bounds on the computational complexity of logical theories
Definability with bounded number of bound variables
Pairs, sets and sequences in first-order theories
Weak quantifier elimination for the full linear theory of the integers

This page was built for publication: The computational complexity of logical theories

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