7 found
Order:
  1.  6
    Relativized Logspace and Generalized Quantifiers Over Finite Ordered Structures.Georg Gottlob - 1997 - Journal of Symbolic Logic 62 (2):545-574.
    We here examine the expressive power of first order logic with generalized quantifiers over finite ordered structures. In particular, we address the following problem: Given a family Q of generalized quantifiers expressing a complexity class C, what is the expressive power of first order logic FO(Q) extended by the quantifiers in Q? From previously studied examples, one would expect that FO(Q) captures L C , i.e., logarithmic space relativized to an oracle in C. We show that this is not always (...)
    Direct download (7 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  2.  13
    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  
  3.  28
    Capturing Relativized Complexity Classes Without Order.Anuj Dawar, Georg Gottlob & Lauri Hella - 1998 - Mathematical Logic Quarterly 44 (1):109-122.
    We consider the problem of obtaining logical characterisations of oracle complexity classes. In particular, we consider the complexity classes LOGSPACENP and PTIMENP. For these classes, characterisations are known in terms of NP computable Lindström quantifiers which hold on ordered structures. We show that these characterisations are unlikely to extend to arbitrary structures, since this would imply the collapse of certain exponential complexity hierarchies. We also observe, however, that PTIMENP can be characterised in terms of Lindström quantifers , though it remains (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  4. Normal Forms for Second-Order Logic Over Finite Structures, and Classification of NP Optimization Problems.Thomas Eiter, Georg Gottlob & Yuri Gurevich - 1996 - Annals of Pure and Applied Logic 78 (1-3):111-125.
    We start with a simple proof of Leivant's normal form theorem for ∑11 formulas over finite successor structures. Then we use that normal form to prove the following:1. over all finite structures, every ∑21 formula is equivalent to a ∑21 formula whose first-order part is a Boolean combination of existential formulas, and2. over finite successor structures, the Kolaitis-Thakur hierarchy of minimization problems collapses completely and the Kolaitis-Thakur hierarchy of maximization problems collapses partially.The normal form theorem for ∑21 fails if ∑21 (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  5.  16
    On the Expressiveness of Frame Satisfiability and Fragments of Second-Order Logic.Thomas Eiter & Georg Gottlob - 1998 - Journal of Symbolic Logic 63 (1):73-82.
    It was conjectured by Halpern and Kapron (Annals of Pure and Applied Logic, vol. 69, 1994) that frame satisfiability of propositional modal formulas is incomparable in expressive power to both Σ 1 1 (Ackermann) and Σ 1 1 (Bernays-Schonfinkel). We prove this conjecture. Our results imply that Σ 1 1 (Ackermann) and Σ 1 1 (Bernays-Schonfinkel) are incomparable in expressive power, already on finite graphs. Moreover, we show that on ordered finite graphs, i.e., finite graphs with a successor, Σ 1 (...)
    Direct download (8 more)  
     
    Export citation  
     
    My bibliography  
  6.  1
    Third International Symposium on Foundations of Information and Knowledge Systems (Foiks 2004).Georg Gottlob, Yuri Gurevich, Dietmar Seipel & J. M. Turull-Torres - 2004 - Bulletin of Symbolic Logic 10 (4):596.
  7. Review of a Carnapian Extension of S5. [REVIEW]Georg Gottlob - 1999 - In E. Orłowska (ed.), Logic at Work. Heidelberg.
     
    Export citation  
     
    My bibliography