Order:
  1.  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 (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  2.  8
    16th Workshop on Logic, Language, Information and Computation (WoLLIC 2009).Hans Tompits, Ken Satoh, Arnold Beckmann, Carlos Caleiro, Thomas Eiter, Sylvain Salvati, Taisuke Sato & Frank Wolter - 2010 - Bulletin of Symbolic Logic 16 (1):805-815.
  3.  20
    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  
  4.  7
    Inconsistency Management for Traffic Regulations: Formalization and Complexity Results.Harald Beck, Thomas Eiter & Thomas Krennwallner - 2012 - In Luis Farinas del Cerro, Andreas Herzig & Jerome Mengin (eds.), Logics in Artificial Intelligence. Springer. pp. 80--93.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark  
  5.  5
    Undoing the Effects of Action Sequences.Thomas Eiter, Esra Erdem & Wolfgang Faber - 2008 - Journal of Applied Logic 6 (3):380-415.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  6.  4
    Model-Based Recasting in Answer-Set Programming.Thomas Eiter, Michael Fink, Jörg Pührer, Hans Tompits & Stefan Woltran - 2013 - Journal of Applied Non-Classical Logics 23 (1-2):75-104.
    As is well known, answer-set programs do not satisfy the replacement property in general, i.e., programs and that are equivalent may cease to be so when they are put in the context of some other program, i.e., and may have different answer sets. Lifschitz, Pearce, and Valverde thus introduced strong equivalence for context-independent equivalence, and proved that such equivalence holds between given programs and iff and are equivalent theories in the monotonic logic of here-and-there. In this article, we consider a (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  7.  2
    Preface.Thomas Eiter & Domenico Lembo - 2005 - Journal of Applied Logic 3 (2):251-252.