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.
    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)  
     
    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.
    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 (...)
    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.
    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)  
     
    My bibliography  
     
    Export citation