The complexity of logical theories
From MaRDI portal
Publication:1159661
DOI10.1016/0304-3975(80)90037-7zbMath0475.03017OpenAlexW1975885036WikidataQ56059276 ScholiaQ56059276MaRDI QIDQ1159661
Publication date: 1980
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(80)90037-7
upper and lower boundsPresburger arithmeticcomplexity measurealternationsencoding computations of alternating Turing machinestheory of reals with additiontime versus space problem
Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)
Related Items
Erratum to: ``Analyzing restricted fragments of the theory of linear arithmetic, On the complexity of theories of permutations, Equivalence Between Model-Checking Flat Counter Systems and Presburger Arithmetic, SAFE RECURSIVE SET FUNCTIONS, The complexity of elementary algebra and geometry, Presburger arithmetic with unary predicates is Π11 complete, Equivalence between model-checking flat counter systems and Presburger arithmetic, The complexity of linear problems in fields, A bibliography of quantifier elimination for real closed fields, Complexity of Presburger arithmetic with fixed quantifier dimension, Deciding Boolean algebra with Presburger arithmetic, A mathematical framework for the semantics of symbolic languages representing periodic time, The complexity of query evaluation in indefinite temporal constraint databases, Automata-theoretical regularity characterizations for the iterated shuffle on commutative regular languages, Subclasses of Presburger arithmetic and the polynomial-time hierarchy, Dominoes and the complexity of subclasses of logical theories, Computational complexity of logical theories of one successor and another unary function, A canonical form of vector machines, Emptiness problems for integer circuits, On the complexity of quantified linear systems, Solving quantified linear arithmetic by counterexample-guided instantiation, Regularity Conditions for Iterated Shuffle on Commutative Regular Languages, Complexity, convexity and combinations of theories, More about Exact Slow $k$-Nim, Well-abstracted transition systems: Application to FIFO automata., On Presburger arithmetic extended with non-unary counting quantifiers, Alternating complexity of counting first-order logic for the subword order, Quantifier elimination for counting extensions of Presburger arithmetic, Classifying the computational complexity of problems, On time-space classes and their relation to the theory of real addition, WORD EQUATIONS OVER GRAPH PRODUCTS, The complexity of Presburger arithmetic with bounded quantifier alternation depth, A uniform method for proving lower bounds on the computational complexity of logical theories, On the complexity of team logic and its two-variable fragment, Exact complexity bounds for ordinal addition, Weak quantifier elimination for the full linear theory of the integers, Proof synthesis and reflection for linear arithmetic, Analyzing restricted fragments of the theory of linear arithmetic, Complexity of logical theories involving coprimality, Unnamed Item, The role of rudimentary relations in complexity theory, The complexity of verifying population protocols, Unnamed Item, The complexity of one-agent refinement modal logic, Double-exponential inseparability of Robinson subsystem Q+, Colors Make Theories Hard, 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, LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE, Probabilistic game automata, Model-Checking Counting Temporal Logics on Flat Structures, Linear problems in valued fields, Unnamed Item, Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories, Real addition and the polynomial hierarchy, Real computations with fake numbers
Cites Work
