Citations of work:

Kevin J. Compton & C. Ward Henson (1990). A Uniform Method for Proving Lower Bounds on the Computational Complexity of Logical Theories.

10 found
Order:
Are we missing citations?

PhilPapers citations & references are currently in beta testing. We expect to add many more in the future.

Meanwhile, you can use our bibliography tool to import references for this or another work.

Or you can directly add citations for the above work:

  1.  2
    Double-Exponential Inseparability of Robinson Subsystem Q₊.Lavinia Egidi & Giovanni Faglia - 2011 - Journal of Symbolic Logic 76 (1):94 - 124.
    In this work a double exponential time inseparability result is proven for a finitely axiomatizable first order theory Q₊. The theory, subset of Presburger theory of addition S₊, is the additive fragment of Robinson system Q. We prove that every set that separates Q₊` from the logically false sentences of addition is not recognizable by any Turing machine working in double exponential time. The lower bound is given both in the non-deterministic and in the linear alternating time models. The result (...)
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  2.  1
    Automatic Structures of Bounded Degree Revisited.Dietrich Kuske & Markus Lohrey - 2011 - Journal of Symbolic Logic 76 (4):1352-1380.
    The first-order theory of a string automatic structure is known to be decidable, but there are examples of string automatic structures with nonelementary first-order theories. We prove that the first-order theory of a string automatic structure of bounded degree is decidable in doubly exponential space (for injective automatic presentations, this holds even uniformly). This result is shown to be optimal since we also present a string automatic structure of bounded degree whose first-order theory is hard for 2EXPSPACE. We prove similar (...)
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  3.  12
    First-Order and Counting Theories of Ω-Automatic Structures.Dietrich Kuske & Markus Lohrey - 2008 - Journal of Symbolic Logic 73 (1):129-150.
    The logic L (Qu) extends first-order logic by a generalized form of counting quantifiers ("the number of elements satisfying... belongs to the set C"). This logic is investigated for structures with an injectively ω-automatic presentation. If first-order logic is extended by an infinity-quantifier, the resulting theory of any such structure is known to be decidable [6]. It is shown that, as in the case of automatic structures [21], also modulo-counting quantifiers as well as infinite cardinality quantifiers ("there are χ many (...)
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  4.  2
    Non-Primitive Recursive Decidability of Products of Modal Logics with Expanding Domains.David Gabelaia, Agi Kurucz, Frank Wolter & Michael Zakharyaschev - 2006 - Annals of Pure and Applied Logic 142 (1):245-268.
    We show that—unlike products of ‘transitive’ modal logics which are usually undecidable—their ‘expanding domain’ relativisations can be decidable, though not in primitive recursive time. In particular, we prove the decidability and the finite expanding product model property of bimodal logics interpreted in two-dimensional structures where one component—call it the ‘flow of time’—is • a finite linear order or a finite transitive tree and the other is composed of structures like • transitive trees/partial orders/quasi-orders/linear orders or only finite such structures expanding (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  5.  3
    Algorithmic Uses of the Feferman–Vaught Theorem.J. A. Makowsky - 2004 - Annals of Pure and Applied Logic 126 (1-3):159-213.
    The classical Feferman–Vaught Theorem for First Order Logic explains how to compute the truth value of a first order sentence in a generalized product of first order structures by reducing this computation to the computation of truth values of other first order sentences in the factors and evaluation of a monadic second order sentence in the index structure. This technique was later extended by Läuchli, Shelah and Gurevich to monadic second order logic. The technique has wide applications in decidability and (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  6.  15
    Succinctness as a Source of Complexity in Logical Formalisms.Georg Gottlob, Nicola Leone & Helmut Veith - 1999 - Annals of Pure and Applied Logic 97 (1-3):231-260.
    The often observed complexity gap between the expressiveness of a logical formalism and its exponentially harder expression complexity is proven for all logical formalisms which satisfy natural closure conditions. The expression complexity of the prefix classes of second-order logic can thus be located in the corresponding classes of the weak exponential hierarchies; further results about expression complexity in database theory, logic programming, nonmonotonic reasoning, first-order logic with Henkin quantifiers and default logic are concluded. The proof method illustrates the significance of (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  7.  6
    Ehrenfeucht Games and Ordinal Addition.Françoise Maurin - 1997 - Annals of Pure and Applied Logic 89 (1):53-73.
    We show in this paper that the theory of ordinal addition of any fixed ordinal ωα, with α less than ωω, admits a quantifier elimination. This in particular gives a new proof for the decidability result first established in 1965 by R. Büchi using transfinite automata. Our proof is based on the Ehrenfeucht games, and we show that quantifier elimination go through generalized power.RésuméOn montre ici que, pour tout ordinal α inférieur à ωω, la théorie additive de ωα admet une (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  8.  20
    The Theory of Integer Multiplication with Order Restricted to Primes is Decidable.Françoise Maurin - 1997 - Journal of Symbolic Logic 62 (1):123-130.
    We show here that the first order theory of the positive integers equipped with multiplication remains decidable when one adds to the language the usual order restricted to the prime numbers. We see moreover that the complexity of the latter theory is a tower of exponentials, of height O(n).
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography  
  9.  18
    Definability and Decidability Issues in Extensions of the Integers with the Divisibility Predicate.Patrick Cegielski, Yuri Matiyasevich & Denis Richard - 1996 - Journal of Symbolic Logic 61 (2):515-540.
    Let M be a first-order structure; we denote by DEF(M) the set of all first-order definable relations and functions within M. Let π be any one-to-one function from N into the set of prime integers. Let ∣ and $\bullet$ be respectively the divisibility relation and multiplication as function. We show that the sets DEF(N,π,∣) and $\mathrm{DEF}(\mathbb{N},\pi,\bullet)$ are equal. However there exists function π such that the set DEF(N,π,∣), or, equivalently, $\mathrm{DEF}(\mathbb{N},\pi,\bullet)$ is not equal to $\mathrm{DEF}(\mathbb{N},+,\bullet)$ . Nevertheless, in all cases (...)
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography  
  10.  2
    Dominoes and the Complexity of Subclasses of Logical Theories.Erich Grädel - 1989 - Annals of Pure and Applied Logic 43 (1):1-30.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   2 citations