Georg Gottlob

AAAI Conference 2025 Conference Paper

Selective Forgetting: Advancing Machine Unlearning Techniques and Evaluation in Language Models

• Lingzhi Wang
• Xingshan Zeng
• Jinsong Guo
• Kam-Fai Wong
• Georg Gottlob

This paper explores Machine Unlearning (MU), an emerging field that is gaining increased attention due to concerns about neural models unintentionally remembering personal or sensitive information. We present SeUL, a novel method that enables selective and fine-grained unlearning for language models. Unlike previous work that employs a fully reversed training objective in unlearning, SeUL minimizes the negative impact on the capability of language models, particularly in terms of generation. Furthermore, we introduce two innovative evaluation metrics, sensitive extraction likelihood (S-EL) and sensitive memorization accuracy (S-MA), specifically designed to assess the effectiveness of forgetting sensitive information. In support of the unlearning framework, we propose efficient automatic online and offline sensitive span annotation methods. The online selection method, based on language probability scores, ensures computational efficiency, while the offline annotation involves a two-stage LLM-based process for robust verification. In summary, this paper contributes a novel selective unlearning method (SeUL), introduces specialized evaluation metrics (S-EL and S-MA) for assessing sensitive information forgetting, and proposes automatic online and offline sensitive span annotation methods to support the overall unlearning framework and evaluation.

CSL Conference 2024 Conference Paper

Artificial Intelligence and Artificial Ignorance (Invited Talk)

• Georg Gottlob

This invited talk first delves into the division between the two primary branches of AI research: symbolic AI, which predominantly focuses on knowledge representation and logical reasoning, and sub-symbolic AI, primarily centered on machine learning employing neural networks. We explore both the notable accomplishments and the challenges encountered in each of these approaches. We provide instances where traditional deep learning encounters limitations, and we elucidate significant obstacles in achieving automated symbolic reasoning. We then discuss the recent groundbreaking advancements in generative AI, driven by language models such as ChatGPT. We showcase instances where these models excel and, conversely, where they exhibit shortcomings and produce erroneous information. We identify and illustrate five key reasons for potential failures in language models, which include: [(i)] 1) information loss due to data compression, 2) training bias, 3) the incorporation of incorrect external data, 4) the misordering of results, and 5) the failure to detect and resolve logical inconsistencies contained in a sequence of LLM-generated prompt-answers. Lastly, we touch upon the Chat2Data project, which endeavors to leverage language models for the automated verification and enhancement of relational databases, all while mitigating the pitfalls (i)-(v) mentioned earlier.

LPAR Conference 2024 Conference Paper

Fuzzy Datalog∃ over Arbitrary t-Norms

• Matthias Lanzinger
• Stefano Sferrazza
• Przemyslaw Andrzej Walega
• Georg Gottlob

One of the main challenges in the area of Neuro-Symbolic AI is to perform logical reasoning in the presence of both neural and symbolic data. This requires combining heterogeneous data sources such as knowledge graphs, neural model predictions, structured databases, crowd-sourced data, and many more. To allow for such reasoning, we generalise the standard rule-based language Datalog with existential rules (commonly referred to as tuple-generating dependencies) to the fuzzy setting, by allowing for arbitrary t-norms in the place of classical conjunctions in rule bodies. The resulting formalism allows us to perform reasoning about data associated with degrees of uncertainty while preserving computational complexity results and the applicability of reasoning techniques established for the standard Datalog setting. In particular, we provide fuzzy extensions of Datalog chases which produce fuzzy universal models and we exploit them to show that in important fragments of the language, reasoning has the same complexity as in the classical setting.

TCS Journal 2023 Journal Article

Fractional covers of hypergraphs with bounded multi-intersection

• Georg Gottlob
• Matthias Lanzinger
• Reinhard Pichler
• Igor Razgon

Fractional (hyper-)graph theory is concerned with the specific problems that arise when fractional analogues of otherwise integer-valued (hyper-)graph invariants are considered. The focus of this paper is on fractional edge covers of hypergraphs. Our main technical result generalizes and unifies previous conditions under which the size of the support of fractional edge covers is bounded independently of the size of the hypergraph itself. We show how this combinatorial result can be used to extend previous tractability results for checking if the fractional hypertree width of a given hypergraph is ≤k for some constant k. Moreover, we show a dual version of our main result for fractional hitting sets.

IJCAI Conference 2023 Conference Paper

MV-Datalog+/-: Effective Rule-based Reasoning with Uncertain Observations (Extended Abstract)

• Matthias Lanzinger
• Stefano Sferrazza
• Georg Gottlob

Modern data processing applications often combine information from a variety of complex sources. Oftentimes, some of these sources, like Machine-Learning systems or crowd-sourced data, are not strictly binary but associated with some degree of confidence in the observation. Ideally, reasoning over such data should take this additional information into account as much as possible. To this end, we propose extensions of Datalog and Datalog+/- to the semantics of Lukasiewicz logic Ł, one of the most common fuzzy logics. We show that such an extension preserves important properties from the classical case and how these properties can lead to efficient reasoning procedures for these new languages.

AIJ Journal 2023 Journal Article

Polynomial combined first-order rewritings for linear and guarded existential rules

• Georg Gottlob
• Marco Manna
• Andreas Pieris

We consider the problem of ontological query answering, that is, the problem of answering a database query (typically a conjunctive query) in the presence of an ontology. This means that during the query answering process we also need to take into account the knowledge that can be inferred from the given database and ontology. Building, however, ontology-aware database systems from scratch, with sophisticated optimization techniques, is a highly non-trivial task that requires a great engineering effort. Therefore, exploiting conventional database systems is an important route towards efficient ontological query answering. Nevertheless, standard database systems are unaware of ontologies. An approach to ontological query answering that enables the use of standard database systems is the so-called polynomial combined query rewriting, originally introduced in the context of description logics: the conjunctive query q and the ontology Σ are rewritten in polynomial time into a first-order query q Σ (in a database-independent way), while the database D and the ontology Σ are rewritten in polynomial time into a new database D Σ (in a query-independent way), such that the answer to q in the presence of Σ over D coincides with the answer to q Σ over D Σ. The latter can then be computed by exploiting a conventional database system. In this work, we focus on linear and guarded existential rules, which form robust rule-based languages for modeling ontologies, and investigate the limits of polynomial combined query rewriting. In particular, we show that this type of rewriting can be successfully applied to (i) linear existential rules when the rewritten query can use the full power of first-order queries, (ii) linear existential rules when the arity of the underlying schema is fixed and the rewritten query is positive existential, namely it uses only existential quantification, conjunction, and disjunction, and (iii) guarded existential rules when the underlying schema is fixed and the rewritten query is positive existential. We can show that the above results reach the limits (under standard complexity-theoretic assumptions such as Image 1 ) of polynomial combined query rewriting in the case of linear and guarded existential rules.

AAAI Conference 2022 Conference Paper

On the Complexity of Inductively Learning Guarded Clauses

• Andrei Draghici
• Georg Gottlob
• Matthias Lanzinger

We investigate the computational complexity of mining guarded clauses from clausal datasets through the framework of inductive logic programming (ILP). We show that learning guarded clauses is NP-complete and thus one step below the ΣP 2 -complete task of learning Horn clauses on the polynomial hierarchy. Motivated by practical applications on large datasets we identify a natural tractable fragment of the problem. Finally, we also generalise all of our results to k-guarded clauses for constant k.

IJCAI Conference 2020 Conference Paper

Fast and Parallel Decomposition of Constraint Satisfaction Problems

• Georg Gottlob
• Cem Okulmus
• Reinhard Pichler

Constraint Satisfaction Problems (CSP) are notoriously hard. Consequently, powerful decomposition methods have been developed to overcome this complexity. However, this poses the challenge of actually computing such a decomposition for a given CSP instance, and previous algorithms have shown their limitations in doing so. In this paper, we present a number of key algorithmic improvements and parallelisation techniques to compute so-called Generalized Hypertree Decompositions (GHDs) faster. We thus advance the ability to compute optimal (i. e. , minimal-width) GHDs for a significantly wider range of CSP instances on modern machines. This lays the foundation for more systems and applications in evaluating CSPs and related problems (such as Conjunctive Query answering) based on their structural properties.

MFCS Conference 2020 Conference Paper

Fractional Covers of Hypergraphs with Bounded Multi-Intersection

• Georg Gottlob
• Matthias Lanzinger
• Reinhard Pichler
• Igor Razgon

Fractional (hyper-)graph theory is concerned with the specific problems that arise when fractional analogues of otherwise integer-valued (hyper-)graph invariants are considered. The focus of this paper is on fractional edge covers of hypergraphs. Our main technical result generalizes and unifies previous conditions under which the size of the support of fractional edge covers is bounded independently of the size of the hypergraph itself. This allows us to extend previous tractability results for checking if the fractional hypertree width of a given hypergraph is ≤ k for some constant k. We also show how our results translate to fractional vertex covers.

KR Conference 2020 Conference Paper

Multi-head Guarded Existential Rules Over Fixed Signatures

• Georg Gottlob
• Marco Manna
• Andreas Pieris

Guarded existential rules form a robust rule-based language for modelling ontologies. The central problem of ontology-based query answering, as well as the notion of polynomial combined rewritability, have been extensively studied during the last years for this formalism. However, the relevant setting where the underlying signature is considered to be fixed is far from being well understood. All the existing results on ontology-based query answering and polynomial combined rewritability assume rule heads with one atom, while existential rules in real ontologies are typically coming with multi-heads consisting of several atoms. We aim to fill this gap.

IJCAI Conference 2020 Conference Paper

Semantic Width and the Fixed-Parameter Tractability of Constraint Satisfaction Problems

• Hubie Chen
• Georg Gottlob
• Matthias Lanzinger
• Reinhard Pichler

Constraint satisfaction problems (CSPs) are an important formal framework for the uniform treatment of various prominent AI tasks, e. g. , coloring or scheduling problems. Solving CSPs is, in general, known to be NP-complete and fixed-parameter intractable when parameterized by their constraint scopes. We give a characterization of those classes of CSPs for which the problem becomes fixed-parameter tractable. Our characterization significantly increases the utility of the CSP framework by making it possible to decide the fixed-parameter tractability of problems via their CSP formulations. We further extend our characterization to the evaluation of unions of conjunctive queries, a fundamental problem in databases. Furthermore, we provide some new insight on the frontier of PTIME solvability of CSPs. In particular, we observe that bounded fractional hypertree width is more general than bounded hypertree width only for classes that exhibit a certain type of exponential growth. The presented work resolves a long-standing open problem and yields powerful new tools for complexity research in AI and database theory.

JELIA Conference 2019 Invited Paper

Vadalog: Recent Advances and Applications

• Georg Gottlob
• Andreas Pieris
• Emanuel Sallinger

Abstract Vadalog is a logic-based reasoning language for modern AI applications, in particular for knowledge graph systems. In this paper, we present recent advances and applications, with a focus on the Vadalog language itself. We first give an easy-to-access self-contained introduction to Warded Datalog+/−, the logical core of Vadalog. We then discuss some recent advances: Datalog rewritability of Warded Datalog+/−, and the piece-wise linear fragment of Warded Datalog+/− that achieves space efficiency. We then proceed with some recent practical applications of the Vadalog language: detection of close links in financial knowledge graphs, as well as the detection of family-owned businesses.

IJCAI Conference 2018 Conference Paper

Finite Model Reasoning in Hybrid Classes of Existential Rules

• Georg Gottlob
• Marco Manna
• Andreas Pieris

Two paradigmatic restrictions that have been studied for ensuring the decidability of query answering under existential rules are guardedness and stickiness. With the aim of consolidating these restrictions, a flexible condition, called tameness, has been proposed a few years ago, which relies on hybrid reasoning, i. e. , a combination of forward and backward procedures. The complexity of query answering under this hybrid class of existential rules is by now well-understood. However, the complexity of finite query answering, i. e. , query answering under finite models, has remained an open problem. Closing this problem is the main goal of this work.

IJCAI Conference 2017 Conference Paper

Swift Logic for Big Data and Knowledge Graphs

• Luigi Bellomarini
• Georg Gottlob
• Andreas Pieris
• Emanuel Sallinger

Many modern companies wish to maintain knowledge in the form of a corporate knowledge graph and to use and manage this knowledge via a knowledge graph management system (KGMS). We formulate various requirements for a fully fledged KGMS. In particular, such a system must be capable of performing complex reasoning tasks but, at the same time, achieve efficient and scalable reasoning over Big Data with an acceptable computational complexity. Moreover, a KGMS needs interfaces to corporate databases, the web, and machine-learning and analytics packages. We present KRR formalisms and a system achieving these goals.

IJCAI Conference 2015 Conference Paper

Beyond SPARQL under OWL 2 QL Entailment Regime: Rules to the Rescue

• Georg Gottlob
• Andreas Pieris

SPARQL is the de facto language for querying RDF data, since its standardization in 2008. A new version, called SPARQL 1. 1, was released in 2013, with the aim of enriching the 2008 language with reasoning capabilities to deal with RDFS and OWL vocabularies, and a mechanism to express navigation patterns through regular expressions. However, SPARQL 1. 1 is not powerful enough for expressing some relevant navigation patterns, and it misses a general form of recursion. In this work, we focus on OWL 2 QL and we propose TriQ-Lite 1. 0, a tractable rule-based formalism that supports the above functionalities, and thus it can be used for querying RDF data. Unlike existing composite approaches, our formalism has simple syntax and semantics in the same spirit as good old Datalog.

IJCAI Conference 2015 Conference Paper

Polynomial Rewritings for Linear Existential Rules

• Georg Gottlob
• Marco Manna
• Andreas Pieris

We consider the scenario of ontology-based query answering. It is generally accepted that true scalability in this setting can only be achieved via query rewriting, which in turn allows for the exploitation of standard RDBMSs. In this work, we close two open fundamental questions related to query rewriting. We establish that linear existential rules are polynomially combined rewritable, while full linear rules are polynomially (purely) rewritable; in both cases, the target query language consists of first-order or non-recursive Datalog queries. An immediate consequence of our results is that DLR- LiteR, the extension of DL-LiteR with n-ary roles, is polynomially combined rewritable.

KR Conference 2014 Conference Paper

Polynomial Combined Rewritings for Existential Rules

• Georg Gottlob
• Marco Manna
• Andreas Pieris

We consider the scenario of ontology-based data access where a conjunctive query is evaluated against a database enriched with intensional knowledge via an ontology. It is generally accepted that true scalability of query answering in this setting can only be achieved by using standard relational database management systems (RDBMSs). An approach to query answering that enables the use of RDBMSs is the so-called polynomial combined approach. We investigate this approach for the main guarded- and sticky-based classes of existential rules, and we highlight the assumptions on the underlying schema which are sufficient for the polynomial combined first-order rewritability of those classes. To the best of our knowledge, this is the first work which explicitly studies the polynomial combined approach for existential rules.

KR Conference 2014 Conference Paper

Stable Model Semantics for Guarded Existential Rules and Description Logics

• Georg Gottlob
• Andre Hernich
• Clemens Kupke
• Thomas Lukasiewicz

Baget et al. 2009; 2011; Thomazo 2011; Calı̀, Gottlob, and Pieris 2012; Gottlob, Manna, and Pieris 2013). Related syntactic conditions led to the Datalog± family (Calı̀, Gottlob, and Lukasiewicz 2012). A class of major relevance are guarded TGDs (GTGDs). A TGD is guarded if its body contains an atom, called guard, that covers all body variables. NCs may be safely used together with guarded TGDs; their bodies are not required to contain a guard atom. A nice and important aspect of guarded rules is that they generalize well-known description logics (DLs). All the DLs of the DL-Lite family in (Calvanese et al. 2007; Poggi et al. 2008) and the DL ELHI (Baader, Brandt, and Lutz 2005) can be embedded into guarded Datalog± (Calı̀, Gottlob, and Lukasiewicz 2012). In particular, this holds for DL-LiteR, the theoretical basis of the QL profile of the Web ontology language OWL 2. To appreciate how easily DL axioms can be transformed into Datalog±, note that rule (1) can be written as ∃EmpProj u BaseLevel v ∃IsManagedBy. We tackle a long-standing open research problem and prove the decidability of query answering under the stable model semantics for guarded existential rules, where rule bodies may contain negated atoms, and provide complexity results. The results extend to guarded Datalog± with negation, and thus provide a natural and decidable stable model semantics to description logics such as ELHI and DL-LiteR. 1 1. 1

AIJ Journal 2014 Journal Article

The price of query rewriting in ontology-based data access

• Georg Gottlob
• Stanislav Kikot
• Roman Kontchakov
• Vladimir Podolskii
• Thomas Schwentick
• Michael Zakharyaschev

We give a solution to the succinctness problem for the size of first-order rewritings of conjunctive queries in ontology-based data access with ontology languages such as OWL 2 QL, linear Datalog ± and sticky Datalog ±. We show that positive existential and nonrecursive datalog rewritings, which do not use extra non-logical symbols (except for intensional predicates in the case of datalog rewritings), suffer an exponential blowup in the worst case, while first-order rewritings can grow superpolynomially unless NP ⊆ P / poly. We also prove that nonrecursive datalog rewritings are in general exponentially more succinct than positive existential rewritings, while first-order rewritings can be superpolynomially more succinct than positive existential rewritings. On the other hand, we construct polynomial-size positive existential and nonrecursive datalog rewritings under the assumption that any data instance contains two fixed constants.

IJCAI Conference 2013 Conference Paper

Robust Constraint Satisfaction and Local Hidden Variables in Quantum Mechanics

• Samson Abramsky
• Georg Gottlob
• Phokion G. Kolaitis

Motivated by considerations in quantum mechanics, we introduce the class of robust constraint satisfaction problems in which the question is whether every partial assignment of a certain length can be extended to a solution, provided the partial assignment does not violate any of the constraints of the given instance. We explore the complexity of specific robust colorability and robust satisfiability problems, and show that they are NPcomplete. We then use these results to establish the computational intractability of detecting local hidden-variable models in quantum mechanics.

AAAI Conference 2012 Conference Paper

Equality-Friendly Well-Founded Semantics and Applications to Description Logics

• Georg Gottlob
• André Hernich
• Clemens Kupke
• Thomas Lukasiewicz

We tackle the problem of defining a well-founded semantics for Datalog rules with existentially quantified variables in their heads and negations in their bodies. In particular, we provide a well-founded semantics (WFS) for the recent Datalog± family of ontology languages, which covers several important description logics (DLs). To do so, we generalize Datalog± by non-stratified nonmonotonic negation in rule bodies, and we define a WFS for this generalization via guarded fixed-point logic. We refer to this approach as equality-friendly WFS, since it has the advantage that it does not make the unique name assumption (UNA); this brings it close to OWL and its profiles as well as typical DLs, which also do not make the UNA. We prove that for guarded Datalog± with negation under the equality-friendly WFS, conjunctive query answering is decidable, and we provide precise complexity results for this problem. From these results, we obtain precise definitions of the standard WFS extensions of EL and of members of the DL-Lite family, as well as corresponding complexity results for query answering.

AIJ Journal 2012 Journal Article

On minimal constraint networks

• Georg Gottlob

In a minimal binary constraint network, every tuple of a constraint relation can be extended to a solution. The tractability or intractability of computing a solution to such a minimal network was a long standing open question. Dechter conjectured this computation problem to be NP-hard. We prove this conjecture. We also prove a conjecture by Dechter and Pearl stating that for k ⩾ 2 it is NP-hard to decide whether a single constraint can be decomposed into an equivalent k-ary constraint network. We show that this holds even in case of bi-valued constraints where k ⩾ 3, which proves another conjecture of Dechter and Pearl. Finally, we establish the tractability frontier for this problem with respect to the domain cardinality and the parameter k.

MFCS Conference 2012 Conference Paper

On the Complexity of Ontological Reasoning under Disjunctive Existential Rules

• Georg Gottlob
• Marco Manna
• Michael Morak
• Andreas Pieris

Abstract Ontology-based data access is an emerging yet powerful technology that allows to enhance a classical relational database with an ontology in order to infer new intensional knowledge. Recently, Datalog+/- was introduced with the purpose of providing tractable reasoning algorithms for expressive ontology languages. In this framework, Datalog is extended by features such as existential quantification in rule heads, and at the same time the rule syntax is restricted to guarantee decidability, and also tractability, of relevant reasoning tasks. In this paper, we enrich Datalog even more by allowing not only existential quantification but also disjunction in rule heads, and we investigate the complexity of reasoning under the obtained formalism.

KR Conference 2012 Conference Paper

Rewriting Ontological Queries into Small Nonrecursive Datalog Programs

• Georg Gottlob
• Thomas Schwentick

with tractable query-answering have been designed, including OWL 2 QL (Grau et al. 2008; Pérez-Urbina, Horrocks, and Motik 2009), which is an OWL-based equivalent of the description logic DL-LiteR (Calvanese et al. 2007). While experimental and commercial ontological database management systems have existed and have been used for a number of years (e. g. (Chong et al. 2005; Acciarri et al. 2005; Virgilio et al. 2011)), they have been problematic with respect to performance, and there is an agreement that ontological query optimization methods have not yet been developed to their full potential. In fact, there is a general feeling that many issues of ontology querying are still not well understood, and that deep theoretical research is necessary to better understand some fundamental issues of query rewriting. In this spirit, the present paper tries to shed light on a relevant problem in this context: Is it at all possible to translate an ontological conjunctive query into a polynomially sized SQL (or SQL-DDL) query? We consider the setting of ontological database access, where an A-box is given in form of a relational database D and where a Boolean conjunctive query q has to be evaluated against D modulo a T -box Σ formulated in DL-Lite or Linear Datalog±. It is well-known that (Σ, q) can be rewritten into an equivalent nonrecursive Datalog program P that can be directly evaluated over D. However, for Linear Datalog± or for DL-Lite versions that allow for role inclusion, the rewriting methods described so far result in a nonrecursive Datalog program P of size exponential in the joint size of Σ and q. This gives rise to the interesting question of whether such a rewriting necessarily needs to be of exponential size. In this paper we show that it is actually possible to translate (Σ, q) into a polynomially sized equivalent nonrecursive Datalog program P. 1 1. 1

AIJ Journal 2012 Journal Article

Towards more expressive ontology languages: The query answering problem

• Andrea Cali`
• Georg Gottlob
• Andreas Pieris

Ontology reasoning finds a relevant application in the so-called ontology-based data access, where a classical extensional database (EDB) is enhanced by an ontology, in the form of logical assertions, that generates new intensional knowledge which contributes to answering queries. In this setting, queries are therefore answered against a logical theory constituted by the EDB and the ontology; more specifically, query answering amounts to computing the answers to the query that are entailed by the EDB and the ontology. In this paper, we study novel relevant classes of ontological theories for which query answering is both decidable and of tractable data complexity, that is, the complexity with respect to the size of the data only. In particular, our new classes belong to the recently introduced family of Datalog-based languages, called Datalog±. The basic Datalog± rules are (function-free) Horn rules extended with existential quantification in the head, known as tuple-generating dependencies (TGDs). We propose the language of sticky sets of TGDs (or sticky Datalog±), which are sets of TGDs with a restriction on multiple occurrences of variables in the rule-bodies. We establish complexity results for answering conjunctive queries under sticky sets of TGDs, showing, in particular, that queries can be compiled into domain independent first-order (and thus translatable into SQL) queries over the given EDB. We also present several extensions of sticky sets of TGDs, and investigate the complexity of query answering under such classes. In summary, we obtain highly expressive and effective ontology languages that unify and generalize both classical database constraints, and important features of the most widespread tractable description logics; in particular, the DL-Lite family of description logics.

AAAI Conference 2011 Conference Paper

New Expressive Languages for Ontological Query Answering

• Andrea Calì
• Georg Gottlob
• Andreas Pieris

Ontology-based data access is a powerful form of extending database technology, where a classical extensional database (EDB) is enhanced by an ontology that generates new intensional knowledge which may contribute to answer a query. Recently, the Datalog± family of ontology languages was introduced; in Datalog±, rules are tuple-generating dependencies (TGDs), i. e. , Datalog rules with the possibility of having existentially-quantified variables in the head. In this paper we introduce a novel Datalog± language, namely sticky sets of TGDs, which allows for a wide class of joins in the body, while enjoying at the same time a low query-answering complexity. We establish complexity results for answering conjunctive queries under sticky sets of TGDs, showing, in particular, that ontological conjunctive queries can be compiled into first-order and thus SQL queries over the given EDB instance. We also show some extensions of sticky sets of TGDs, and how functional dependencies and so-called negative constraints can be added to a sticky set of TGDs without increasing the complexity of query answering. Our language thus properly generalizes both classical database constraints and most widespread tractable description logics.

IJCAI Conference 2011 Conference Paper

Tackling the Partner Units Configuration Problem

• Markus Aschinger
• Conrad Drescher
• Georg Gottlob
• Peter Jeavons
• Evgenij Thorstensen

The Partner Units Problem is a specific type of configuration problem with important applications in the area of surveillance and security. In this work we show that a special case of the problem, that is of great interest to our partners in industry, can directly be tackled via a structural problem decompostion method. Combining these theoretical insights with general purpose AI techniques such as constraint satisfaction and SAT solving proves to be particularly effective in practice.

MFCS Conference 2010 Conference Paper

Balanced Queries: Divide and Conquer

• Dmitri Akatov
• Georg Gottlob

Abstract We define a new hypergraph decomposition method called Balanced Decomposition and associate Balanced Width to hypergraphs and queries. We compare this new method to other well known decomposition methods, and analyze the complexity of finding balanced decompositions of bounded width and the complexity of answering queries of bounded width. To this purpose we define a new complexity class, allowing recursive divide and conquer type algorithms, as a resource-bounded class in the nondeterministic auxiliary stack automaton computation model, and show that finding decompositions of bounded balanced width is feasible in this new class, whereas answering queries of bounded balanced width is complete for it.

AIJ Journal 2010 Journal Article

Bounded treewidth as a key to tractability of knowledge representation and reasoning

• 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 problems are on the second or third level of the polynomial hierarchy. In this paper, we show how the notion of treewidth can be fruitfully applied to this area. In particular, we show that all these problems become tractable (actually, even solvable in linear time), if the treewidth of the involved formulae or programs is bounded by some constant. Clearly, these theoretical tractability results as such do not immediately yield feasible algorithms. However, we have recently established a new method based on monadic datalog which allowed us to design an efficient algorithm for a related problem in the database area. In this work, we exploit the monadic datalog approach to construct new algorithms for logic-based abduction.

AAAI Conference 2010 Conference Paper

Ontological Reasoning with F-logic Lite and its Extensions

• Andrea Cali
• Georg Gottlob
• Michael Kifer
• Thomas Lukasiewicz
• Andreas Pieris

AAAI Conference 2008 Conference Paper

Abduction with Bounded Treewidth: From Theoretical Tractability to Practically Efficient Computation

• Georg Gottlob

Abductive diagnosis is an important method to identify explanations for a given set of observations. Unfortunately, most of the algorithmic problems in this area are intractable. We have recently shown (Gottlob, Pichler, and Wei 2006) that these problems become tractable if the underlying clausal theory has bounded treewidth. However, turning these theoretical tractability results into practically efficient algorithms turned out to be very problematical. In (Gottlob, Pichler, and Wei 2007), we have established a new method based on monadic datalog which remedies this unsatisfactory situation. Specifically, we designed an efficient algorithm for a strongly related problem in the database area. In the current paper, we show that these favorable results can be carried over to logic-based abduction.

JELIA Conference 2008 Conference Paper

Query Answering in the Description Logic Horn-

• Thomas Eiter
• Georg Gottlob
• Magdalena Ortiz 0001
• Mantas Simkus

Abstract We provide an ExpTime algorithm for answering conjunctive queries (CQs) in Horn - \(\mathcal{SHIQ}\), a Horn fragment of the well-known Description Logic \(\mathcal{SHIQ}\) underlying the OWL-Lite standard. The algorithm employs a domino system for model representation, which is constructed via a worst-case optimal tableau algorithm for Horn - \(\mathcal{SHIQ}\); the queries are answered by reasoning over the domino system. Our algorithm not only shows that CQ answering in Horn - \(\mathcal{SHIQ}\) is not harder than satisfiability testing, but also that it is polynomial in data complexity, making Horn - \(\mathcal{SHIQ}\) an attractive expressive Description Logic.

KR Conference 2008 Conference Paper

Taming the Infinite Chase: Query Answering under Expressive Relational Constraints

• Andrea Cali
• Georg Gottlob
• Michael Kifer

A crucial task in Knowledge Representation is answering queries posed over a knowledge base, represented as a set of facts plus a set of rules. In this paper we address the problem of answering conjunctive queries posed over knowledge bases where rules are an extension of Datalog rules, and may have existentially quantified variables in the head; this kind of rules are traditionally called tuple-generating dependencies (TGDs) in the database literature, but they are broadly used in description logics and in ontological reasoning. In this setting, the chase algorithm is an important tool for query answering. So far, most of the research has concentrated on cases where the chase terminates. We define and study large classes of TGDs under which the query evaluation problems remain decidable even in case the chase does not terminate. We provide tight complexity bounds for such cases. Our results immediately extend to query containment.

IJCAI Conference 2007 Conference Paper

• 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 particular, we show that this is NP-complete in general Bayesian Games in Standard Normal Form, and that it becomes PP-hard (and, in fixed-precision scenarios, PP-complete), when the game is represented succinctly in General Normal Form. Suitable restrictions in case of graphical games that make the problem tractable are also discussed.

IJCAI Conference 2007 Conference Paper

• Georg Gottlob
• Gianluigi Greco
• Toni Mancini

Conditional Constraint Satisfaction Problems (CCSPs) are generalizations of classical CSPs that support conditional activation of variables and constraints. Despite the interest emerged for CCSPs in the context of modelling the intrinsic dynamism of diagnosis, structural design, and product configuration applications, a complete characterization of their computational properties and of their expressiveness is still missing. In fact, the aim of the paper is precisely to face these open research issues. First, CCSPs are formally characterized in terms of a suitable fragment of first-order logic. Second, the complexity of some basic reasoning tasks for CCSPs is studied, by establishing completeness results for the first and the second level of the polynomial hierarchy. Finally, motivated by the hardness results, an island of tractability for CCSPs is identified, by extending structural decomposition methods originally proposed for CSPs.

AAAI Conference 2007 Conference Paper

Efficient Datalog Abduction through Bounded Treewidth

• Georg Gottlob

Abductive diagnosis is an important method for identifying possible causes which explain a given set of observations. Unfortunately, abduction suffers from the fact that most of the algorithmic problems in this area are intractable. We have recently obtained very promising results for a strongly related problem in the database area. Specifically, the PRIMALITY problem becomes efficiently solvable and highly parallelizable if the underlying functional dependencies have bounded treewidth (Gottlob, Pichler, & Wei 2006b). In the current paper, we show that these favorable results can be carried over to logic-based abduction. In fact, we even show a further generalization of these results.

AAAI Conference 2006 Conference Paper

Bounded Treewidth as a Key to Tractability of Knowledge Representation and Reasoning

• Georg Gottlob

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 problems are on the second or third level of the polynomial hierarchy. In this paper, we show how the powerful notion of treewidth can be fruitfully applied to this area. In particular, we show that all these problems become tractable (actually, even solvable in linear time), if the treewidth of the involved formulae (or of the disjunctive logic programs, resp.) is bounded by some constant. Experiments with a prototype implementation prove the feasibility of this new approach, in principle, and also give us hints for necessary improvements. In many areas of computer science, bounded treewidth has been shown to be a realistic and practically relevant restriction. We thus argue that bounded treewidth is a key factor in the development of efficient algorithms also in knowledge representation and reasoning – despite the high worst case complexity of the problems of interest.

TCS Journal 2006 Journal Article

Reasoning under minimal upper bounds in propositional logic

• Thomas Eiter
• Georg Gottlob

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 it appears, minimal models may not always be suitable to capture the intuitive semantics of a knowledge base, aiming intuitively at an exclusive interpretation of disjunctions of atoms, i. e. , if possible then assign at most one of the disjuncts the value true in a model. In this paper, we consider an approach which is more lenient and also admits non-minimal models, such that inclusive interpretation of disjunction also may be possible in cases where minimal model reasoning adopts an exclusive interpretation. Nonetheless, in the spirit of minimization, the approach aims at including only positive information that is necessary. This is achieved by closing the set of admissible models of a theory under minimal upper bounds in the set of models of the theory, which we refer to as curbing. We demonstrate this method on some examples, and investigate its semantical and computational properties. We establish that curbing is an expressive reasoning method, since the main reasoning tasks are shown to be PSPACE-complete. On the other hand, we also present cases of lower complexity, and in particular cases in which the complexity is located, just as for ordinary minimal model reasoning, at the second level of the Polynomial Hierarchy, or even below.

IJCAI Conference 2005 Conference Paper

The Complexity of Quantified Constraint Satisfaction Problems under Structural Restrictions

• Georg Gottlob
• Gianluigi Greco
• Francesco

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 QCSP satisfiability remains PSPACE-hard for all known structural properties more general than bounded treewidth and for the incomparable hypergraph acyclicity. Moreover, if the domain is not fixed, the problem is PSPACE-hard even for tree-shaped constraint scopes. On the positive side, we identify relevant tractable classes, including QCSPs with prefix ∃∀ having bounded hypertree width, and QCSPs with a bounded number of guards. The latter are solvable in polynomial time without any bound on domains or quantifier alternations.

I&C Journal 2003 Journal Article

On the complexity of single-rule datalog queries

• Georg Gottlob
• Christos Papadimitriou

Datalog programs containing a unique rule and possibly some facts are known as single rule programs, or sirups. We study the complexity of evaluating sirups over variable and fixed databases, respectively, as well as the descriptive complexity of sirups, i. e. , their expressive power. In all cases it turns out that even very restricted classes of sirups have the same complexity and essentially the same expressive power as general datalog programs. In particular, the evaluation of single clause programs is EXPTIME complete (combined complexity) and, if restricted to linear recursive rules, PSPACE complete. Moreover, sirups with one recursive rule and one fact capture PTIME on ordered structures, if a certain data representation is assumed and certain predefined relations are provided. We also prove that the datalog clause implication problem, i. e. , deciding whether a datalog clause implies another one, is EXPTIME complete. Our main technical tool is a product construction which maps a datalog programs to an essentially equivalent sirup.

TARK Conference 2003 Conference Paper

Pure Nash equilibria: hard and easy games

• 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 Equilibrium is NP-hard, while deciding whether a game has a strong Nash equilibrium is St-complete. We then study practically relevant restrictions that lower the complexity. In particular, we are interested in quantitative and qualitative restrictions of the way each player's move depends on moves of other players. We say that a game has small neighborhood if the " utility function for each player depends only on (the actions of) a logarithmically small number of other players, The dependency structure of a game G can he expressed by a graph G(G) or by a hypergraph I-I(G). Among other results, we show that if jC has small neighborhood and if I-I(G) has botmdecl hypertree width (or if G(G) has bounded treewidth), then finding pure Nash and Pareto equilibria is feasible in polynomial time. If the game is graphical, then these problems are LOGCFL-complete and thus in the class _NC~of highly parallelizable problems.

ECAI Conference 2002 Conference Paper

Combining hypertree, bicomp, and hinge decomposition

• Georg Gottlob
• Martin Hutle
• Franz Wotawa

TCS Journal 2002 Journal Article

Computing LOGCFL certificates

• Georg Gottlob
• Nicola Leone
• Francesco Scarcello

The complexity class LOGCFL consists of all languages (or decision problems) which are logspace reducible to a context-free language. Since LOGCFL is included in AC 1, the problems in LOGCFL are highly parallelizable. By results of Ruzzo (JCSS 21 (1980) 218), the complexity class LOGCFL can be characterized as the class of languages accepted by alternating Turing machines (ATMs) which use logarithmic space and have polynomially sized accepting computation trees. We show that for each such ATM M recognizing a language A in LOGCFL, it is possible to construct an L LOGCFL transducer TM such that TM on input w∈A outputs an accepting tree for M on w. It follows that computing single LOGCFL certificates is feasible in functional AC 1 and is thus highly parallelizable. Wanke (J. Algorithms 16 (1994) 470) has recently shown that for any fixed k, deciding whether the treewidth of a graph is at most k is in the complexity-class LOGCFL. As an application of our general result, we show that the task of computing a tree-decomposition for a graph of constant treewidth is in functional LOGCFL, and thus in AC 1. We also show that the following tasks are all highly parallelizable: Computing a solution to an acyclic constraint satisfaction problem; computing an m-coloring for a graph of bounded treewidth; computing the chromatic number and minimal colorings for graphs of bounded tree- width.

AIJ Journal 2002 Journal Article

Fixed-parameter complexity in AI and nonmonotonic reasoning

• Georg Gottlob
• Francesco Scarcello
• Martha Sideri

Many relevant intractable problems become tractable if some problem parameter is fixed. However, various problems exhibit very different computational properties, depending on how the runtime required for solving them is related to the fixed parameter chosen. The theory of parameterized complexity deals with such issues, and provides general techniques for identifying fixed-parameter tractable and fixed-parameter intractable problems. We study the parameterized complexity of various problems in AI and nonmonotonic reasoning. We show that a number of relevant parameterized problems in these areas are fixed-parameter tractable. Among these problems are constraint satisfaction problems with bounded treewidth and fixed domain, restricted forms of conjunctive database queries, restricted satisfiability problems, propositional logic programming under the stable model semantics where the parameter is the dimension of a feedback vertex set of the program's dependency graph, and circumscriptive inference from a positive k-CNF restricted to models of bounded size. We also show that circumscriptive inference from a general propositional theory, when the attention is restricted to models of bounded size, is fixed-parameter intractable and is actually complete for a novel fixed-parameter complexity class.

JELIA Conference 2002 Invited Paper

Hypergraph Transversal Computation and Related Problems in Logic and AI

• Thomas Eiter
• Georg Gottlob

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 variant, i. e. , the recognition of the transversal hypergraph for another hypergraph. We survey some results on problems which are known to be related to computing the transversal hypergraph, where we focus on problems in propositional Logic and AI. Some of the results have been established already some time ago, and were announced but their derivation was not widely disseminated. We then address recent developments on the computational complexity of computing resp. recognizing the transversal hypergraph. The precise complexity of these problems is not known to date, and is in fact open for more than 20 years now.

STOC Conference 2002 Conference Paper

New results on monotone dualization and generating hypergraph transversals

• Thomas Eiter
• Georg Gottlob
• Kazuhisa Makino

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 NP -completeness. We present a number of new polynomial time resp. output-polynomial time results for significant cases, which largely advance the tractability frontier and improve on previous results. Furthermore, we show that duality of two monotone CNFs can be disproved with limited nondeterminism (more precisely, in polynomial time with $O(\log^2 n)$ suitably guessed bits). This result sheds new light on the complexity of this important problem.

TCS Journal 2002 Journal Article

Propositional default logics made easier: computational complexity of model checking

• Robert Baumgartner
• Georg Gottlob

Liberatore and Schaerf (Proceedings of the ECAI’ 98, 1998) give a proof that model checking for propositional normal default theories is in Δ 2 P and Δ2 P[O(log n)]-hard. However, the precise complexity is left as an open problem. We solve this problem by proving that model checking for normal default theories is complete for Δ2 P[O(log n)]. This is the class of decision problems solvable in polynomial time with a logarithmic number of calls to an oracle in NP. Additionally, we analyse the computational cost of model checking w. r. t. weak extensions, stable expansions and N -expansions and take a look at the complexity of model checking for disjunction-free default theories. Furthermore, we show that not only for disjunction-free default theories, but also for a larger class of default theories, which we call default theories in extended Horn normal form, the complexity of model checking is, in the case of normal default theories, tractable. Additionally, the complexity results are used to draw some interesting conclusions on translatability issues. In particular, there exists no function from default logic into logic programming which is polynomial, faithful and modular unless coNP =Σ2 P. Finally, we give an overview of our results concerning model checking in case of disjunctive default logic and stationary default logic.

JELIA Conference 2002 Conference Paper

The DLV System

• Nicola Leone
• Gerald Pfeifer
• Wolfgang Faber 0001
• Francesco Calimeri
• Tina Dell'Armi
• Thomas Eiter
• Georg Gottlob
• Giovambattista Ianni

Abstract The development of the DLV system has started as a research projectfinanced by FWF (the Austrian Science Funds) in 1996, and has evolved into an international collaboration over the years. Currently, the University of Calabria and TU Wien participate in the project, supported by a scientific-technological collaboration between Italy and Austria. At the time of writing, the latest version of the system has been released on April 12, 2002.

NMR Workshop 2002 Conference Paper

Visual Data Extraction Through Visual Logic Programming

• Georg Gottlob

more precisely, a datalog Program, whose rules describe the patterns to be extracted. The program (aka wrapper) can then be applied to similarily structured Web pages for extracting the appropriate patterns and translating them into XML. In the second part of the talk, some theoretical issues on Lixto will be presented. We will show that Lixto expresses monadic second order logic over trees (i.e., Parsing trees of Web Pages). Moreover, we will discuss some challenges for nonmonotonic reasoning related to information extraction. More information on Lixto can be found at www.lixto.com or www.lixto.net.

MFCS Conference 2001 Invited Paper

Hypertree Decompositions: A Survey

• Georg Gottlob
• Nicola Leone
• 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 tree decomposition of a graph) is a suitable clustering of its hyperedges yielding a tree or a forest. Important NP hard problems become tractable if restricted to instances whose associated hypergraphs are of bounded hypertree width. We also review a number of complexity results on problems whose structure is described by acyclic or nearly acyclic hypergraphs.

LPAR Conference 2001 Conference Paper

The Elog Web Extraction Language

• Robert Baumgartner
• Sergio Flesca
• Georg Gottlob

Abstract This paper illustrates some aspects of the visual wrapper generation tool Lixto and describes its internal declarative logic-based language Elog. In particular, it gives an example scenarioand contains a detailed description of predicates including their input/output behavior and introduces several new conditions. Additionally, entity relationship diagrams of filters and patterns are depicted and some words on the implementation are issued. Finally, some possible ramifications are discussed.

I&C Journal 2001 Journal Article

Working with ARMs: Complexity Results on Atomic Representations of Herbrand Models

• Georg Gottlob
• Reinhard Pichler

An atomic representation of a Herbrand model (ARM) is a finite set of (not necessarily ground) atoms over a given Herbrand universe. Each ARM represents a possibly infinite Herbrand interpretation. This concept has emerged independently in different branches of computer science as a natural and useful generalization of the concept of finite Herbrand interpretation. It was shown that several recursively decidable problems on finite Herbrand models (or interpretations) remain decidable on ARMs. The following problems are essential when working with ARMs: Deciding the equivalence of two ARMs, deciding subsumption between ARMs, and evaluating clauses over ARMs. These problems were shown to be decidable, but their computational complexity has remained obscure so far. The previously published decision algorithms require exponential space. In this paper, we prove that all mentioned problems are coNP-complete.

AIJ Journal 2000 Journal Article

A comparison of structural CSP decomposition methods

• 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 tractable CSPs based on the concept of hypertree decomposition recently developed in Database Theory, and analyze the cost of solving CSPs having bounded hypertree-width. We provide a framework for comparing parametric decomposition-based methods according to tractability criteria and compare the most relevant methods. We show that the method of hypertree decomposition dominates the others in the case of general CSPs (i. e. , CSPs of unbounded arity). We also make comparisons for the restricted case of binary CSPs. Finally, we consider the application of decomposition methods to the dual graph of a hypergraph. In fact, this technique is often used to exploit binary decomposition methods for nonbinary CSPs. However, even in this case, the hypertree-decomposition method turns out to be the most general method.

FOCS Conference 2000 Conference Paper

Existential Second-Order Logic over Graphs: Charting the Tractability Frontier

• Georg Gottlob
• Phokion G. Kolaitis
• Thomas Schwentick

Fagin's (1974) theorem, the first important result of descriptive complexity, asserts that a property of graphs is in NP if and only if it is definable by an existential second-order formula. We study the complexity of evaluating existential second-order formulas that belong to prefix classes of existential second-order logic, where a prefix class is the collection of all existential second-order and the first-order quantifiers obey a certain quantifier pattern. We completely characterize the computation complexity of prefix classes of existential second-order logic in three different contexts: over directed graphs; over undirected graphs with self-loops; and over undirected graphs without self-loops. Our main result is that in each of these three contexts a dichotomy holds, i. e. , each prefix class of existential second-order logic either contains sentences that can express NP-complete problems or each of its sentences expresses a polynomial-time solvable problem. Although the boundary of the dichotomy coincides for the first two cases, it changes, as one move to undirected graphs without self-loops.

LPAR Conference 2000 Conference Paper

On the Complexity of Theory Curbing

• Thomas Eiter
• Georg Gottlob

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 circumscription treats disjunction inclusively. In an earlier paper, theory curbing was shown to be feasible in PSPACE, but the precise complexity was left open. In the present paper we prove it to be PSPACE-complete. In particular, we show that both the model checking and the inferencing problem under curbed theories are PSPACE complete. We also study relevant cases where the complexity of theory curbing is located - just as for plain propositional circumscription - at the second level of the polynomial hierarchy and is thus presumably easier than PSPACE.

IJCAI Conference 1999 Conference Paper

A Comparison of Structural CSP Decomposition Methods

• Georg Gottlob
• Nicola Leone
• Francesco Scarcello

AIJ Journal 1999 Journal Article

Enhancing model checking in verification by AI techniques

• 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 concurrent system satisfies its formal specification, it can not precisely locate an error and suggest a repair, i. e. , a suitable correction, to the system. In this paper, we tackle this problem by using principles from AI. In particular, we introduce the abstract concept of a system repair problem, and exemplify this concept on repair of concurrent programs and protocols. For the development of our framework, we formally extend the concept ofcounterexample, which has been proposed in model checking previously, and provide examples which demonstrate the need for such an extension. Moreover, we investigate into optimization issues for the problem of finding a repair, and present techniques which gain in some cases a considerable reduction of the search space for a repair.

IJCAI Conference 1999 Conference Paper

On the Complexity of Model Checking for Propositional Default Logics: New Results and Tractable Cases

• 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 a new ample class of default theories with a tractable model checking problem.

LPAR Conference 1999 Conference Paper

On the Complexity of Single-Rule Datalog Queries

• Georg Gottlob
• Christos H. Papadimitriou

Abstract Datalog is a well-known database query language based on the logic programming paradigm. A general datalog program consists of a number of rules and facts. Programs containing a unique rule and possibly some facts are called single rule programs (sirups). We study both the combined and the program complexity of sirups, ie. , the complexity of evaluating sirups over variable and fixed databases, respectively. Moreover, we study the descriptive complexity of sirups, i. e. , their expressive power. In all cases it turns out that even very restricted classes of sirups have the same complexity and essentially the same expressive power as general datalog programs. We show that the evaluation of single clause programs is EXPTIME complete (combined complexity), and, if restricted to linear recursive rules, PSPACE complete. Moreover, sirups with one recursive rule and one additional fact capture PTIME on ordered structures, if a certain data representation is assumed and certain predefined relations are provided. Our results are obtained by a uniform product construction which maps a datalog program into a single rule by essentially maintaining its semantics. We also prove that the datalog clause implication problem, i. e. , deciding whether a datalog clause implies another one, is EXPTIME complete.

TCS Journal 1998 Journal Article

Foreword

• Georg Gottlob
• Moshe Y. Vardi

FOCS Conference 1998 Conference Paper

The Complexity of Acyclic Conjunctive Queries

• Georg Gottlob
• Nicola Leone
• Francesco Scarcello

We show that the problem of evaluating acylic Boolean database-queries is LOGCFL-complete and thus highly parallelizable. We present a parallel database algorithm solving this problem with a logarithmic number of parallel join operations. It follows from our main result that the acylic versions of the following important database and Al problems are LOGCFL-complete: The query output tuple problem for conjunctive queries, conjunctive query containment, clause subsumption, and constraint satisfaction.

TCS Journal 1997 Journal Article

Abduction from logic programs: Semantics and complexity

• 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 in different areas of computer science; in particular, it has been recognized as an important principle of common-sense reasoning. In this paper, we define a general abduction model for logic programming, where the inference operator (i. e. , the semantics to be applied on programs), can be specified by the user. Advanced forms of logic programming have been proposed as valuable tools for knowledge representation and reasoning. We show that logic programming semantics can be more meaningful for abductive reasoning than classical inference by providing examples from the area of knowledge representation and reasoning. The main part of the paper is devoted to an extensive study of the computational complexity of the principal problems in abductive reasoning, which are: Given an instance of an abduction problem (1) does the problem have solution (i. e. , an explanation); (2) does a given hypothesis belong to some explanation; and (3) does a given hypothesis belong to all explanations. This problems are analyzed for different underlying logic programming semantics, namely, the well-founded semantics, the stable model semantics and the minimal model semantics, paying attention to normal and disjunctive logic programs for the case of propositional as well as function-free first-order programs. The main results are that the above abductive reasoning tasks on propositional logic programs populate the classes at the lower end of the polynomial hierarchy up to ∑4 p, and provide complete problems for a number of classes over the first four levels of the hierarchy. Similar results are obtained in the first-order case. This proves abduction from logic programs as a rich source of problems of varying complexity.

AIJ Journal 1997 Journal Article

Semantics and complexity of abduction from default theories

• 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 representation is commonly based on nonclassical formalisms like default logic, autoepistemic logic, or circumscription, it is necessary to perform abductive reasoning from theories (i. e. , knowledge bases) of nonclassical logics. In this paper, we investigate how abduction can be performed from theories in default logic. In particular, we present a basic model of abduction from default theories. Different modes of abduction are plausible, based on credulous and skeptical default reasoning; they appear useful for different applications such as diagnosis and planning. Moreover, we thoroughly analyze the complexity of the main abductive reasoning tasks, namely finding an explanation, deciding relevance of a hypothesis and deciding necessity of a hypothesis. These problems are intractable even in the prepositional case and we locate them into the appropriate slots of the polynomial hierarchy. However, we also present known classes of default theories for which abduction is tractable. Moreover, we also consider first-order default theories, based on domain closure and the unique names assumption. In this setting, the abduction tasks are decidable, but have exponentially higher complexity than in the propositional case.

TCS Journal 1996 Journal Article

A non-ground realization of the stable and well-founded semantics

• Georg Gottlob
• Sherry Marcus
• Anil Nerode
• Gernot Salzer
• 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 ground stable model may also be very large. We develop a non-ground semantic theory for non-monotonic logic programming. Its principal advantage is that stable models and well-founded models can be represented as sets of atoms, rather than as sets of ground atoms. A set SI of atoms may be viewed as a compact representation of the Herbrand interpretation consisting of all ground instances of atoms in SI. We develop generalizations of the stable and well-founded semantics based on such non-ground interpretations SI. The key notions for our theory are those of covers and anticovers. A cover as well as its anticover are sets of substitutions — non-ground in general — representing all substitutions obtained by ground instantiating some substitution in the (anti)cover, with the additional requirement that each ground substitution is represented either by the cover or by the anticover, but not by both. We develop methods for computing anticovers for a given cover, show that membership in so-called optimal covers is decidable, and investigate the complexity in the Datalog case.

MFCS Conference 1995 Invited Paper

Second Order Logic and the Weak Exponential Hierarchies

• Georg Gottlob
• Nicola Leone
• Helmut Veith

Abstract Second order logic over finite structures is well-known to capture the levels of the polynomial hierarchy PH. Recently, it has been shown that Θ 1 k — the first order closure of second order Σ 1 m — captures the class Θ P k = \(L^{\Sigma _k^P }\), a natural intermediate class of the polynomial hierarchy [12]. In this paper we show that with respect to expression complexity, second order logic characterizes the levels of the weak exponential hierarchy EH. Moreover, we extend these results to intermediate classes EΘ P k in EH which correspond to the Θ P k classes in PH. To this end, in extending previous results, we show completeness under projection translations of certain quantified propositional formula languages for Θ P k. Those, as well as quantified Boolean formulas are applied to improved complexity upgrade techniques based on the ”succinct input” paradigm. Thus, we obtain a uniform treatment for obtaining expression complexity results for a large number of natural languages. We exhibit examples from database theory and nonmonotonic reasoning. In particular, we investigate the expression complexity of first order logic with Henkin quantifiers and default logic.

IJCAI Conference 1995 Conference Paper

Semantics and Complexity of Abduction from Default Theories

• Thomas Titer
• 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 theories of nonclassical logics. In this paper, we investigate how abduction can be performed from theories in default logic. Different modes of abduction are plausible, based on credulous and skeptical default reasoning; they appear useful for different applications such as diagnosis and planning. Moreover, we analyze the complexity of the main abductive reasoning tasks. They are intractable in the general case; we also present known classes of default theories for which abduction is tractable.

AIJ Journal 1994 Journal Article

Cumulative default logic: Finite characterization, algorithms, and complexity

• Georg Gottlob
• Mingyi Zhang

Brewka's Cumulative Default Logic (CDL), a new version of Reiter's default logic, puts emphasis on the joint consistency among the justifications of all applied defaults to obtain cumulativity. In this paper, a finite characterization of CDL extensions using sets of generating defaults is given. From this characterization we derive new algorithms for various reasoning tasks in CDL. Moreover, we show that (propositional) cumulative default reasoning has the same complexity as classical default reasoning.

FOCS Conference 1993 Conference Paper

NP Trees and Carnap's Modal Logic

• Georg Gottlob

We consider problems and complexity classes definable by interdependent queries to an oracle in NP. How the queries depend on each other is specified by a directed graph G. We first study the class of problems where G is a general dag and show that this class coincides with /spl Delta//sub 2//sup P/. We then consider the class where G is a tree. Our main result states that this class is identical to P/sup NP/ [O(log n)], the class of problems solvable in polynomial time with a logarithmic number of queries to an oracle in NP. Using this result we show that the following problems are all P/sup NP/[O(logn)] complete: validity-checking of formulas in Carnap's modal logic, checking whether a formula is almost surely valid over finite structures in modal logics K, T, and S4, and checking whether a formula belongs to the stable set of beliefs generated by a propositional theory. >

TCS Journal 1993 Journal Article

Propositional circumscription and extended closed-world reasoning are ΠP2-complete

• Thomas Eiter
• Georg Gottlob

TCS Journal 1993 Journal Article

Propositional circumscription and extended closed-world reasoning are ΠP2-complete

• Thomas Eiter
• Georg Gottlob

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 studied in detail for fragments of propositional logic. One open problem is whether the deduction problem for arbitrary propositional theories under the extended closed-world assumption or under circumscription is ΠP 2-complete, i. e. , complete for a class of the second level of the polynomial hierarchy. We answer this question by proving these problems ΠP 2-complete, and we show how this result applies to other variants of closed-world reasoning.

AIJ Journal 1993 Journal Article

Removing redundancy from a clause

• Georg Gottlob
• Christian G. Fermüller

This paper deals with the problem of removing redundant literals from a given clause. We first consider condensing, a weak type of redundancy elimination. A clause is condensed if it does not subsume any proper subset of itself. It is often useful (and sometimes necessary) to replace a non-condensed clause C by a condensation, i. e. , by a condensed subset of C which is subsumed by C. After studying the complexity of an existing clause condensing algorithm, we present a more efficient algorithm and provide arguments for the optimality of the new method. We prove that testing whether a given clause is condensed is co-NP-complete and show that several problems related to clause condensing belong to complexity classes that are, probably, slightly harder than NP. We also consider a stronger version of redundancy elimination: a clause C is strongly condensed iff it does not contain any proper subset C′ such that C logically implies C′. We show that the problem of testing whether a clause is strongly condensed is undecidable.

IJCAI Conference 1993 Conference Paper

The Complexity of Nested Counterfactuals and Iterated Knowledge Base Revisions

• Thomas Eiter
• Georg Gottlob

We consider the computational complexity of evaluating nested counterfactuals over a propositional knowledge base. Counterfactual implication models a statement "if p, then q, " where p is known or expected to be false, and is different from material implication A nested counterfactual is a counterfactual statement where the conclusion q is a (possibly negated) counterfactual. Statements of the form intuitively correspond to hypothetical queries involving a sequence of revisions. We show that evaluating such statements is complete, and that this task becomes PSPACE-cornplete if negation is allowed in the nesting. We also consider nesting a counterfactual in the premise, i. e. and show that evaluating such statements is most likely much harder than evaluating

IJCAI Conference 1993 Conference Paper

The Power of Beliefs or Translating Default Logic Into Standard Autoepistemic Logic

• Georg Gottlob

AIJ Journal 1992 Journal Article

An efficient method for eliminating varying predicates from a circumscription

• 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 (floating) predicates. We show that the inference problem under this form of circumscription is efficiently reducible to inferencing under circumscription without varying predicates. In fact, we transform this problem even into circumscription without fixed and varying predicates, that is where all predicates are minimized. Thus any theorem prover or algorithm for inferencing under circumscription without fixed and varying predicates is able to handle inferencing under the general form of predicate circumscription. As a consequence, algorithms that compute circumscription for an inference task can be simplified.

ECAI Conference 1992 Conference Paper

Formaiizing the Repair Process

• Gerhard Friedrich
• Georg Gottlob
• Wolfgang Nejdl

AIJ Journal 1992 Journal Article

On the complexity of propositional knowledge base revision, updates, and counterfactuals

• Thomas Eiter
• Georg Gottlob

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 for the following problem: given a knowledge base T, an update p, and a formula q, decide whether q is derivable from T ○ p, the updated (or revised) knowledge base. Note that this problem includes the evaluation of the counterfactual p > q over T, that is a conditional statement “if p, then q”, where p is known or expected to be false. We consider the general case where T is an arbitrary propositional formula (or theory) as well as restricted versions of this problem, in particular where T is a conjunction of Horn clauses, or where the size of the update p is bounded by a constant.