Riccardo Rosati, Georg Gottlob
We analyze the asymptotic conditional validity of modal formulas, i.e., the probability that a formula ψ is valid in the finite Kripke structures in which a given modal formula ϕ is valid, when the...
Taming the Infinite Chase: Query Answering under Expressive Relational Constraints (2009)
Andrea Calì, Georg Gottlob, Michael Kifer
Answering queries posed over knowledge bases is a central problem in knowledge representation and database theory. In databases, query containment is one of the important query optimization and...
DLV: An Advanced System for Knowledge Representation and Reasoning (2009)
Nicola Leone, Wolfgang Faber, Gerald Pfeifer, Annamaria Bria, Francesco Calimeri, Gelsomina Catalano, ...
DLV [5] is a KRR system which is based on Disjunctive Logic Programming (DLP) [6] under the stable model semantics (also called Answer Set Programming) [4]. Roughly, a DLP program is a set of...
We consider the computation of eigenvectors x = (x1,..., xn) over the integers, where each component xi satisfies |xi | ≤ b for an integer b. We address various problems in this context, and...
Generalized Hypertree Decompositions: NP-hardness and Tractable Variants (2009)
Gottlob, Georg, Miklos, Zoltan, Schwentick, Thomas
The generalized hypertree width GHW(H) of a hypergraph H is a measure of its cyclicity. Classes of conjunctive queries or constraint satisfaction problems whose associated hypergraphs have bounded...
Tree Projections: Game Characterization and Computational Aspects (2009)
Gottlob, Georg, Greco, Gianluici, Miklos, Zoltan, Scarcello, Francesco, Schwentick, Thomas, Lipshteyn, Marina, ...
The notion of tree projection provides a natural generalization for various structural decomposition methods, which have been proposed in the literature in order to single out classes of...
Abiteboul, Serge, Gottlob, Georg, Manna, Marco
A distributed XML document is an XML document that spans several machines or Web repositories. We assume that a distribution design of the document tree is given, providing an XML tree some of whose...
Abiteboul, Serge, Gottlob, Georg, Manna, Marco
A distributed XML document is an XML document that spans several machines or Web repositories. We assume that a distribution design of the document tree is given, providing an XML tree some of whose...
Personalized Portal for REWERSE (2008)
Reviewers Ingo Brunkhorst, Uta Schwertel, Nicola Henze, Robert Baumgartner, Tim Geisler, Georg Gottlob, ...
This reports documents the achievement of working group A3- “Personalized Information Systems” to design and develop a Personalized Portal for REWERSE. We have collected scenarios for a...
Jürgen Dix, Georg Gottlob, V. Wiktor Marek, Cecylia Rauszer
as STABLE and SUPPORTED (both are co-NP-complete) as well as Msupp
Monadic Datalog over Finite Structures with Bounded Treewidth (2008)
Gottlob, Georg, Pichler, Reinhard, Wei, Fang
Bounded treewidth and Monadic Second Order (MSO) logic have proved to be key concepts in establishing fixed-parameter tractability results. Indeed, by Courcelle's Theorem we know: Any property of...
ABSTRACT Conjunctive Queries over Trees ∗ (2008)
Georg Gottlob, Christoph Koch, Dbai Tu Wien
We study the complexity and expressive power of conjunctive queries over unranked labeled trees, where the tree structures are represented using “axis relations ” such as “child”,...
Georg Gottlob, Gianluigi Greco, Francesco Scarcello
In this paper we investigate complexity issues related to pure Nash equilibria of strategic games. We show that, even in very restrictive settings, determining whether a game has a pure Nash...
The Lixto systems applications in Business Intelligence and Semantic Web (2008)
Robert Baumgartner, Oliver Frölich, Georg Gottlob, Tu Wien
Abstract: This paper shows how technologies for Web data extraction, syndication and integration allow for new applications and services in the Business Intelligence and the Semantic Web domain....
ABSTRACT The Complexity of XPath Query Evaluation (2008)
In this paper, we study the precise complexity of XPath 1.0 query processing. Even though heavily used by its incorporation into a variety of XML-related standards, the precise cost of evaluating an...
The Personal Publication Reader (2008)
Fabian Abel, Robert Baumgartner, Georg Gottlob, Nicola Henze, Marcus Herzog, Matthias Kriesell, ...
Abstract. This application demonstrates how to provide personalized, syndicated views on distributed web data using Semantic Web technologies. The application comprises four steps: The information...
ABSTRACT Monadic Datalog over Finite Structures with Bounded Treewidth (2008)
Bounded treewidth and Monadic Second Order (MSO) logic have proved to be key concepts in establishing fixed-parameter tractability results. Indeed, by Courcelle’s Theorem we know: Any property of...
Georg Gottlob, Zoltán Miklós, Thomas Schwentick, Lehrstuhl Informatik I
comlab.ox.ac.uk The generalized hypertree width GHW (H) of a hypergraph H is a measure of its cyclicity. Classes of conjunctive queries or constraint satisfaction problems whose associated...
Management]: Languages—query languages (2008)
Evgeny Dantsin, Thomas Eiter, Georg Gottlob, Andrei Voronkov
This article surveys various complexity and expressiveness results on different forms of logic programming. The main focus is on decidable forms of logic programming, in particular, propositional...
Georg Gottlob, Mgr Michal Ceresna
HTML Wrapping ist eine häufig gebrauchte Strategie für den Zugriff und die Extraktion von Daten, die sich im World Wide Web befinden. HTML Wrapper lokalisieren die relevanten Daten in den Webseiten...
Some recent advances in the identification of tractable classes of combinatorial auctions are discussed. In particular, the work of [Gottlob and Greco 2007] is illustrated, where a research question...
ABSTRACT The Lixto Data Extraction Project – Back and Forth between Theory and Practice (2008)
Georg Gottlob, Christoph Koch, Robert Baumgartner, Marcus Herzog, Dbai Tu Wien, Sergio Flesca
We present the Lixto project, which is both a research project in database theory and a commercial enterprise that develops Web data extraction (wrapping) and Web service definition software. We...
Conditional Constraint Satisfaction: Logical Foundations and Complexity (2008)
Georg Gottlob, Gianluigi Greco, Toni Mancini
Conditional Constraint Satisfaction Problems (CC-SPs) are generalizations of classical CSPs that support conditional activation of variables and constraints. Despite the interest emerged for CCSPs in...
Table of Contents Foundations of Rule-Based Query Answering........................ 1 (2008)
François Bry, Norbert Eisinger, Thomas Eiter, Tim Furche, Georg Gottlob, Clemens Ley, ...
Oracle File System Translator (2008)
Simona Citrigno, Thomas Eiter, Wolfgang Faber, Georg Gottlob, Christoph Koch, Nicola Leone, ...
During the last years, much research has been done concerning semantics and complexity of Disjunctive Deductive Databases (DDDBs). While DDDBs — function-free disjunctive logic programs with...
ABSTRACT Visual Web Information Extraction with Lixto ∗ (2008)
Robert Baumgartner, Sergio Flesca, Georg Gottlob
We present new techniques for supervised wrapper generation and automated web information extraction, and a system called Lixto implementing these techniques [6]. Our system can generate wrappers...
by Deutsche Forschungsgemeinschaft (DFG). Some of the results in the present paper have appeared without full proof in the shorter workshop paper [Gottlob et al. 2000]. Permission to make...
Gottlob, Georg, Szeider, Stefan
We survey the parameterized complexity of problems that arise in artificial intelligence, database theory and automated reasoning. In particular, we consider various parameterizations of the...
Width Parameters Beyond Tree-width and their Applications (2008)
Hlineny, Petr, Oum, Sang-il, Seese, Detlef, Gottlob, Georg
Besides the very successful concept of tree-width (see [Bodlaender, H. and Koster, A. (2007) Combinatorial optimisation on graphs of bounded treewidth. These are special issues on Parameterized...
On the Weak mod m Representation of Boolean Functions (2007)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
one article at a time in L ATEX source form on the Internet. Pagination
Georg Gottlob, Sherry Marcus, Anil Nerode, V. S. Subrahmanian
The declarative semantics of nonmonotonic logic programming has largely been based on propositional programs. However, the ground instantiation of a logic program may be very large, and likewise, a...
Jurgen Dix, Georg Gottlob, Wiktor Marek
Abstract. It is wellknown that Minker's semantics GCWA for positive disjunctive programs P is \Pi P 2-complete, i.e. to decide if a literal is true in all minimal models of P. This is in...
Complexity Results Eigenvector, Yuri Gurevich, Thomas Eiter, Thomas Eiter, Thomas Eiter, ...
logic over strings. Journal of the ACM, 47(1):77-131, 2000.
In this paper we show that Datalog is well-suited as a temporal verification language. Datalog is a well-known database query language relying on the logic programming paradigm. We introduce Datalog...
THE DLV SYSTEM FOR KNOWLEDGE REPRESENTATION AND REASONING (2007)
Abtg Wissensbasierte Systeme, Georg Gottlob, Christoph Koch, Cristinel Mateis, Simona Perri, Francesco Scarcello, ...
2
Datalog LITE: a deductive query language with linear time model checking (2007)
Georg Gottlob, Erich Gr Adel, Rwth Aachen
We present Datalog LITE, a new deductive query language with a linear time model checking algorithm, i.e., linear time data complexity and program complexity. Datalog LITE is a variant of Datalog...
Reinhard Pichler, Hypergraphs Acyclicity, Nicola Leone, Francesco Buccafurri, Thomas Eiter, Georg Gottlob, ...
ACTL formulas having linear counterexamples. JCSS, 62(3):463-515, 2001.
NEW RESULTS ON MONOTONE DUALIZATION AND GENERATING HYPERGRAPH TRANSVERSALS (2007)
Abtg Wissensbasierte Systeme, Hypergraph Transversals, Kazuhisa Makino, Thomas Eiter, Thomas Eiter, Georg Gottlob, ...
2 and Kazuhisa Makino 3 Abstract. We consider the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph), whose associated decision problem is a...
COMPLEXITY OF NESTED CIRCUMSCRIPTION AND NESTED ABNORMALITY THEORIES (2007)
Abtg Wissensbasierte Systeme, Marco Cadoli, Marco Cadoli, Thomas Eiter, Thomas Eiter, Georg Gottlob, ...
www.kr.tuwien.ac.at
Journal of the ACM, to appear. Existential Second-Order Logic over Strings (2007)
Thomas Eiter, Georg Gottlob, Yuri Gurevich
Existential second-order logic (ESO) and monadic second-order logic (MSO) have attracted much interest in logic and computer science. ESO is a much more expressive logic over successor structures...
Francesco Buccafurri, Thomas Eiter, Georg Gottlob, Nicola Leone
In case an ACTL formula fails over a transition graph M, it is most useful to provide a counterexample, i.e., a computation tree of M witnessing the failure. If there exists a single path in M which...
Database and Artificial (2007)
Monadic query languages over trees currently receive considerable interest in the database community, as the problem of selecting nodes from a tree is the most basic and widespread database query...
Complexity of Nested Circumscription and Abnormality Theories (2007)
Marco Cadoli, Thomas Eiter, Georg Gottlob
We propose L Circ, an extension of circumscription by allowing propositional combinations and nesting of circumscriptive theories. As shown, Lifschitz 's nested abnormality theories (NATs,...
Evgeny Dantsin, Thomas Eiter, Georg Gottlob, Andrei Voronkov
This paper surveys various complexity results on different forms of logic programming. The main focus is on decidable forms of logic programming, in particular, propositional logic programming and...
This paper addresses complexity issues for important problems arising with disjunctive logic programming. In particular, the complexity of deciding whether a disjunctive logic program is consistent...
ABSTRACT Visual Web Information Extraction with Lixto ∗ (2007)
Robert Baumgartner, Sergio Flesca, Georg Gottlob
We present new techniques for supervised wrapper generation and automated web information extraction, and a system called Lixto implementing these techniques [6]. Our system can generate wrappers...
Chapter 1 LINEAR TIME DATALOG AND BRANCHING TIME LOGIC (2007)
Georg Gottlob, Erich Gradel, Helmut Veith
Abstract We survey recent results about the relation between Datalog and temporal verification logics. Datalog is a well-known database query language relying on the logic programming paradigm. We...
We consider the computation of eigenvectors x = (x 1; : : : ; xn) over the integers, where each component x i satisfies jx i j b for an integer b. We address various problems in this context, and...
IOS Press Well-Founded Semantics for Default Logic (2007)
Abstract. Default logic is one of the most popular approaches to model defeasible reasoning. Nevertheless, there are a number of problems with Reiter's original semantics that have led to the...
Georg Gottlob, Francesco Scarcello, Martha Sideri
Abstract This paper studies the fixed-parameter complexity of various problems in AI and nonmonotonic reasoning. We show that a number of relevant parameterized problems in these areas are...
COMPLEXITY AND EXPRESSIVE POWER OF LOGIC PROGRAMMING (2007)
Abtg Wissensbasierte Systeme, Georg Gottlob, Thomas Eiter, Andrei Voronkov, Evgeny Dantsin, Evgeny Dantsin
1 Thomas Eiter, 2 Georg Gottlob, 3 Andrei Voronkov 4 Abstract. This paper surveys various complexity and expressiveness results on different forms of logic programming. The main focus is on decidable...
ON ACTL FORMULAS HAVING DETERMINISTIC COUNTEREXAMPLES (2007)
Abtg Wissensbasierte Systeme, Georg Gottlob, Nicola Leone, Francesco Buccafurri, Francesco Buccafurri, Thomas Eiter, ...
3 Nicola Leone 3 Abstract. In case an ACTL formula OE fails over a labeled transition graph M, it is most useful to provide a counterexample, i.e., a computation tree of M witnessing the failure. If...
Logic-based Web Information Extraction (2007)
this article. Therefore, a wrapper is assumed to extract relevant data from a possibly poorly structured source and to put it into the desired representation formalism by applying a number of...
ABSTRACT The Complexity of XPath Query Evaluation (2007)
In this paper, we study the precise complexity of XPath 1.0 query processing. Even though heavily used by its incorporation into a variety of XML-related standards, the precise cost of evaluating an...
ABSTRACT Conjunctive Queries over Trees ∗ (2007)
Georg Gottlob, Christoph Koch, Dbai Tu Wien
We study the complexity and expressive power of conjunctive queries over unranked labeled trees, where the tree structures are represented using “axis relations ” such as “child”,...
ABSTRACT The Lixto Data Extraction Project – Back and Forth between Theory and Practice (2007)
Georg Gottlob, Christoph Koch, Robert Baumgartner, Marcus Herzog, Dbai Tu Wien, Sergio Flesca
We present the Lixto project, which is both a research project in database theory and a commercial enterprise that develops Web data extraction (wrapping) and Web service definition software. We...
A Backtracking-Based Algorithm for Computing Hypertree-Decompositions (2007)
Hypertree decompositions of hypergraphs are a generalization of tree decompositions of graphs. The corresponding hypertree-width is a measure for the cyclicity and therefore tractability of the...
Width parameters beyond tree-width and their applications (2007)
Petr Hliněny, Sang-il Oum, Detlef Seese, Georg Gottlob
Besides the very successful concept of tree-width (see [Bodlaender, H. and Koster, A. (2007) Combinatorial optimisation on graphs of bounded treewidth. These are special issues on Parameterized...
Foundations of rule-based query answering (2007)
François Bry, Norbert Eisinger, Thomas Eiter, Tim Furche, Georg Gottlob, Clemens Ley, ...
Abstract. This survey article introduces into the essential concepts and methods underlying rule-based query languages. It covers four complementary areas: declarative semantics based on adaptations...
Foundations of rule-based query answering (2007)
François Bry, Tim Furche, Georg Gottlob, Benedikt Linse, Reinhard Pichler, Fang Wei
Abstract. This survey article introduces into the essential concepts and methods underlying rule-based query languages. It covers four complementary areas: declarative semantics based on adaptations...
doi:10.1093/comjnl/bxm056 Fixed-Parameter Algorithms For Artificial Intelligence, Constraint (2007)
We survey the parameterized complexity of problems that arise in artificial intelligence, database theory and automated reasoning. In particular, we consider various parameterizations of the...
Heuristic Methods for Hypertree Decompositions (2007)
Artan Dermaku, Tobias Ganzow, Georg Gottlob, Benjamin McMahan, Nysret Musliu, Marko Samer
In this paper we propose new algorithms for generating generalized hypertree decompositions. The well known heuristics for generating tree decompositions based on vertex ordering have been extended...
T.: Complexity of pure equilibria in bayesian games (2007)
Georg Gottlob, Gianluigi Greco, Toni Mancini
In this paper we make a comprehensive study of the complexity of the problem of deciding the existence of equilibria in strategic games with incomplete information, in case of pure strategies. In...
The Logic behind Weighted CSP (2006)
Thomas Schiex, Cyril Terrioux, Stefano Bistarelli, Hélène Fargier, Georg Gottlob, Javier Larrosa, ...
Soft 2006 is already the eighth International Workshop on Preferences and Soft Constraints, held in conjunction with CP. This year, the usual topics of the workshop have been extended to graph...
Width Parameters Beyond Tree-width and Their Applications (2006)
Besides the successful concept of tree-width (see [H. Bodlaender, A. Koster: Combinatorial optimisation on graphs of bounded treewidth, ***** * this survey volume ******, 14 p.]) in the past years,...
Hypertree Width and Related Hypergraph Invariants (2006)
Isolde Adler, Georg Gottlob, Martin Grohe
We study the notion of hypertree width of hypergraphs. We prove that, up to a constant factor, hypertree width is the same as a number of other hypergraph invariants that resemble graph invariants...
COMPUTATIONAL ASPECTS OF MONOTONE DUALIZATION: A BRIEF SURVEY (2006)
Ab Wissensbasierte Systeme, Thomas Eiter, Kazuhisa Makino, Georg Gottlob, Thomas Eiter, Kazuhisa Makino, ...
Abstract.Dualization of a monotone Boolean function represented by a conjunctive normal form (CNF) is a problem which, in different disguise, is ubiquitous in many areas including Computer Science,...
G.: RDF Querying: Language Constructs and Evaluation Methods Compared (2006)
Tim Furche, Benedikt Linse, François Bry, Dimitris Plexousakis, Georg Gottlob
Abstract. This article is firstly an introduction into query languages for the Semantic Web, secondly an in-depth comparison of the languages introduced. Only RDF query languages are considered...
Hypertree Width and Related Hypergraph Invariants (2006)
Isolde Adler, Georg Gottlob, Martin Grohe
We study the notion of hypertree width of hypergraphs. We prove that, up to a constant factor, hypertree width is the same as a number of other hypergraph invariants that resemble graph invariants...
Bounded Treewidth as a Key to Tractability of Knowledge Representation and Reasoning (2006)
Georg Gottlob, Reinhard Pichler, Fang Wei
Several forms of reasoning in AI – like abduction, closed world reasoning, circumscription, and disjunctive logic programming – are well known to be intractable. In fact, many of the relevant...
Data exchange: Computing cores in polynomial time (2006)
Data exchange deals with inserting data from one database into another database having a different schema. We study and solve a central computational problem of data exchange, namely, computing the...
The Lixto Project: Exploring New Frontiers of Web Data Extraction (2006)
Julien Carme, Michal Ceresna, Oliver Frölich, Georg Gottlob, Marcus Herzog, Wolfgang Holzinger, ...
Abstract. The Lixto project is an ongoing research effort in the area of Web data extraction. Whereas the project originally started out with the idea to develop a logic-based extraction language and...
The complexity of quantified constraint satisfaction problems under structural restrictions (2005)
Georg Gottlob, Gianluigi Greco, Francesco Scarcello
We give a clear picture of the tractability/intractability frontier for quantified constraint satisfaction problems (QCSPs) under structural restrictions. On the negative side, we prove that checking...
The Personal Publication Reader (2005)
Fabian Abel Robert, Robert Baumgartner, Adrian Brooks, Christian Enzi, Georg Gottlob, Nicola Henze, ...
This application demonstrates how to provide personalized, syndicated views on distributed web data using Semantic Web technologies. The application comprises four steps: The information gathering...
REASONING UNDER MINIMAL UPPER BOUNDS IN PROPOSITIONAL LOGIC (2005)
Ab Wissensbasierte Systeme, Thomas Eiter, Georg Gottlob, Thomas Eiter, Georg Gottlob
Abstract. Reasoning from the minimal models of a theory, as fostered by circumscription, is in the area of Artificial Intelligence an important method to formalize common sense reasoning. However, as...
Web data extraction for business intelligence: the lixto approach (2005)
Robert Baumgartner, Oliver Frölich, Georg Gottlob, Patrick Harz, Marcus Herzog, Peter Lehmann, ...
Abstract: Knowledge about market developments and competitor activities on the market becomes more and more a critical success factor for enterprises. The World Wide Web provides public domain...
Hypertree decompositions: Structure, algorithms, and applications (2005)
Georg Gottlob, Martin Grohe, Nysret Musliu, Marko Samer, Francesco Scarcello
Abstract We review the concepts of hypertree decomposition and hypertree width from a graph theoretical perspective and report on a number of recent results related to these concepts. We also show...
The infomix system for advanced integration of incomplete and inconsistent data (2005)
Nicola Leone, Gianluigi Greco, Giovambattista Ianni, Vincenzino Lio, Giorgio Terracina, Thomas Eiter, ...
The task of an information integration system is to combine data residing at different sources, providing the user with a unified view of them, called global schema. Users formulate queries over the...
Hypertree-Width and Related Hypergraph Invariants (2005)
Isolde Adler, Georg Gottlob, Martin Grohe
We study the notion of hypertree-width of hypergraphs. We prove that, up to a constant factor, hypertree-width is the same as a number of other hypergraph invariants that resemble graph invariants...
The Complexity of XPath Query Evaluation and XML Typing (2005)
Georg Gottlob, Christoph Koch, Reinhard Pichler
We study the complexity of two central XML processing problems. The first is XPath 1.0 query processing, which has been shown to be in PTime in previous work. We prove that both the data complexity...
Annotating the Legacy Web with Lixto (2004)
Robert Baumgartner, Georg Gottlob, Marcus Herzog, Wolfgang Slany
The Semantic Web is still a vision. The unstructured Web of today contains millions of documents which cannot be queried and where layout and structure are heavily mixed. Moreover, they are not...
Conjunctive Queries over Trees (2004)
Georg Gottlob, Christoph Koch, Klaus U. Schulz
We study the complexity and expressive power of conjunctive queries over unranked labeled trees represented using a variety of structure relations such as “child”, “descendant”, and...
Grouped processing of relational algebra expressions over data streams (2004)
Getta, Janusz, Vossough, Ehsan, Benczúr, A. (Andras), Demetrovics, János, Gottlob, Georg
Implementation of the data stream processing applications requires a method for formal specification of the computations at a dataflow level. The logical models of stream processing hide the lower...
XPath processing in a nutshell (2003)
Georg Gottlob, Christoph Koch, Reinhard Pichler
We provide a concise yet complete formal definition of the semantics of XPath 1 and summarize efficient algorithms for processing queries in this language. Our presentation is intended both for the...
XPath query evaluation: improving time and space efficiency (2003)
Contemporary XPath query engines evaluate queries in time exponential in the sizes of input queries, a fact that has gone unnoticed for a long time. Recently, the first mainmemory evaluation...
Monadic Datalog and the Expressive Power of Languages for Web Information Extraction (2003)
Devices]: Automata; F.4.1 [Mathematical Logic and Formal Languages]: Computational Logic; F.4.3 [Math- ematical Logic and Formal Languages]: Classes defined by grammars or automata; H.2.3 [Database...
XPath Processing in a Nutshell (2003)
Georg Gottlob, Christoph Koch, Reinhard Pichler
We provide a concise yet complete formal definition of the semantics of XPath 1 and summarize efficient algorithms for processing queries in this language. Our presentation is intended both for the...
Pure Nash equilibria: hard and easy games (2003)
Georg Gottlob, Gianluigi Greco, Francesco Scarcello
We investigate complexity issues related to pure Nash equilibria of strategic games. We show that, even in very restrictive settings, determining whether a game has a pure Nash Equilibrium is...
The DLV System for Knowledge Representation and Reasoning (2002)
Nicola Leone, Gerald Pfeifer, Wolfgang Faber, Thomas Eiter, Georg Gottlob, Simona Perri, ...
Disjunctive Logic Programming (DLP) is an advanced formalism for knowledge representation and reasoning, which is very expressive in a precise mathematical sense: it allows to express every property...
Efficient algorithms for processing XPath queries (2002)
Georg Gottlob, Christoph Koch, Reinhard Pichler
Our experimental analysis of several popular XPath processors reveals a striking fact: Query evaluation in each of the systems requires time exponential in the size of queries in the worst case. We...
Efficient algorithms for processing XPath queries (2002)
Georg Gottlob, Christoph Koch, Reinhard Pichler
Our experimental analysis of several popular XPath processors reveals a striking fact: Query evaluation in each of the systems requires time exponential in the size of queries in the worst case. We...
New results on monotone dualization and generating hypergraph transversals (2002)
Thomas Eiter, Georg Gottlob, Kazuhisa Makino
We consider the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph), whose associated decision problem is a prominent open problem in...
Efficient algorithms for processing XPath queries (2002)
Georg Gottlob, Christoph Koch, Reinhard Pichler
Our experimental analysis of several popular XPath processors reveals a striking fact: Query evaluation in each of the systems requires time exponential in the size of queries in the worst case. We...
Monadic Datalog and the Expressive Power of Languages for Web Information Extraction (2002)
Research on information extraction from Web pages (wrapping) has seen much activity in recent times (particularly systems implementations), but little work has been done on formally studying the...
New results on monotone dualization and generating hypergraph transversals (2002)
Thomas Eiter, Georg Gottlob, Kazuhisa Makino
ac.jp This paper considers the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph), whose associated decision problem is a prominent open problem in...
Hypergraph transversal computation and related problems in logic and AI (2002)
Abstract. Generating minimal transversals of a hypergraph is an important problem which has many applications in Computer Science. In the present paper, we address this problem and its decisional...
Efficient algorithms for processing XPath queries (2002)
Georg Gottlob, Christoph Koch, Reinhard Pichler
Our experimental analysis of several popular XPath processors reveals a striking fact: Query evaluation in each of the systems requires time exponential in the size of queries in the worst case. We...
Efficient algorithms for processing XPath queries (2002)
Georg Gottlob, Christoph Koch, Reinhard Pichler
Our experimental analysis of several popular XPath processors reveals a striking fact: Query evaluation in each of the systems requires time exponential in the size of queries in the worst case. We...
Hypergraph transversal computation and related problems in logic and AI (2002)
Abstract. Generating minimal transversals of a hypergraph is an important problem which has many applications in Computer Science. In the present paper, we address this problem and its decisional...
Declarative Information Extraction, Web Crawling, and Recursive Wrapping with Lixto (2001)
Robert Baumgartner, Sergio Flesca, Georg Gottlob
Abstract. Lixto is a system and method for the visual and interactive generation of wrappers for Web pages under the supervision of a human developer, for automatically extracting information from...
Second-order logic over strings: Regular and nonregular fragments (2001)
Thomas Eiter, Georg Gottlob, Thomas Schwentick
Abstract. By a well-known result due to Buchi and Trakhtenbrot, all monadic second-order sentences over words describe regular languages. In this paper, we investigate prefix classes of general...
Visual web information extraction with Lixto (2001)
Robert Baumgartner, Sergio Flesca, Georg Gottlob
We present new techniques for supervised wrapper generation and automated web information extraction, and a system called Lixto implementing these techniques. Our system can generate wrappers which...
Supervised Wrapper Generation with Lixto (2001)
Robert Baumgartner, Dbai Tu Wien, Sergio Flesca, Georg Gottlob
We illustrate basic features of the Lixto wrapper generator such as the user and system interaction, the capacious visual interface, the marking and selecting procedures, and the extraction tasks by...
Visual web information extraction with Lixto (2001)
Robert Baumgartner, Sergio Flesca, Georg Gottlob
We present new techniques for supervised wrapper generation and automated web information extraction, and a system called Lixto implementing these techniques. Our system can generate wrappers which...
Visual web information extraction with Lixto (2001)
Robert Baumgartner, Sergio Flesca, Georg Gottlob
We present new techniques for supervised wrapper generation and automated web information extraction, and a system called Lixto implementing these techniques. Our system can generate wrappers which...
Hypertree decompositions: A survey (2001)
Georg Gottlob, Francesco Scarcello
Abstract. This paper surveys recent results related to the concept of hypertree decomposition and the associated notion of hypertree width. A hypertree decomposition of a hypergraph (similar to a...
Georg Gottlob, Nicola Leone, Francesco Scarcello C
Robbers,marshals,and guards: game theoretic and logical characterizations of hypertree width $
Georg Gottlob, Nicola Leone, Francesco Scarcello
º3Ä'w. p É:)Î8r:ÌÔ pqÊ ÏcGÕ r>Ì×Ö pnØ|DÉ: ÕBr:ÌÚÙ(p Îc)ÕBr Ó
A comparison of structural CSP decomposition methods (2000)
Georg Gottlob, Nicola Leone, Francesco Scarcello
We compare tractable classes of constraint satisfaction problems (CSPs). We first give a uniform presentation of the major structural CSP decomposition methods. We then introduce a new class of...
Existential second-order logic over graphs: Charting the tractability frontier (2000)
Georg Gottlob, Tu Wien, Phokion G. Kolaitis, Thomas Schwentick
Fagin's theorem, the rst important result of descriptive complexity, asserts that a property of graphs is in NP if and only if it is denable by an existential secondorder formula. In this paper,...
On the Complexity of Theory Curbing (2000)
Abstract. In this paper, we determine the complexity of propositional theory curbing. Theory Curbing is a nonmonotonic technique of common sense reasoning that is based on model minimality but unlike...
A comparison of structural CSP decomposition methods (2000)
Georg Gottlob, Nicola Leone, Francesco Scarcello
We compare tractable classes of constraint satisfaction problems (CSPs). We first give a uniform presentation of the major structural CSP decomposition methods. We then introduce a new class of...
Generalized Quantifiers in Logic Programs (1999)
Abstract. Generalized quantifiers are an important concept in modeltheoretic logic which has applications in different fields such as linguistics, philosophical logic and computer science. In this...
Enhancing Model Checking in Verification by AI Techniques (1999)
Francesco Buccafurri, Thomas Eiter, Georg Gottlob, Nicola Leone
Model checking is a fruitful application of computational logic with high relevance to the verification of concurrent systems. While model checking is capable of automatically testing that a...
Robert Baumgartner, Georg Gottlob
We analyse the complexity of standard and weak model checking for propositional default logic; in particular, we solve the open problem of complexity in case of normal default theories and introduce...
Complexity and Expressive Power of Logic Programming (1999)
Abtg Wissensbasierte Systeme, Georg Gottlob, Andrei Voronkov, Evgeny Dantsin, Evgeny Dantsin, Thomas Eiter, ...
. This paper surveys various complexity and expressiveness results on different forms of logic programming. The main focus is on decidable forms of logic programming, in particular, propositional...
Datalog LITE: Temporal versus deductive reasoning in verification (1998)
Georg Gottlob, Erich Grädel, Helmut Veith
. In this paper we show that Datalog is well-suited as a temporal verification language. Datalog is a well-known database query language relying on the logic programming paradigm. We introduce...
Towards a Compact Knowledge Representation by AR Models (1998)
Georg Gottlob, Reinhard Pichler
An AR model (= atomic representation of a Herbrand structure ) is given through a set A = fA 1 ; : : : ; An g of atoms over some Herbrand universe H with the following intended meaning: a ground atom...
The complexity of acyclic conjunctive queries (1998)
Georg Gottlob, Nicola Leone, Francesco Scarcello
This paper deals with the evaluation of acyclic Boolean conjunctive queries in relational databases. By well-known results of Yannakakis [1981], this problem is solvable in polynomial time; its...
Modular logic programming and generalized quantifiers (1997)
Thomas Eiter, Georg Gottlob, Ag Informatik
Abstract. The research on systems of logic programming with modules has followed two mainstreams, programming-in-the-large, where compositional operators are provided for combining separate and...
Modular logic programming and generalized quantifiers (1997)
Helmut Veith, Thomas Eiter, Thomas Eiter, Georg Gottlob, Georg Gottlob
The research on logic programming with modules has followed two mainstreams: Programming-in-the-large, where compositional operators are provided for combining separate and independent modules, and...
On the indiscernibility of individuals in logic programming (1997)
Thomas Eiter, Georg Gottlob, Nicola Leone
According to Leibniz ' principle, two individuals a and b are indiscernible, if they share the same properties. Indiscernibility of objects provides a potential for optimization in deductive...
We consider disjunctive Datalog, a powerful database query language based on disjunctive gic programming. Briefly, disjunctive Datalog is a variant of Datalog where disjunctions may appear in the...
Abduction from logic programs: Semantics and complexity (1997)
Thomas Eiter, Georg Gottlob, Nicola Leone
Abduction-- from observations and a theory, find using hypotheses an explanation for the observations-- gained increasing interest during the last years. This form of reasoning has wide applicability...
The dlv system: Model generator and application frontends (1997)
Simona Citrigno, Thomas Eiter, Wolfgang Faber, Georg Gottlob, Christoph Koch, Nicola Leone, ...
ay
Semantics and Complexity of Abduction from Default Theories (1997)
Thomas Eiter, Georg Gottlob, Nicola Leone
Abductive reasoning (roughly speaking, find an explanation for observations out of hypotheses), has been recognized as an important principle of common-sense reasoning. Since logical knowledge...
Default Logic as a Query Language (1997)
Marco Cadoli, Thomas Eiter, Georg Gottlob
| Research in non-monotonic reasoning has focused largely on the idea of representing knowledge about the world via rules that are generally true but can be defeated. Even if relational databases are...
Semantics and Complexity of Abduction from Default Theories (Extended Abstract) (1997)
Thomas Eiter, Georg Gottlob, Nicola Leone
Since logical knowledge representation is commonly based on nonclassical formalisms like default logic, autoepistemic logic, or circumscription, it is necessary to perform abductive reasoning from...
Default Logic as a Query Language (1997)
Marco Cadoli, Thomas Eiter, Georg Gottlob
Research in NMR has focused largely on the idea of representing knowledge about the world via rules that are generally true but can be defeated. Even if relational databases are nowadays the main...
Existential Second-Order Logic over Strings (1997)
Thomas Eiter, Thomas Eiter, Georg Gottlob, Georg Gottlob, Yuri Gurevich, Yuri Gurevich
. Existential second-order logic (ESO) and monadic second-order logic (MSO) have attracted much interest in logic and computer science. ESO is a much more expressive logic over word structures than...
Capturing Relativized Complexity Classes without Order (1997)
Anuj Dawar, Georg Gottlob, Lauri Hella
We consider the problem of obtaining logical characterisations of oracle complexity classes. In particular, we consider the complexity classes LOGSPACE NP and PTIME NP . For these classes,...
Enhancing Symbolic Model Checking by AI Techniques (1997)
Nicola Leone, Francesco Buccafurri, Francesco Buccafurri, Georg Gottlob, Georg Gottlob, Thomas Eiter, ...
. Model checking is a fruitful application of computational logic with high relevance to the verification of concurrent systems. While model checking is capable of automatically testing that a...
System: Model Generator and Application Frontends (1997)
Simona Citrigno, Thomas Eiter, Wolfgang Faber, Georg Gottlob, Christoph Koch, Nicola Leone, ...
During the last years, much research has been done concerning semantics and complexity of Disjunctive Deductive Databases (DDDBs). While DDDBs --- function-free disjunctive logic programs with...
The dlv System: Model Generator and Application Frontends (1997)
Simona Citrigno Thomas, Thomas Eiter, Wolfgang Faber, Georg Gottlob, Christoph Koch, Nicola Leone, ...
During the last years, much research has been done concerning semantics and complexity of Disjunctive Deductive Databases (DDDBs). While DDDBs | function-free disjunctive logic programs with negation...
Relativized Logspace and Generalized Quantifiers over Finite Structures (1997)
The expressive power of first order logic with generalized quantifiers over finite ordered structures is studied. The following problem is addressed: Given a family Q of generalized quantifiers...
Annals of Pure and AppliedLogic, 78 (1996), 111--125. (1997)
Normal Forms For, Thomas Eiter, Georg Gottlob, Yuri Gurevich
We start with a simple proof of Leivant's normal form theorem for \Sigma 1 formulas over finite successor structures. Then we use that normal form to prove the following: (i) over all finite...
Existential Second-Order Logic over Strings (Extended Abstract) (1997)
Thomas Eiter, Georg Gottlob, Yuri Gurevich, G. Gottlob, Y. Gurevich
Existential second-order logic (ESO) and monadic second-order logic (MSO) have attracted much interest in logic and computer science. ESO is a much moreexpressive logic over word structures than MSO....
On the Indiscernibility of Individuals in Logic Programming (1997)
EITER, THOMAS, GOTTLOB, GEORG, LEONE, NICOLA
According to Leibniz' principle, two individuals a and b are indiscernible, if they share the same properties. Indiscernibility of objects provides a potential for optimization in deductive systems,...
Extending object-oriented systems with roles (1996)
G. Gottlob, M. Schrefl, B. Rock, Einzelergebnisse Materialien, Im Interesse, Georg Gottlob, ...
zu vervielfaltigen. Die Autoren sind fur kritische Hinweise dankbar. "Institutsberichte " primarily comprise preliminary publications, specific partial results and complementary...
Thomas Eiter Georg, Thomas Eiter, Georg Gottlob, Georg Gottlob, Yuri Gurevich, Yuri Gurevich
We start with a simple proof of Leivant's normal form theorem for \Sigma 1 1 formulas over finite successor structures. Then we use that normal form to prove the following: (i) over all finite...
Thomas Eiter, Georg Gottlob, Yuri Gurevich
We start with a simple proof of Leivant's normal form theorem for 1 1 formulas over nite successor structures. Then we use that normal form to prove the following: (i) over all nite structures,...
Reducing Disjunctive to Non-Disjunctive Semantics by Shift-Operations (1996)
Jürgen Dix, J Urgen Dix, Georg Gottlob, Wiktor Marek, Cecylia Rauszer
It is wellknown that Minker's semantics GCWA for positive disjunctive programs P is P P 2 -complete , i.e. to decide if a literal is true in all minimal models of P . This is in contrast to the...
Approximating the Stable Model Semantics is Hard (1996)
Georg Gottlob, Miroslaw Truszczynski
In this paper we investigate the complexity of problems concerned with approximating the stable model semantics. We show that under rather weak assumptions it is NP-hard to decide whether the size of...
Thomas Eiter, Georg Gottlob, Yuri Gurevich
We start with a simple proof of Leivant's normal form theorem for \Sigma 1 1 formulas over finite successor structures. Then we use that normal form to prove the following: (i) over all finite...
On the Indiscernibility of Individuals in Logic Programming (1996)
Thomas Eiter, Thomas Eiter, Georg Gottlob, Georg Gottlob, Nicola Leone, Nicola Leone
According to Leibniz's principle, two individuals a and b are indiscernible, if they share the same properties. Indiscernibility of objects provides a potential for optimization in deductive...
Thomas Eiter, Georg Gottlob, Yuri Gurevich
We start with a simple proof of Leivant's normal form theorem for \Sigma 1 1 formulas over finite successor structures. Then we use that normal form to prove the following: (i) over all finite...
Identifying the minimal transversals of a hypergraph and related problems (1995)
The paper considers two decision problems on hypergraphs, hypergraph saturation and recognition of the transversal hypergraph, and discusses their significance for several search problems in applied...
Note on the Complexity of Some Eigenvector Problems (1995)
Thomas Eiter, Thomas Eiter, Georg Gottlob, Georg Gottlob
We consider the computation of eigenvectors x = (x 1 ; : : : ; n) over the integers, where each component x i satisfies jx i j c for a constant c. We address decisional problems in this context, and...
Identifying the Minimal Transversals of a Hypergraph and Related Problems (1995)
The paper considers two decision problems on hypergraphs, hypergraph saturation and recognition of the transversal hypergraph, and discusses their significance for several search problems in applied...
Symmetric Logspace is Closed Under Complement (1995)
Noam Nisan, Abadi Greg, Frederickson John Mitchell, Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, ...
We present a Logspace, many-one reduction from the undirected Abstract-1 st connectivity problem to its complement. This shows that SL = coSL. 1 Introduction This paper deals with the complexity...
On the Weak mod m Representation of Boolean Functions (1995)
Vince Grolmusz, Abadi Greg, Frederickson John Mitchell, Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, ...
Let P be a polynomial over the ring of mod m integers. P weakly represents Boolean function f : f0; 1g n ! f0; 1g if there is a subset S ` f0; 1; : : : ; m \Gamma 1g such that f(x) = 0 if and only if...
Thomas Eiter, Georg Gottlob, Yuri Gurevich
We start with a simple proof of Leivant's normal form theorem for \Sigma 1 1 formulas over finite successor structures. Then we use that normal form to prove the following: (i) over all finite...
Probabilistically Checkable Debate Systems and Nonapproximability of PSPACE-Hard Functions (1995)
Pankaj Agarwal, Joan Feigenbaum, Carsten Lund, Andrew Goldberg, Ketan Mulmuley, ...
We initiate an investigation of probabilistically checkable debate systems (PCDS), a natural generalization of probabilistically checkable proof systems (PCPS). A PCDS for a language L consists of a...
Nils Klarlund, Dexter Kozen, Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, ...
Rabin conditions are a general class of properties of infinite sequences that encompass most known automata-theoretic acceptance conditions and notions of fairness. In this paper, we introduce a...
Symmetric Logspace is Closed under Complement (1995)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
We present a Logspace, many-one reduction from the undirected Abstract-1 s--t connectivity problem to its complement. This shows that SL = coSL.
The complexity of logic-based abduction (1995)
Abduction is an important form of nonmonotonic reasoning allowing one to find explanations for certain symptoms or manifestations. When the application domain is described by a logical theory, we...
[ii] Chicago Journal of Theoretical Computer Science 1995-3Rabin Measures (1995)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
Published one article at a time in LATEX source form on the Internet. Pagination
Adding Disjunction to Datalog (Extended Abstract) (1994)
Thomas Eiter, Georg Gottlob, Heikki Mannila
) Thomas Eiter Georg Gottlob Heikki Mannila Christian Doppler Laboratory for Expert Systems, Information Systems Department Technical University of Vienna, Paniglgasse 16, A-1040 Wien, Austria...
A Slightly Revised Version Will Appear in: (1994)
Annals Of Mathematics, Gerhard Friedrich, Georg Gottlob, Wolfgang Nejdl
This paper defines the model-based diagnosis and repair process. We consider repair (i.e. restoration of specified system purposes) as the main goal of this process. Our goal is to define how an...
The power of beliefs or translating default logic into standard autoepistemic logic (1993)
Since Konolige's translation of default logic into strongly grounded autoepistemic logic, several other variants of Moore's original autoepistemic logic that embody default logic have been...
Propositional Circumscription and Extended Closed World Reasoning are \Pi P 2 -complete (1993)
Circumscription and the closed world assumption with its variants are well-known nonmonotonic techniques for reasoning with incomplete knowledge. Their complexity in the propositional case has been...
Complexity Aspects of Various Semantics for Disjunctive Databases (1993)
This paper addresses complexity issues for important problems arising with disjunctive databases. In particular, the complexity of inference of a literal and a formula from a propositional...
Complexity Results for Disjunctive Logic Programming and Application to Nonmonotonic Logics (1993)
Ben-Eliyahu and Dechter have shown that stable semantics of a large class of extended propositional disjunctive logic programs (EDLPs) can be efficiently expressed in the language of propositional...
The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions (1993)
We consider the computational complexity of evaluating nested counterfactuals over a propositional knowledge base. Counterfactual implication p ? q models a statement "if p, then q," where...
The Complexity of Logic-Based Abduction (1993)
Thomas Eiter, Thomas Eiter, Georg Gottlob, Georg Gottlob
Abduction is an important form of nonmonotonic reasoning allowing one to find explanations for certain symptoms or manifestations. When the application domain is described by a logical theory, we...
The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions (1993)
We consider the computational complexity of evaluating nested counterfactuals over a propositional knowledge base. A counterfactual p ? q is a conditional query with the meaning "If p would be...
Thomas Eiter, Georg Gottlob, Yuri Gurevich
We introduce curbing, a new nonmonotonic technique of commonsense reasoning that is based on model minimality but unlike circumscription treats disjunction inclusively. A finitely axiomatized...
Thomas Eiter, Georg Gottlob, Yuri Gurevich
We introduce curbing, a new nonmonotonic technique of commonsense reasoning that is based on model minimality but unlike circumscription treats disjunction inclusively. A first-order theory T is...
Circumscriptive Approach For, Thomas Eiter, Georg Gottlob, Yuri Gurevich
Weintroduce curbing, a new nonmonotonic technique of commonsense reasoning that is based on model minimality but unlike circumscription treats disjunction inclusively. A first-order theory T is...
A circumscriptive approach for inclusive interpretation of disjunctive information*
Formalizing the repair process (1992)
Gerhard Friedrich, Georg Gottlob, Wolfgang Nejdl
Abstract. This paper defines the model-based diagnosis and repair process. We consider repair (i.e. restoration of specified system purposes) as the main goal of this process. Our goal is to define...
On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals (1992)
Thomas Eiter, Georg Gottlob, Expert Systems
We study the complexity of several recently proposed methods for updating or revising propositional knowledge bases. In particular, we derive complexity results for the following problem: given a...
On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals (1992)
We study the complexity of several recently proposed methods for updating or revising propositional knowledge bases under the principle of minimal change. In particular, we derive complexity results...
An Efficient Method for Eliminating Varying Predicates from a Circumscription (1992)
Marco Cadoli, Thomas Eiter, Georg Gottlob
Circumscription appears to be the most powerful and well-studied technique used in formalizing common-sense reasoning. The general form of predicate circumscription allows for fixed and varying...
Complexity Results for Nonmonotonic Logics (1992)
The complexity of different reasoning tasks in nonmonotonic propositional logics is investigated. The systems of logic we considered are Reiter's default logic, McDermott's and Doyle's nonmonotonic...
Semantics of Object-Oriented Data Models - The Evolving Algebra Approach (1991)
Georg Gottlob, Gerti Kappel, Michael Schrefl
The formal description of the semantics of object-oriented data models is still an open problem. Some characteristic features of object-oriented data models, such as methods and inheritance, involve...
Georg Gottlob, Georg Gottlob, Leonid Libkin, Leonid Libkin
This paper first presents some new results on excluded functional dependencies, i.e., FDs which do not hold on a given relation schema. In particular, we show how excluded dependencies relate to...
Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan, Knowledge-base Systems, Cgt Stefano Ceri, ...
this paper we have shown that the magic-sets techniques can be extended to deal with conditions. We believe that the work described in this paper is important not only because it extends the...
Closed world databases opened through null values (1988)
We propose a new approach to the treatment of null-valued attributes in the relational model. The approach is based on the new concept of locally-controlled open world database. A locally-controlled...