20 found
Order:
  1.  18
    On the complexity of propositional knowledge base revision, updates, and counterfactuals.Thomas Eiter & Georg Gottlob - 1992 - Artificial Intelligence 57 (2-3):227-270.
  2.  10
    The price of query rewriting in ontology-based data access.Georg Gottlob, Stanislav Kikot, Roman Kontchakov, Vladimir Podolskii, Thomas Schwentick & Michael Zakharyaschev - 2014 - Artificial Intelligence 213 (C):42-59.
  3.  4
    Fixed-parameter complexity in AI and nonmonotonic reasoning.Georg Gottlob, Francesco Scarcello & Martha Sideri - 2002 - Artificial Intelligence 138 (1-2):55-86.
  4.  6
    A comparison of structural CSP decomposition methods.Georg Gottlob, Nicola Leone & Francesco Scarcello - 2000 - Artificial Intelligence 124 (2):243-282.
  5.  4
    Removing redundancy from a clause.Georg Gottlob & Christian G. Fermüller - 1993 - Artificial Intelligence 61 (2):263-289.
  6.  5
    Towards more expressive ontology languages: The query answering problem.Andrea Cali`, Georg Gottlob & Andreas Pieris - 2012 - Artificial Intelligence 193 (C):87-128.
  7.  4
    Bounded treewidth as a key to tractability of knowledge representation and reasoning.Georg Gottlob, Reinhard Pichler & Fang Wei - 2010 - Artificial Intelligence 174 (1):105-132.
  8.  5
    Semantics and complexity of abduction from default theories.Thomas Eiter, Georg Gottlob & Nicola Leone - 1997 - Artificial Intelligence 90 (1-2):177-223.
  9.  8
    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 (8 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  10.  7
    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 (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  11.  8
    On minimal constraint networks.Georg Gottlob - 2012 - Artificial Intelligence 191-192 (C):42-60.
  12.  5
    Enhancing model checking in verification by AI techniques.Francesco Buccafurri, Thomas Eiter, Georg Gottlob & Nicola Leone - 1999 - Artificial Intelligence 112 (1-2):57-104.
  13.  5
    An efficient method for eliminating varying predicates from a circumscription.Marco Cadoli, Thomas Eiter & Georg Gottlob - 1992 - Artificial Intelligence 54 (3):397-410.
  14.  3
    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 (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  15.  11
    Polynomial combined first-order rewritings for linear and guarded existential rules.Georg Gottlob, Marco Manna & Andreas Pieris - 2023 - Artificial Intelligence 321 (C):103936.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  16.  11
    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 (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  17.  17
    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  
     
    Bookmark  
  18.  4
    Cumulative default logic: Finite characterization, algorithms, and complexity.Georg Gottlob & Mingyi Zhang - 1994 - Artificial Intelligence 69 (1-2):329-345.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  19.  9
    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.
  20. Review of a Carnapian Extension of S5. [REVIEW]Georg Gottlob - 1999 - In E. Orłowska (ed.), Logic at Work. Heidelberg.
     
    Export citation  
     
    Bookmark   3 citations