8 found
Sort by:
  1. Andrea Calı, Georg Gottlob, Michael Kifer, Thomas Lukasiewicz & Andreas Pieris (2010). Ontological Reasoning with F-Logic Lite and its Extensions. Complexity 2:2EXPTIME.
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  2. Georg Gottlob, Yuri Gurevich, Dietmar Seipel & J. M. Turull-Torres (2004). Third International Symposium on Foundations of Information and Knowledge Systems (Foiks 2004). Bulletin of Symbolic Logic 10 (4).
    Direct download  
     
    My bibliography  
     
    Export citation  
  3. Georg Gottlob (1999). Review of a Carnapian Extension of S5. [REVIEW] In E. Orłowska (ed.), Logic at Work. Heidelberg.
    No categories
     
    My bibliography  
     
    Export citation  
  4. Georg Gottlob, Nicola Leone & Helmut Veith (1999). Succinctness as a Source of Complexity in Logical Formalisms. Annals of Pure and Applied Logic 97 (1-3):231-260.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  5. Anuj Dawar, Georg Gottlob & Lauri Hella (1998). Capturing Relativized Complexity Classes Without Order. Mathematical Logic Quarterly 44 (1):109-122.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  6. Thomas Eiter & Georg Gottlob (1998). On the Expressiveness of Frame Satisfiability and Fragments of Second-Order Logic. 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 (6 more)  
     
    My bibliography  
     
    Export citation  
  7. Georg Gottlob (1997). Relativized Logspace and Generalized Quantifiers Over Finite Ordered Structures. 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 (6 more)  
     
    My bibliography  
     
    Export citation  
  8. Thomas Eiter, Georg Gottlob & Yuri Gurevich (1996). Normal Forms for Second-Order Logic Over Finite Structures, and Classification of NP Optimization Problems. Annals of Pure and Applied Logic 78 (1-3):111-125.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation