13 found
Order:
  1.  18
    The Complexity of First-Order and Monadic Second-Order Logic Revisited.Markus Frick & Martin Grohe - 2004 - Annals of Pure and Applied Logic 130 (1-3):3-31.
    The model-checking problem for a logic L on a class C of structures asks whether a given L-sentence holds in a given structure in C. In this paper, we give super-exponential lower bounds for fixed-parameter tractable model-checking problems for first-order and monadic second-order logic. We show that unless PTIME=NP, the model-checking problem for monadic second-order logic on finite words is not solvable in time f·p, for any elementary function f and any polynomial p. Here k denotes the size of the (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  2.  5
    Arity Hierarchies.Martin Grohe - 1996 - Annals of Pure and Applied Logic 82 (2):103-163.
    Many logics considered in finite model theory have a natural notion of an arity. The purpose of this article is to study the hierarchies which are formed by the fragments of such logics whose formulae are of bounded arity.Based on a construction of finite graphs with a certain property of homogeneity, we develop a method that allows us to prove that the arity hierarchies are strict for several logics, including fixed-point logics, transitive closure logic and its deterministic version, variants of (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  3. Zur Struktur dessen, was wirklich berechenbar ist.H. -D. Ebbinghaus & Martin Grohe - 1999 - Philosophia Naturalis 36 (1):91-116.
    No categories
    Translate
     
     
    Export citation  
     
    Bookmark  
  4.  38
    An Analysis of the W -Hierarchy.Yijia Chen, Jörg Flum & Martin Grohe - 2007 - Journal of Symbolic Logic 72 (2):513 - 534.
    We observe that the W*-hierarchy, a variant (introduced by Downey, Fellows, and Taylor [7]) of the better known W-hierarchy, coincides with the W-hierarchy, though not level wise, but just as a whole hierarchy. More precisely, we prove that W[t] ⊆ W*[t] ⊆ W[2t − 2] for each t ≥ 2. It was known before that W[1] = W*[1] and W[2] = W*[2]. Our second main result is a new logical characterization of the W*-hierarchy in terms of "Fagin-definable problems." As a (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  5.  21
    A Double Arity Hierarchy Theorem for Transitive Closure Logic.Martin Grohe & Lauri Hella - 1996 - Archive for Mathematical Logic 35 (3):157-171.
    In this paper we prove that thek-ary fragment of transitive closure logic is not contained in the extension of the (k−1)-ary fragment of partial fixed point logic by all (2k−1)-ary generalized quantifiers. As a consequence, the arity hierarchies of all the familiar forms of fixed point logic are strict simultaneously with respect to the arity of the induction predicates and the arity of generalized quantifiers.Although it is known that our theorem cannot be extended to the sublogic deterministic transitive closure logic, (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  6. 2003 European Summer Meeting of the Association for Symbolic Logic Logic Colloquim'03.Michael Benedikt, Stevo Todorcevic, Alexandru Baltag, Howard Becker, Matthew Foreman, Jean-Yves Girard, Martin Grohe, Peter T. Johnstone, Simo Knuuttila & Menachem Kojman - 2004 - Bulletin of Symbolic Logic 10 (2).
  7.  7
    Bounded Fixed-Parameter Tractability and Reducibility.Rod Downey, Jörg Flum, Martin Grohe & Mark Weyer - 2007 - Annals of Pure and Applied Logic 148 (1):1-19.
    We study a refined framework of parameterized complexity theory where the parameter dependence of fixed-parameter tractable algorithms is not arbitrary, but restricted by a function in some family . For every family of functions, this yields a notion of -fixed-parameter tractability. If is the class of all polynomially bounded functions, then -fixed-parameter tractability coincides with polynomial time decidability and if is the class of all computable functions, -fixed-parameter tractability coincides with the standard notion of fixed-parameter tractability. There are interesting choices (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  8.  22
    Complete Problems for Fixed-Point Logics.Martin Grohe - 1995 - Journal of Symbolic Logic 60 (2):517-527.
    Direct download (11 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  9.  39
    On Fixed-Point Logic with Counting.Jörg Flum & Martin Grohe - 2000 - Journal of Symbolic Logic 65 (2):777-787.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  10.  18
    Some Remarks on Finite Löwenheim‐Skolem Theorems.Martin Grohe - 1996 - Mathematical Logic Quarterly 42 (1):569-571.
    We discuss several possible extensions of the classical Löwenheim-Skolem Theorem to finite structures and give a counterexample refuting almost all of them.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  11.  9
    An Existential Locality Theorem.Martin Grohe & Stefan Wöhrle - 2004 - Annals of Pure and Applied Logic 129 (1-3):131-148.
    We prove an existential version of Gaifman's locality theorem and show how it can be applied algorithmically to evaluate existential first-order sentences in finite structures.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  12.  21
    Finite Variable Logics in Descriptive Complexity Theory.Martin Grohe - 1998 - Bulletin of Symbolic Logic 4 (4):345-398.
  13.  1
    Pebble Games and Linear Equations.Martin Grohe & Martin Otto - 2015 - Journal of Symbolic Logic 80 (3):797-844.