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...
Table of Contents Foundations of Rule-Based Query Answering........................ 1 (2008)
François Bry, Norbert Eisinger, Thomas Eiter, Tim Furche, Georg Gottlob, Clemens Ley, ...
Complexity Theory 1. General Information 1.1. Classes Classes (2008)
Language. This lecture will probably be held in English.
Algorithmic aspects of Herbrand models represented by ground atoms with ground equations (2007)
Bernhard Gramlich, Reinhard Pichler
Abstract. Automated model building has evolved as an important subdiscipline of automated deduction over the past decade. One crucial issue in automated model building is the selection of an...
Reinhard Pichler, Hypergraphs Acyclicity, Nicola Leone, Francesco Buccafurri, Thomas Eiter, Georg Gottlob, ...
ACTL formulas having linear counterexamples. JCSS, 62(3):463-515, 2001.
Uwe Egly, Reinhard Pichler, Stefan Woltran
Subsumption is an important redundancy elimination method in automated theorem proving. For a given Herbrand universe H, it can be strengthened to the clausal H-subsumption, i.e., a clause D over a...
On the Complexity of Equational Problems in CNF over a Finite Domain (2007)
Abstract. Equational problems (i.e.: first-order formulae with quantifier prefix 9
Extending Decidable Clause Classes via Constraints (2007)
There are several well known possibilities which constrained clauses (= c-clauses, for short) provide in addition to standard clauses. In particular, many (even infinitely many) standard clauses can...
Model Representation over Finite and Infinite Signatures (2007)
Fermüller, Christian G., Pichler, Reinhard
The computationally adequate representation of term models for sets of clauses is a topic that is relevant to many areas of Computer Science. Two fundamental decision problems arise: (1) to check...
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...
Model Representation over Finite and Infinite Signatures (2007)
Fermüller, Christian G., Pichler, Reinhard
The computationally adequate representation of term models for sets of clauses is a topic that is relevant to many areas of Computer Science. Two fundamental decision problems arise: (1) to check...
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...
On deciding subsumption problems (2005)
Abtg Wissensbasierte Systeme, Uwe Egly, Uwe Egly, Reinhard Pichler, Reinhard Pichler, Stefan Woltran, ...
Abstract. Subsumption is an important redundancy elimination method in automated deduction. A clause D is subsumed by a set C of clauses if there is a clause C 2 C and a substitution such that the...
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...
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 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...
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...
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...
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...
Allegorese und Ethik bei Proklos : Untersuchungen zum Kommentar zu Platons Politeia / (2001)
Innsbruck, Universiẗat, Diss., 2001.
Completeness and Redundancy in Constrained Clause Logic (2000)
In [CZ 91], a resolution-based inference system on c-clauses (i.e. constrained clauses) was introduced, incorporating powerful deletion rules for redundancy elimination. This inference system was...
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...
This paper is structured as follows: First we transform the original model equivalence problem into another type of problem which we shall call the linear term tuple cover problem, i.e.: Given a set...