University of Oxford Logo University of OxfordDepartment of Computer Science - Home

Thomas Lukasiewicz: Abstracts of Publications

This page is no longer updated; please refer to the new page.

Refereed Journal Papers

Georg Gottlob, Thomas Lukasiewicz, Maria Vanina Martinez, and Gerardo I. Simari
Query Answering under Probabilistic Uncertainty in Datalog+/- Ontologies
Annals of Mathematics and Artificial Intelligence, 2013 (in press).

The recently introduced Datalog+/- family of ontology languages is especially useful for representing and reasoning over lightweight ontologies, and is set to play a central role in the context of query answering and information extraction for the Semantic Web. Recently, it has become apparent that it is necessary to develop a principled way to handle uncertainty in this domain. In addition to uncertainty as an inherent aspect of the Web, one must also deal with forms of uncertainty due to inconsistency and incompleteness, uncertainty resulting from automatically processing Web data, as well as uncertainty stemming from the integration of multiple heterogeneous data sources. In this paper, we take an important step in this direction by developing a probabilistic extension of Datalog+/-. This extension uses Markov logic networks as the underlying probabilistic semantics. Here, we focus especially on scalable algorithms for answering threshold queries, which correspond to the question "what is the set of all ground atoms that are inferred from a given probabilistic ontology with a probability of at least p?". These queries are especially relevant to Web information extraction, since uncertain rules lead to uncertain facts, and only information with a certain minimum confidence is desired. We present several algorithms, namely a basic approach, an anytime one, and one based on heuristics, which is guaranteed to return sound results. Furthermore, we also study inconsistency in probabilistic Datalog+/- ontologies. We propose two approaches for computing preferred repairs based on two different notions of distance between repairs, namely symmetric and score-based distance. We also study the complexity of the decision problems corresponding to computing such repairs, which turn out to be polynomial and NP-complete in the data complexity, respectively.

Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz
A General Datalog-Based Framework for Tractable Query Answering over Ontologies
Journal of Web Semantics, 14, 57-83, July 2012.

Ontologies and rules play a central role in the development of the Semantic Web. Recent research in this context focuses especially on highly scalable formalisms for the Web of Data, which may highly benefit from exploiting database technologies. In this paper, as a first step towards closing the gap between the Semantic Web and databases, we introduce a family of expressive extensions of Datalog, called Datalog+/-, as a new paradigm for query answering over ontologies. The Datalog+/- family admits existentially quantified variables in rule heads, and has suitable restrictions to ensure highly efficient ontology querying. We show in particular that different versions of Datalog+/- generalize the tractable description logic EL and the DL-Lite family of tractable description logics, which are the most common tractable ontology languages in the context of the Semantic Web and databases. We also show how stratified negation can be added to Datalog+/- while keeping ontology querying tractable. Furthermore, the Datalog+/- family is of interest in its own right, and can, moreover, be used in various contexts such as data integration and data exchange. It paves the way for applying results from databases to the context of the Semantic Web.

Claudia d'Amato, Nicola Fanizzi, Bettina Fazzinga, Georg Gottlob, and Thomas Lukasiewicz
Ontology-Based Semantic Search on the Web and its Combination with the Power of Inductive Reasoning
Annals of Mathematics and Artificial Intelligence, 65(2/3), 83-121, July 2012.

Semantic Web search is currently one of the hottest research topics in both Web search and the Semantic Web. In previous work, we have presented a novel approach to Semantic Web search, which allows for evaluating ontology-based complex queries that involve reasoning over the Web relative to an underlying background ontology. We have developed the formal model behind this approach, and provided a technique for processing Semantic Web search queries, which consists of an offline ontological inference step and an online reduction to standard Web search. In this paper, we continue this line of research. We further enhance the above approach by the use of inductive rather than deductive reasoning in the offline inference step. This increases the robustness of Semantic Web search, as it adds the important ability to handle inconsistencies, noise, and incompleteness, which are all very likely to occur in distributed and heterogeneous environments such as the Web. The inductive variant also allows to infer new (not logically deducible) knowledge (from training individuals). We report on a prototype implementation of (both the deductive and) the inductive variant of our approach in desktop search, and we provide extensive new experimental results, especially on the running time and the precision and the recall of our new approach.

Bettina Fazzinga, Giorgio Gianforme, Georg Gottlob, and Thomas Lukasiewicz
Semantic Web Search Based on Ontological Conjunctive Queries
Journal of Web Semantics, 9, 453-473, December 2011.

Many experts predict that the next huge step forward in Web information technology will be achieved by adding semantics to Web data, and will possibly consist of (some form of) the Semantic Web. In this paper, we present a novel approach to Semantic Web search, called Serene, which allows for a semantic processing of Web search queries, and for evaluating complex Web search queries that involve reasoning over the Web. More specifically, we first add ontological structure and semantics to Web pages, which then allows for both attaching a meaning to Web search queries and Web pages, and for formulating and processing ontology-based complex Web search queries (i.e., conjunctive queries) that involve reasoning over the Web. Here, we assume the existence of an underlying ontology (in a lightweight ontology language) relative to which Web pages are annotated and Web search queries are formulated. Depending on whether we use a general or a specialized ontology, we thus obtain a general or a vertical Semantic Web search interface, respectively. That is, we are actually mapping the Web into an ontological knowledge base, which then allows for Semantic Web search relative to the underlying ontology. The latter is then realized by reduction to standard Web search on standard Web pages and logically completed ontological annotations. That is, standard Web search engines are used as the main inference motor for ontology-based Semantic Web search. We develop the formal model behind this approach and also provide an implementation in desktop search. Furthermore, we report on extensive experiments, including an implemented Semantic Web search on the Internet Movie Database.

Thomas Lukasiewicz, Livia Predoiu, and Heiner Stuckenschmidt
Tightly Integrated Probabilistic Description Logic Programs for Representing Ontology Mappings
Annals of Mathematics and Artificial Intelligence, 63(3/4), 385-425, December 2011.

Creating mappings between ontologies is a common way of approaching the semantic heterogeneity problem on the Semantic Web. To fit into the landscape of Semantic Web languages, a suitable, logic-based representation formalism for mappings is needed. We argue that such a formalism has to be able to deal with uncertainty and inconsistencies in automatically created mappings. We analyze the requirements for such a formalism, and we propose a novel approach to probabilistic description logic programs as such a formalism, which tightly combines normal logic programs under the well-founded semantics with both tractable ontology languages and Bayesian probabilities. We define the language, and we show that it can be used to resolve inconsistencies and merge mappings from different matchers based on the level of confidence assigned to different rules. Furthermore, we explore the semantic and computational aspects of probabilistic description logic programs under the well-founded semantics. In particular, we show that the well-founded semantics approximates the answer set semantics. We also describe algorithms for consistency checking and tight query processing, and we analyze the data and general complexity of these two central computational problems. As a crucial property, the novel tightly integrated probabilistic description logic programs under the well-founded semantics allow for tractable consistency checking and for tractable tight query processing in the data complexity, and they have even a first-order rewritable (and thus LogSpace data complexity) special case, which is especially interesting for representing ontology mappings.

Andrea Calì, Georg Gottlob, Thomas Lukasiewicz, and Andreas Pieris
A Logical Toolbox for Ontological Reasoning
SIGMOD Record, 40(3), 5-14, September 2011.

In ontology-enhanced database systems, an ontology on top of the extensional database expresses intensional knowledge that enhances the database schema. Queries posed to such systems are to be evaluated considering all the knowledge inferred from the data by means of the ontology; in other words, queries are to be evaluated against the logical theory constituted by the data and the ontology. In this context, tractability of query answering is a central issue, given that the data size is normally very large. This paper surveys results on a recently introduced family of Datalog-based languages, called Datalog+/-, which is a useful logical toolbox for ontology modeling and for ontology-based query answering. We present different Datalog+/- languages and related complexity results, showing that Datalog+/- can be successfully adopted due to its clarity, expressiveness and its good computational properties.

Thomas Eiter, Giovambattista Ianni, Thomas Lukasiewicz, and Roman Schindlauer
Well-Founded Semantics for Description Logic Programs in the Semantic Web
ACM Transactions on Computational Logic (TOCL), 12(2), Article 11, January 2011.

The realization of the Semantic Web vision, in which computational logic has a prominent role, has stimulated a lot of research on combining rules and ontologies, which are formulated in different formalisms. In particular, combining logic programming with the Web Ontology Language (OWL), which is a standard based on description logics, emerged as an important issue for linking the Rules and Ontology Layers of the Semantic Web. Non-monotonic description logic programs (or dl-programs) were introduced for such a combination, in which a pair (L,P) of a description logic knowledge base L and a set of rules P with negation as failure is given a model-based semantics that generalizes the answer set semantics of logic programs. In this paper, we reconsider dl-programs and present a well-founded semantics for them as an analog for the other main semantics of logic programs. It generalizes the canonical definition of the well-founded semantics based on unfounded sets, and, as we show, lifts many of the well-known properties from ordinary logic programs to dl-programs. Among these properties: our semantics amounts to a partial model approximating the answer set semantics, which yields for positive and stratified dl-programs a total model coinciding with the answer set semantics; it has polynomial data complexity provided the access to the description logic knowledge base is polynomial; under suitable restrictions, it has lower complexity and even first-order rewritability is achievable. The results add to previous evidence that dl-programs are a versatile and robust combination approach, which moreover is implementable using legacy engines.

Bettina Fazzinga and Thomas Lukasiewicz
Semantic Search on the Web
Semantic Web, 1(1/2), 89-96, December 2010.

Web search is a key technology of the Web, since it is the primary way to access content on the Web. Current standard Web search is essentially based on a combination of textual keyword search with an importance ranking of the documents depending on the link structure of the Web. For this reason, it has many limitations, and there are a plethora of research activities towards more intelligent forms of search on the Web, called semantic search on the Web, or also Semantic Web search. In this paper, we give a brief overview of existing such approaches, including own ones, and sketch some possible future directions of research.

Thomas Lukasiewicz
A Novel Combination of Answer Set Programming with Description Logics for the Semantic Web
IEEE Transactions on Knowledge and Data Engineering (TKDE), 22(11), 1577-1592, November 2010.

We present a novel combination of disjunctive programs under the answer set semantics with description logics for the Semantic Web. The combination is based on a well-balanced interface between disjunctive programs and description logics, which guarantees the decidability of the resulting formalism without assuming syntactic restrictions. We show that the new formalism has very nice semantic properties. In particular, it faithfully extends both disjunctive programs and description logics. Furthermore, we describe algorithms for reasoning in the new formalism, and we give a precise picture of its computational complexity. We also define the well-founded semantics for the normal case, where normal programs are combined with tractable description logics, and we explore its semantic and computational properties. In particular, we show that the well-founded semantics approximates the answer set semantics. We also describe algorithms for the problems of consistency checking and literal entailment under the well-founded semantics, and we give a precise picture of their computational complexity. As a crucial property, in the normal case, consistency checking and literal entailment under the well-founded semantics are both tractable in the data complexity, and even first-order rewritable (and thus can be done in LogSpace in the data complexity) in a special case that is especially useful for representing mappings between ontologies.

Andrea Calì, Thomas Lukasiewicz, Livia Predoiu, and Heiner Stuckenschmidt
Tightly Coupled Probabilistic Description Logic Programs for the Semantic Web
Journal on Data Semantics, 12, 95-130, June 2009.

We present a novel approach to probabilistic description logic programs for the Semantic Web in which disjunctive logic programs under the answer set semantics are tightly coupled with description logics and Bayesian probabilities. The approach has several nice features. In particular, it is a logic-based representation formalism that naturally fits into the landscape of Semantic Web languages. Tightly coupled probabilistic description logic programs can especially be used for representing mappings between ontologies, which are a common way of approaching the semantic heterogeneity problem on the Semantic Web. In this application, they allow in particular for resolving inconsistencies and for merging mappings from different matchers based on the level of confidence assigned to different rules. Furthermore, tightly coupled probabilistic description logic programs also provide a natural integration of ontologies, action languages, and Bayesian probabilities towards Web Services. We explore the computational aspects of consistency checking and query processing in tightly coupled probabilistic description logic programs. We show that these problems are decidable and computable, respectively, and that they can be reduced to consistency checking and cautious/brave reasoning, respectively, in tightly coupled disjunctive description logic programs. Using these results, we also provide an anytime algorithm for tight query processing. Furthermore, we analyze the complexity of consistency checking and query processing in the new probabilistic description logic programs, and we present a special case of these problems with polynomial data complexity.

Thomas Lukasiewicz and Umberto Straccia
Description Logic Programs under Probabilistic Uncertainty and Fuzzy Vagueness
International Journal of Approximate Reasoning, 50(6), 837-853, June 2009.

This paper is directed towards an infrastructure for handling both uncertainty and vagueness in the Rules, Logic, and Proof layers of the Semantic Web. More concretely, we present probabilistic fuzzy description logic programs, which combine fuzzy description logics, fuzzy logic programs (with stratified default-negation), and probabilistic uncertainty in a uniform framework for the Semantic Web. We define important concepts dealing with both probabilistic uncertainty and fuzzy vagueness, such as the expected truth value of a crisp sentence and the probability of a vague sentence. Furthermore, we describe a shopping agent example, which gives evidence of the usefulness of probabilistic fuzzy description logic programs in realistic Web applications. We also provide algorithms for query processing in probabilistic fuzzy description logic programs, and we delineate a special case where query processing can be done in polynomial time in the data complexity.

Luca Iocchi, Thomas Lukasiewicz, Daniele Nardi, and Riccardo Rosati
Reasoning about Actions with Sensing under Qualitative and Probabilistic Uncertainty
ACM Transactions on Computational Logic (TOCL), 10(1), Article 5, January 2009.

We focus on the aspect of sensing in reasoning about actions under qualitative and probabilistic uncertainty. We first define the action language E for reasoning about actions with sensing, which has a semantics based on the autoepistemic description logic ALCK_NF, and which is given a formal semantics via a system of deterministic transitions between epistemic states. As an important feature, the main computational tasks in E can be done in linear and quadratic time. We then introduce the action language E+ for reasoning about actions with sensing under qualitative and probabilistic uncertainty, which is an extension of E by actions with nondeterministic and probabilistic effects, and which is given a formal semantics in a system of deterministic, nondeterministic, and probabilistic transitions between epistemic states. We also define the notion of a belief graph, which represents the belief state of an agent after a sequence of deterministic, nondeterministic, and probabilistic actions, and which compactly represents a set of unnormalized probability distributions. Using belief graphs, we then introduce the notion of a conditional plan and its goodness for reasoning about actions under qualitative and probabilistic uncertainty. We formulate the problems of optimal and threshold conditional planning under qualitative and probabilistic uncertainty, and show that they are both uncomputable in general. We then give two algorithms for conditional planning in our framework. The first one is always sound, and it is also complete for the special case in which the relevant transitions between epistemic states are cycle-free. The second algorithm is a sound and complete solution to the problem of finite-horizon conditional planning in our framework. Under suitable assumptions, it computes every optimal finite-horizon conditional plan in polynomial time. We also describe an application of our formalism in a robotic-soccer scenario, which underlines its usefulness in realistic applications.

Thomas Lukasiewicz and Umberto Straccia
Managing Uncertainty and Vagueness in Description Logics for the Semantic Web
Journal of Web Semantics, 6(4), 291-308, November 2008.

Ontologies play a crucial role in the development of the Semantic Web as a means for defining shared terms in web resources. They are formulated in web ontology languages, which are based on expressive description logics. Significant research efforts in the semantic web community are recently directed towards representing and reasoning with uncertainty and vagueness in ontologies for the Semantic Web. In this paper, we give an overview of approaches in this context to managing probabilistic uncertainty, possibilistic uncertainty, and vagueness in expressive description logics for the Semantic Web.

Thomas Lukasiewicz
Probabilistic Description Logic Programs under Inheritance with Overriding for the Semantic Web
International Journal of Approximate Reasoning, 49(1), 18-34, September 2008.

Towards uncertainty reasoning in the Rules, Logic, and Proof layers of the Semantic Web, we present a novel approach to probabilistic description logic programs, which combine probabilistic logic programs, probabilistic default theories, and the description logics behind OWL Lite and OWL DL. The approach is based on new notions of entailment for reasoning with conditional constraints, which realize the principle of inheritance with overriding for both classical and purely probabilistic knowledge. They are obtained by generalizing previous formalisms for probabilistic default reasoning with conditional constraints. In addition to dealing with probabilistic knowledge, the new notions of entailment thus also allow for handling default knowledge. We analyze the semantic properties of the new entailment relations. We also present algorithms for solving the main computational problems related to probabilistic description logic programs under inheritance with overriding.

Thomas Eiter, Giovambattista Ianni, Thomas Lukasiewicz, Roman Schindlauer, and Hans Tompits
Combining Answer Set Programming with Description Logics for the Semantic Web
Artificial Intelligence, 172(12/13), 1495-1539, August 2008.

We propose a combination of logic programming under the answer set semantics with the description logics SHIF(D) and SHOIN(D), which underly the Web ontology languages OWL Lite and OWL DL, respectively. To this end, we introduce description logic programs (or dl-programs), which consist of a description logic knowledge base L and a finite set P of description logic rules (or dl-rules). Such rules are similar to usual rules in nonmonotonic logic programs, but they may also contain queries to L, possibly under default negation, in their bodies. They allow for building rules on top of ontologies but also, to a limited extent, building ontologies on top of rules. We define a suite of semantics for various classes of dl-programs, which conservatively extend the standard semantics of the respective classes and coincide with it in absence of a description logic knowledge base. More concretely, we generalize positive, stratified, and arbitrary normal logic programs to dl-programs, and define a Herbrand model semantics for them. We show that they have similar properties as ordinary logic programs, and also provide fixpoint characterizations in terms of (iterated) consequence operators. For arbitrary dl-programs, we define answer sets by generalizing Gelfond and Lifschitz's notion of a transform, leading to a strong and a weak answer set semantics, which are based on reductions to the semantics of positive dl-programs and ordinary positive logic programs, respectively. We also show how the weak answer sets can be computed utilizing answer sets of ordinary normal logic programs. Furthermore, we show how some advanced reasoning tasks for the Semantic Web, including different forms of closed-world reasoning and default reasoning, as well as DL-safe rules, can be realized on top of dl-programs. Finally, we give a precise picture of the computational complexity of dl-programs, and we describe efficient algorithms and a prototype implementation of dl-programs which is available on the Web.

Thomas Lukasiewicz and Umberto Straccia
Tightly Coupled Fuzzy Description Logic Programs under the Answer Set Semantics for the Semantic Web
International Journal on Semantic Web and Information Systems, 4(3), 68-89, July-September 2008.

We present a novel approach to fuzzy description logic programs (or simply fuzzy dl-programs) under the answer set semantics, which is a tight integration of fuzzy disjunctive logic programs under the answer set semantics with fuzzy description logics. From a different perspective, it is a generalization of tightly coupled disjunctive dl-programs by fuzzy vagueness in both the description logic and the logic program component. We show that the new formalism faithfully extends both fuzzy disjunctive logic programs and fuzzy description logics, and that under suitable assumptions, reasoning in the new formalism is decidable. We present a polynomial reduction of certain fuzzy dl-programs to tightly coupled disjunctive dl-programs, and we analyze the complexity of consistency checking and query processing for certain fuzzy dl-programs. Furthermore, we provide a special case of fuzzy dl-programs for which deciding consistency and query processing can both be done in polynomial time in the data complexity.

Thomas Lukasiewicz
Expressive Probabilistic Description Logics
Artificial Intelligence, 172(6/7), 852-883, April 2008.

The work in this paper is directed towards sophisticated formalisms for reasoning under probabilistic uncertainty in ontologies in the Semantic Web. Ontologies play a central role in the development of the Semantic Web, since they provide a precise definition of shared terms in web resources. They are expressed in the standardized web ontology language OWL, which consists of the three increasingly expressive sublanguages OWL Lite, OWL DL, and OWL Full. The sublanguages OWL Lite and OWL DL have a formal semantics and a reasoning support through a mapping to the expressive description logics SHIF(D) and SHOIN(D), respectively. In this paper, we present the expressive probabilistic description logics P-SHIF(D) and P-SHOIN(D), which are probabilistic extensions of these description logics. They allow for expressing rich terminological probabilistic knowledge about concepts and roles as well as assertional probabilistic knowledge about instances of concepts and roles. They are semantically based on the notion of probabilistic lexicographic entailment from probabilistic default reasoning, which naturally interprets this terminological and assertional probabilistic knowledge as knowledge about random and concrete instances, respectively. As an important additional feature, they also allow for expressing terminological default knowledge, which is semantically interpreted as in Lehmann's lexicographic entailment in default reasoning from conditional knowledge bases. Another important feature of this extension of SHIF(D) and SHOIN(D) by probabilistic uncertainty is that it can be applied to other classical description logics as well. We then present sound and complete algorithms for the main reasoning problems in the new probabilistic description logics, which are based on reductions to reasoning in their classical counterparts, and to solving linear optimization problems. In particular, this shows the important result that reasoning in the new probabilistic description logics is decidable/computable. Furthermore, we also analyze the computational complexity of the main reasoning problems in the new probabilistic description logics in the general as well as restricted cases.

Thomas Lukasiewicz
Fuzzy Description Logic Programs under the Answer Set Semantics for the Semantic Web
Fundamenta Informaticae, 82(3), 289-310, 2008.

There are numerous semantic web applications where dealing with vagueness and imprecision plays an important role. Some examples of such applications are (i) multimedia information processing and retrieval, (ii) natural language interfaces to the Web, and (iii) ontology mapping and information retrieval. In this paper, towards dealing with vagueness and imprecision in the reasoning layers of the Semantic Web, we present an approach to normal fuzzy description logic programs under the answer set semantics, which are a generalization of normal description logic programs (dl-programs) under the answer set semantics by fuzzy vagueness and imprecision in both the description logic and the logic program component. We define a canonical semantics of positive and stratified fuzzy dl-programs in terms of a unique least model and iterative least models, respectively. We then define the answer set semantics of general fuzzy dl-programs, and show in particular that all answer sets of a fuzzy dl-program are minimal models, and that the answer set semantics of positive and stratified fuzzy dl-programs coincides with their canonical least model and iterative least model semantics, respectively. We also provide a characterization of the canonical semantics of positive and stratified fuzzy dl-programs in terms of a fixpoint and an iterative fixpoint semantics, respectively. Furthermore, we provide a reduction of fuzzy dl-programs under the answer set semantics to normal dl-programs under the answer set semantics. Finally, we also describe a special case of fuzzy dl-programs where query processing can be done in polynomial time in the data complexity.

Jörg Schellhase and Thomas Lukasiewicz
Using Search Strategies and a Description Logic Paradigm with Conditional Preferences for Literature Search
International Journal of Metadata, Semantics and Ontologies, 3(1), 68-83, 2008.

In this paper, we propose a novel query formalism for literature search, which is based on description logics and variable-strength conditional preferences. Query languages of current search engines are very restricted in their expressive power. There are scientific search engines on the web, however, that have valuable metadata about research publications, authors, organisations, and scientific events. We show that description logics with conditional preferences allow for a more powerful query language, which can exploit the available metadata more effectively than the current approaches do. In particular, our approach allows for expressing nearly all important information search strategies proposed by Bates. We also describe a dialogue-oriented interface to the new query formalism and discuss possible extensions.

Thomas Lukasiewicz and Jörg Schellhase
Variable-Strength Conditional Preferences for Ranking Objects in Ontologies
Journal of Web Semantics, 5(3), 180-194, September 2007.

We introduce conditional preference bases as a means for ranking objects in ontologies. Conditional preference bases consist of a description logic knowledge base and a finite set of conditional preferences, which are statements of the form "generally, in the context φ, property α is preferred over property ¬α with strength s". They are inspired by variable-strength defaults in conditional knowledge bases. We define the notion of consistency for conditional preference bases, and we show how consistent conditional preference bases can be used for ranking objects in ontologies, where every object represents essentially a set of individuals that are sharing the same ranking-relevant properties. More concretely, we define two object rankings, denoted κ^sum and κ^lex, which evaluate the strengths of conditional preferences in an additive and a lexicographic way, respectively. Furthermore, we provide algorithms for the main computational tasks for ranking objects under conditional preference bases, we analyze the complexity of these tasks, and we delineate a tractable special case. To give evidence of the usefulness of this approach in practice, we describe two applications in the areas of product and literature search, where it allows especially for a flexible user-defined ranking of the query results reflecting personal preferences.

Thomas Lukasiewicz
Probabilistic Description Logic Programs
International Journal of Approximate Reasoning, 45(2), 288-307, July 2007.

Towards sophisticated representation and reasoning techniques that allow for probabilistic uncertainty in the Rules, Logic, and Proof layers of the Semantic Web, we present probabilistic description logic programs (or pdl-programs), which are a combination of description logic programs (or dl-programs) under the answer set semantics and the well-founded semantics with Poole's independent choice logic. We show that query processing in such pdl-programs can be reduced to computing all answer sets of dl-programs and solving linear optimization problems, and to computing the well-founded model of dl-programs, respectively. Moreover, we show that the answer set semantics of pdl-programs is a refinement of the well-founded semantics of pdl-programs. Furthermore, we also present an algorithm for query processing in the special case of stratified pdl-programs, which is based on a reduction to computing the canonical model of stratified dl-programs.

Thomas Lukasiewicz
Nonmonotonic Probabilistic Logics under Variable-Strength Inheritance with Overriding: Complexity, Algorithms, and Implementation
International Journal of Approximate Reasoning, 44(3), 301-321, March 2007.

In previous work, I have introduced nonmonotonic probabilistic logics under variable-strength inheritance with overriding. They are formalisms for probabilistic reasoning from sets of strict logical, default logical, and default probabilistic sentences, which are parameterized through a value lambda in [0,1] that describes the strength of the inheritance of default probabilistic knowledge. In this paper, I continue this line of research. I give a precise picture of the complexity of deciding consistency of strength lambda and of computing tight consequences of strength lambda. Furthermore, I present algorithms for these tasks, which are based on reductions to the standard problems of deciding satisfiability and of computing tight logical consequences in model-theoretic probabilistic logic. Finally, I describe the system nmproblog, which includes a prototype implementation of these algorithms.

Thomas Eiter and Thomas Lukasiewicz
Causes and Explanations in the Structural-Model Approach: Tractable Cases
Artificial Intelligence, 170(6/7), 542-580, May 2006.

This paper continues the research on the computational aspects of Halpern and Pearl's causes and explanations in the structural model approach. To this end, we first explore how an instance of deciding weak cause can be reduced to an equivalent instance in which irrelevant variables in the (potential) weak cause and the causal model are removed, which extends previous work by Hopkins. We then present a new characterization of weak cause for a certain class of causal models in which the causal graph over the endogenous variables has the form of a directed chain of causal subgraphs, called decomposable causal graph. Furthermore, we also identify two important subclasses in which the causal graph over the endogenous variables forms a directed tree and more generally a directed chain of layers, called causal tree and layered causal graph, respectively. By combining the removal of irrelevant variables with this new characterization of weak cause, we then obtain techniques for deciding and computing causes and explanations in the structural-model approach, which can be done in polynomial time under suitable restrictions. This way, we obtain several tractability results for causes and explanations in the structural-model approach. To our knowledge, these are the first explicit ones. They are especially useful for dealing with structure-based causes and explanations in first-order reasoning about actions, which produces large causal models that are naturally layered through the time line, and thus have the structure of layered causal graphs. Furthermore, an important feature of the tractable cases for causal trees and layered causal graphs is that they can be recognized efficiently, namely in linear time. Finally, by extending the new characterization of weak cause, we obtain similar techniques for computing the degrees of responsibility and blame, and hence also novel tractability results for structure-based responsibility and blame.

Thomas Lukasiewicz
Weak Nonmonotonic Probabilistic Logics
Artificial Intelligence, 168(1/2), 119-161, October 2005.

We present an approach where probabilistic logic is combined with default reasoning from conditional knowledge bases in Kraus et al.'s System P, Pearl's System Z, and Lehmann's lexicographic entailment. The resulting probabilistic generalizations of default reasoning from conditional knowledge bases allow for handling in a uniform framework strict logical knowledge, default logical knowledge, as well as purely probabilistic knowledge. Interestingly, probabilistic entailment in System P coincides with probabilistic entailment under g-coherence from imprecise probability assessments. We then analyze the semantic and nonmonotonic properties of the new formalisms. It turns out that they all are proper generalizations of their classical counterparts and have similar properties as them. In particular, they all satisfy the rationality postulates of System P and some Direct Inference property. Moreover, probabilistic entailment in System Z and probabilistic lexicographic entailment both satisfy the property of Rational Monotonicity and some Irrelevance property, while probabilistic entailment in System P does not. We also analyze the relationships between the new formalisms. Here, probabilistic entailment in System P is weaker than probabilistic entailment in System Z, which in turn is weaker than probabilistic lexicographic entailment. Moreover, they all are weaker than entailment in probabilistic logic where default sentences are interpreted as strict sentences. Under natural conditions, probabilistic entailment in System Z and lexicographic entailment even coincide with such entailment in probabilistic logic, while probabilistic entailment in System P does not. Finally, we also present algorithms for reasoning under probabilistic entailment in System Z and probabilistic lexicographic entailment, and we give a precise picture of its complexity.

Veronica Biazzo, Angelo Gilio, Thomas Lukasiewicz, and Giuseppe Sanfilippo
Probabilistic Logic under Coherence: Complexity and Algorithms
Annals of Mathematics and Artificial Intelligence, 45(1/2), 35-81, October 2005.

In previous work, we have explored the relationship between probabilistic reasoning under coherence and model-theoretic probabilistic reasoning. In particular, we have shown that the notions of g-coherence and of g-coherent entailment in probabilistic reasoning under coherence can be expressed by combining notions in model-theoretic probabilistic reasoning with concepts from default reasoning. In this paper, we continue this line of research. Based on the above semantic results, we draw a precise picture of the computational complexity of probabilistic reasoning under coherence. Moreover, we introduce transformations for probabilistic reasoning under coherence, which reduce an instance of deciding g-coherence or of computing tight intervals under g-coherent entailment to a smaller problem instance, and which can be done very efficiently. Furthermore, we present new algorithms for deciding g-coherence and for computing tight intervals under g-coherent entailment, which reformulate previous algorithms using terminology from default reasoning. They are based on reductions to standard problems in model-theoretic probabilistic reasoning, which in turn can be reduced to linear optimization problems. Hence, efficient techniques for model-theoretic probabilistic reasoning can immediately be applied for probabilistic reasoning under coherence (for example, column generation techniques). We describe several such techniques, which transform problem instances in model-theoretic probabilistic reasoning into smaller problem instances. We also describe a technique for obtaining a reduced set of variables for the associated linear optimization problems in the conjunctive case, and give new characterizations of this reduced set as a set of non-decomposable variables, and using the concept of random gain.

Thomas Lukasiewicz
Nonmonotonic Probabilistic Reasoning under Variable-Strength Inheritance with Overriding
Synthese, 146(1/2), 153-169, August 2005.

We present an approach to reasoning from statistical and subjective knowledge, which is based on a combination of probabilistic reasoning from conditional constraints with approaches to default reasoning from conditional knowledge bases. More precisely, we introduce the notions of z-, lexicographic, and conditional entailment for conditional constraints, which are probabilistic generalizations of Pearl's entailment in system Z, Lehmann's lexicographic entailment, and Geffner's conditional entailment, respectively. We show that the new formalisms have nice properties. In particular, they show a similar behavior as reference-class reasoning in a number of uncontroversial examples. The new formalisms, however, also avoid many drawbacks of reference-class reasoning. More precisely, they can handle complex scenarios and even purely probabilistic subjective knowledge as input. Moreover, conclusions are drawn in a global way from all the available knowledge as a whole. We then show that the new formalisms also have nice general nonmonotonic properties. In detail, the new notions of z-, lexicographic, and conditional entailment have similar properties as their classical counterparts. In particular, they all satisfy the rationality postulates proposed by Kraus, Lehmann, and Magidor, and they have some general irrelevance and direct inference properties. Moreover, the new notions of z- and lexicographic entailment satisfy the property of rational monotonicity. Furthermore, the new notions of z-, lexicographic, and conditional entailment are proper generalizations of both their classical counterparts and the classical notion of logical entailment for conditional constraints. Finally, we provide algorithms for reasoning under the new formalisms, and we analyze its computational complexity.

Gabriele Kern-Isberner and Thomas Lukasiewicz
Combining Probabilistic Logic Programming with the Power of Maximum Entropy
Artificial Intelligence, 157(1/2), 139-202, August 2004.

This paper is on the combination of two powerful approaches to uncertain reasoning: logic programming in a probabilistic setting, on the one hand, and the information-theoretical principle of maximum entropy, on the other hand. More precisely, we present two approaches to probabilistic logic programming under maximum entropy. The first one is based on the usual notion of entailment under maximum entropy, and is defined for the very general case of probabilistic logic programs over Boolean events. The second one is based on a new notion of entailment under maximum entropy, where the principle of maximum entropy is coupled with the closed world assumption (CWA) from classical logic programming. It is only defined for the more restricted case of probabilistic logic programs over conjunctive events. We then analyze the nonmonotonic behavior of both approaches along benchmark examples and along general properties for default reasoning from conditional knowledge bases. It turns out that both approaches have very nice nonmonotonic features. In particular, they realize some inheritance of probabilistic knowledge along subclass relationships, without suffering from the problem of inheritance blocking and from the drowning problem. They both also satisfy the property of rational monotonicity and several irrelevance properties. We finally present algorithms for both approaches, which are based on generalizations of recent techniques for probabilistic logic programming under logical entailment. The algorithm for the first approach still produces quite large weighted entropy maximization problems, while the one for the second approach generates optimization problems of the same size as the ones produced in probabilistic logic programming under logical entailment.

Thomas Eiter and Thomas Lukasiewicz
Complexity Results for Explanations in the Structural-Model Approach
Artificial Intelligence, 154(1/2), 145-198, April 2004.

We analyze the computational complexity of Halpern and Pearl's (causal) explanations in the structural-model approach, which are based on their notions of weak and actual cause. In particular, we give a precise picture of the complexity of deciding explanations, alpha-partial explanations, and partial explanations, and of computing the explanatory power of partial explanations. Moreover, we analyze the complexity of deciding whether an explanation or an alpha-partial explanation over certain variables exists. We also analyze the complexity of deciding explanations and partial explanations in the case of succinctly represented context sets, the complexity of deciding explanations in the general case of situations, and the complexity of deciding subsumption and equivalence between causal models. All complexity results are derived for the general case, as well as for the restriction to the case of binary causal models, in which all endogenous variables may take only two values. To our knowledge, no complexity results for explanations in the structural-model approach have been derived so far. Our results give insight into the computational structure of Halpern and Pearl's explanations, and pave the way for efficient algorithms and implementations.

Veronica Biazzo, Rosalba Giugno, Thomas Lukasiewicz, and V.S. Subrahmanian
Temporal Probabilistic Object Bases
IEEE Transactions on Knowledge and Data Engineering (TKDE), 15(4), 921-939, July/August 2003.

There are numerous applications where we have to deal with temporal uncertainty associated with objects. The ability to automatically store and manipulate time, probabilities, and objects is important. We propose a data model and algebra for temporal probabilistic object bases (TPOBs), which allows us to specify the probability with which an event occurs at a given time point. In explicit TPOB-instances, the sets of time points along with their probability intervals are explicitly enumerated. In implicit TPOB-instances, sets of time points are expressed by constraints and their probability intervals by probability distribution functions. Thus, implicit object base instances are succinct representations of explicit ones; they allow for an efficient implementation of algebraic operations, while their explicit counterparts make defining algebraic operations easy. We extend the relational algebra to both explicit and implicit instances and prove that the operations on implicit instances correctly implement their counterpart on explicit instances.

Thomas Eiter and Thomas Lukasiewicz
Complexity Results for Structure-Based Causality
Artificial Intelligence, 142(1), 53-89, November 2002.

We give a precise picture of the computational complexity of causal relationships in Pearl's structural models, where we focus on causality between variables, event causality, and probabilistic causality. As for causality between variables, we consider the notions of causal irrelevance, cause, cause in a context, direct cause, and indirect cause. As for event causality, we analyze the complexity of the notions of necessary and possible cause, and of the sophisticated notions of weak and actual cause by Halpern and Pearl. In the course of this, we also prove an open conjecture by Halpern and Pearl, and establish other semantic results. We then analyze the complexity of the probabilistic notions of probabilistic causal irrelevance, likely causes of events, and occurrences of events despite other events. Moreover, we consider decision and optimization problems involving counterfactual formulas. To our knowledge, no complexity aspects of causal relationships in the structural-model approach have been considered so far, and our results shed light on this issue.

Veronica Biazzo, Angelo Gilio, Thomas Lukasiewicz, and Giuseppe Sanfilippo
Probabilistic Logic under Coherence, Model-Theoretic Probabilistic Logic, and Default Reasoning in System P
Journal of Applied Non-Classical Logics, 12(2), 189-213, 2002.

We study probabilistic logic under the viewpoint of the coherence principle of de Finetti. In detail, we explore how probabilistic reasoning under coherence is related to model-theoretic probabilistic reasoning and to default reasoning in System P. In particular, we show that the notions of g-coherence and of g-coherent entailment can be expressed by combining notions in model-theoretic probabilistic logic with concepts from default reasoning. Moreover, we show that probabilistic reasoning under coherence is a generalization of default reasoning in System P. That is, we provide a new probabilistic semantics for System P, which neither uses infinitesimal probabilities nor atomic bound (or big-stepped) probabilities. These results also provide new algorithms for probabilistic reasoning under coherence and for default reasoning in System P, and they give new insight into default reasoning with conditional objects.

Thomas Lukasiewicz
Probabilistic Default Reasoning with Conditional Constraints
Annals of Mathematics and Artificial Intelligence, 34(1-3), 35-88, March 2002.

We present an approach to reasoning from statistical and subjective knowledge, which is based on a combination of probabilistic reasoning from conditional constraints with approaches to default reasoning from conditional knowledge bases. More precisely, we introduce the notions of z-, lexicographic, and conditional entailment for conditional constraints, which are probabilistic generalizations of Pearl's entailment in system Z, Lehmann's lexicographic entailment, and Geffner's conditional entailment, respectively. We show that the new formalisms have nice properties. In particular, they show a similar behavior as reference-class reasoning in a number of uncontroversial examples. The new formalisms, however, also avoid many drawbacks of reference-class reasoning. More precisely, they can handle complex scenarios and even purely probabilistic subjective knowledge as input. Moreover, conclusions are drawn in a global way from all the available knowledge as a whole. We then show that the new formalisms also have nice general nonmonotonic properties. In detail, the new notions of z-, lexicographic, and conditional entailment have similar properties as their classical counterparts. In particular, they all satisfy the rationality postulates proposed by Kraus, Lehmann, and Magidor, and they have some general irrelevance and direct inference properties. Moreover, the new notions of z- and lexicographic entailment satisfy the property of rational monotonicity. Furthermore, the new notions of z-, lexicographic, and conditional entailment are proper generalizations of both their classical counterparts and the classical notion of logical entailment for conditional constraints. Finally, we provide algorithms for reasoning under the new formalisms, and we analyze its computational complexity.

Thomas Eiter, Thomas Lukasiewicz, and Michael Walter
A Data Model and Algebra for Probabilistic Complex Values
Annals of Mathematics and Artificial Intelligence, 33(2-4), 205-252, December 2001.

We present a probabilistic data model for complex values. More precisely, we introduce probabilistic complex value relations, which combine the concept of probabilistic relations with the idea of complex values in a uniform framework. We elaborate a model-theoretic definition of probabilistic combination strategies, which has a rigorous foundation on probability theory. We then define an algebra for querying database instances, which comprises the operations of selection, projection, renaming, join, Cartesian product, union, intersection, and difference. We prove that our data model and algebra for probabilistic complex values generalizes the classical relational data model and algebra. Moreover, we show that under certain assumptions, all our algebraic operations are tractable. We finally show that most of the query equivalences of classical relational algebra carry over to our algebra on probabilistic complex value relations. Hence, query optimization techniques for classical relational algebra can easily be applied to optimize queries on probabilistic complex value relations.

Thomas Eiter, James J. Lu, Thomas Lukasiewicz, and V.S. Subrahmanian
Probabilistic Object Bases
ACM Transactions on Database Systems (TODS), 26(3), 264-312, September 2001.

Although there are many applications where an object-oriented data model is a good way of representing and querying data, current object database systems are unable to handle objects whose attributes are uncertain. In this article, we extend previous work by Kornatzky and Shimony to develop an algebra to handle object bases with uncertainty. We propose concepts of consistency for such object bases, together with an NP-completeness result, and classes of probabilistic object bases for which consistency is polynomially checkable. In addition, as certain operations involve conjunctions and disjunctions of events, and as the probability of conjunctive and disjunctive events depends both on the probabilities of the primitive events involved as well as on what is known (if anything) about the relationship between the events, we show how all our algebraic operations may be performed under arbitrary probabilistic conjunction and disjunction strategies. We also develop a host of equivalence results in our algebra, which may be used as rewrite rules for query optimization. Last but not least, we have developed a prototype probabilistic object base server on top of ObjectStore. We describe experiments to assess the efficiency of different possible rewrite rules.

Thomas Lukasiewicz
Probabilistic Logic Programming with Conditional Constraints (Appendix)
ACM Transactions on Computational Logic (TOCL), 2(3), 289-339, July 2001.

We introduce a new approach to probabilistic logic programming in which probabilities are defined over a set of possible worlds. More precisely, classical program clauses are extended by a subinterval of [0,1] that describes a range for the conditional probability of the head of a clause given its body. We then analyze the complexity of selected probabilistic logic programming tasks. It turns out that probabilistic logic programming is computationally more complex than classical logic programming. More precisely, the tractability of special cases of classical logic programming generally does not carry over to the corresponding special cases of probabilistic logic programming. Moreover, we also draw a precise picture of the complexity of deciding and computing tight logical consequences in probabilistic reasoning with conditional constraints in general. We then present linear optimization techniques for deciding satisfiability and computing tight logical consequences of probabilistic logic programs. These techniques are efficient in the special case in which we have little relevant purely probabilistic knowledge.We finally show that probabilistic logic programming under certain syntactic and semantic restrictions is closely related to van Emden's quantitative deduction, and thus has computational properties similar to classical logic programming. Based on this result, we present an efficient approximation technique for probabilistic logic programming.

Thomas Eiter and Thomas Lukasiewicz
Default Reasoning from Conditional Knowledge Bases: Complexity and Tractable Cases
Artificial Intelligence, 124(2), 169-241, December 2000.

Conditional knowledge bases have been proposed as belief bases that include defeasible rules (also called defaults) of the form "phi->psi", which informally read as "generally, if phi then psi". Such rules may have exceptions, which can be handled in different ways. A number of entailment semantics for conditional knowledge bases have been proposed in the literature. However, while the semantic properties and interrelationships of these formalisms are quite well understood, about their computational properties only partial results are known so far. In this paper, we fill these gaps and first draw a precise picture of the complexity of default reasoning from conditional knowledge bases: Given a conditional knowledge base KB and a default "phi->psi", does KB entail "phi->psi"? We classify the complexity of this problem for a number of well-known approaches (including Goldszmidt et al.'s maximum entropy approach and Geffner's conditional entailment), where we consider the general propositional case as well as natural syntactic restrictions (in particular, to Horn and literal-Horn conditional knowledge bases). As we show, the more sophisticated semantics for conditional knowledge bases are plagued with intractability in all these fragments. We thus explore cases in which these semantics are tractable, and find that most of them enjoy this property on feedback-free Horn conditional knowledge bases, which constitute a new, meaningful class of conditional knowledge bases. Furthermore, we generalize previous tractability results from Horn to q-Horn conditional knowledge bases, which allow for a limited use of disjunction. Our results complement and extend previous results, and contribute in refining the tractability/intractability frontier of default reasoning from conditional knowledge bases. They provide useful insight for developing efficient implementations.

Thomas Lukasiewicz
Local Probabilistic Deduction from Taxonomic and Probabilistic Knowledge-Bases over Conjunctive Events
International Journal of Approximate Reasoning, 21(1), 23-61, May 1999.

We elaborate locally complete inference rules for probabilistic deduction from taxonomic and probabilistic knowledge-bases over conjunctive events. We integrate the presented inference rules into a local probabilistic deduction technique, which exploits taxonomic knowledge for an efficient representation of conjunctive events. This local probabilistic deduction technique is less incomplete and more efficient than already existing local approaches to probabilistic deduction. However, we show that it cannot compete with global probabilistic deduction by linear programming. Surprisingly, we can provide examples of globally very incomplete probabilistic deductions in the presented local approach. More generally, we even show that all systems of inference rules for probabilistic deduction in taxonomic and probabilistic knowledge-bases over conjunctive events that have a limited number of probabilistic formulas in the premises of their inference patterns are globally incomplete. Furthermore, we show that the presented local approach is not more efficient than the linear programming approach for that framework. We conclude that probabilistic deduction by the iterative application of inference rules on interval restrictions for conditional probabilities, even though considered very promising in the literature so far, is very limited in its field of application.

Thomas Lukasiewicz
Probabilistic Deduction with Conditional Constraints over Basic Events
Journal of Artificial Intelligence Research (JAIR), 10, 199-241, April 1999.

We study the problem of probabilistic deduction with conditional constraints over basic events. We show that globally complete probabilistic deduction with conditional constraints over basic events is NP-hard. We then concentrate on the special case of probabilistic deduction in conditional constraint trees. We elaborate very efficient techniques for globally complete probabilistic deduction. In detail, for conditional constraint trees with point probabilities, we present a local approach to globally complete probabilistic deduction, which runs in linear time in the size of the conditional constraint trees. For conditional constraint trees with interval probabilities, we show that globally complete probabilistic deduction can be done in a global approach by solving nonlinear programs. We show how these nonlinear programs can be transformed into equivalent linear programs, which are solvable in polynomial time in the size of the conditional constraint trees.

Refereed and Invited Papers in Books

Thomas Lukasiewicz and Gerardo I. Simari
Tractable Probabilistic Description Logic Programs
Invited paper in Z. Ma and L. Yan, editors, Advances in Probabilistic Databases for Uncertain Information Management, pp. 131-159. Volume 304 of Studies in Fuzziness and Soft Computing. Springer, 2013.

We propose tractable probabilistic description logic programs for the Semantic Web, which combine tractable description logics, normal programs under the answer set semantics, and probabilities. In detail, we first provide novel reductions of tight query processing and of deciding consistency in probabilistic description logic programs to the answer set semantics of the underlying normal description logic programs. Based on these reductions, we then introduce a novel well-founded semantics for probabilistic description logic programs, called the total well-founded semantics. Contrary to the previous answer set and well-founded semantics, it is defined for all probabilistic description logic programs and all probabilistic queries. Furthermore, tight (resp., tight literal) query processing under the total well-founded semantics coincides with tight (resp., tight literal) query processing under the previous well-founded (resp., answer set) semantics in all cases where the latter is defined. We then present an anytime algorithm for tight query processing in probabilistic description logic programs under the total well-founded semantics. We also show that tight literal query processing in probabilistic description logic programs under the total well-founded semantics can be done in polynomial time in the data complexity and is complete for EXP in the combined complexity. Finally, we describe an application of probabilistic description logic programs in probabilistic data integration for the Semantic Web.

Claudia d'Amato, Nicola Fanizzi, Bettina Fazzinga, Georg Gottlob, and Thomas Lukasiewicz
Semantic Web Search and Inductive Reasoning
In F. Bobillo, P. C. G. da Costa, C. d'Amato, N. Fanizzi, K. B. Laskey, K. J. Laskey, T. Lukasiewicz, M. Nickles, and M. Pool, editors, Uncertainty Reasoning for the Semantic Web II, pp. 237-261. Volume 7123 of Lecture Notes in Computer Science. Springer, 2012.

Extensive research activities are recently directed towards the Semantic Web as a future form of the Web. Consequently, Web search as the key technology of the Web is evolving towards some novel form of Semantic Web search. A very promising recent such approach is based on combining standard Web pages and search queries with ontological background knowledge, and using standard Web search engines as the main inference motor of Semantic Web search. In this paper, we further enhance this approach to Semantic Web search by the use of inductive reasoning techniques. This adds especially the important ability to handle inconsistencies, noise, and incompleteness, which are all very likely to occur in distributed and heterogeneous environments, such as the Web. We report on a prototype implementation of the new approach and experimental results.

Claudia d'Amato, Nicola Fanizzi, Floriana Esposito, and Thomas Lukasiewicz
Representing Uncertain Concepts in Rough Description Logics via Contextual Indiscernibility Relations
In F. Bobillo, P. C. G. da Costa, C. d'Amato, N. Fanizzi, K. B. Laskey, K. J. Laskey, T. Lukasiewicz, M. Nickles, and M. Pool, editors, Uncertainty Reasoning for the Semantic Web II, pp. 237-261. Volume 7123 of Lecture Notes in Computer Science. Springer, 2012.

We investigate the modeling of uncertain concepts via rough description logics (RDLs), which are an extension of traditional description logics (DLs) by a mechanism to handle approximate concept definitions via lower and upper approximations of concepts based on a rough-set semantics. This allows to apply RDLs to modeling uncertain knowledge. Since these approximations are ultimately grounded on an indiscernibility relation, we explore possible logical and numerical ways for defining such relations based on the considered knowledge. In particular, we introduce the notion of context, allowing for the definition of specific equivalence relations, which are directly used for lower and upper approximations of concepts. The notion of context also allows for defining similarity measures, which are used for introducing a notion of tolerance in the indiscernibility. Finally, we describe several learning problems in our RDL framework.

Andrea Calì, Georg Gottlob, Thomas Lukasiewicz, and Andreas Pieris
Datalog+/-: A Family of Languages for Ontology Querying
In O. de Moor, G. Gottlob, T. Furche, and A. Sellers, editors, Datalog Reloaded - First International Workshop (Datalog 2010), pp. 351-368. Volume 6702 of Lecture Notes in Computer Science. Springer, 2011.

In ontology-based data access, an extensional database is enhanced by an ontology that generates new intensional knowledge which has to be considered when answering queries. In this setting, tractable data complexity (i.e., complexity w.r.t. the data only) of query answering is crucial, given the need to deal with large data sets. This paper summarizes results on a recently introduced family of Datalog-based languages, called Datalog+/-, which is a new framework for tractable ontology querying. Plain Datalog is extended by allowing existential quantifiers, the equality predicate, and the truth constant false to appear in rule heads. At the same time, the resulting language is syntactically restricted, so as to achieve decidability and even tractability.

Andrea Calì, Georg Gottlob, Thomas Lukasiewicz, Bruno Marnette, and Andreas Pieris
Datalog+/-: A Family of Logical Knowledge Representation and Query Languages for New Applications
Invited paper in J.-P. Jouannaud, editor, Proceedings of the 2010 IEEE Conference on Logic in Computer Science (LICS 2010), pp. 228-242. IEEE Computer Society, 2010.

This paper summarizes results on a recently introduced family of Datalog-based languages, called Datalog+/-, which is a new framework for tractable ontology querying, and for a variety of other applications. Datalog+/- extends plain Datalog by features such as existentially quantified rule heads and, at the same time, restricts the rule syntax so as to achieve decidability and tractability. In particular, we discuss three paradigms ensuring decidability: chase termination, guardedness, and stickiness.

Thomas Lukasiewicz and Umberto Straccia
Tightly Coupled Fuzzy Description Logic Programs under the Answer Set Semantics for the Semantic Web
Invited paper in M. Lytras and A. Sheth, editors, Progressive Concepts for Semantic Web Evolution: Applications and Developments, Advances in Semantic Web Information Systems, pp. 237-256. Information Science Reference, 2010.

This chapter presents a novel approach to fuzzy description logic programs (or simply fuzzy dl-programs) under the answer set semantics, which is a tight integration of fuzzy disjunctive logic programs under the answer set semantics with fuzzy description logics. From a different perspective, it is a generalization of tightly coupled disjunctive dl-programs by fuzzy vagueness in both the description logic and the logic program component. The authors show that the new formalism faithfully extends both fuzzy disjunctive logic programs and fuzzy description logics, and that under suitable assumptions, reasoning in the new formalism is decidable. The authors present a polynomial reduction of certain fuzzy dl-programs to tightly coupled disjunctive dl-programs, and we analyze the complexity of consistency checking and query processing for certain fuzzy dl-programs. Furthermore, the authors provide a special case of fuzzy dl-programs for which deciding consistency and query processing can both be done in polynomial time in the data complexity.

Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz
Datalog Extensions for Tractable Query Answering over Ontologies
Invited paper in R. De Virgilio, F. Giunchiglia, and L. Tanca, editors, Semantic Web Information Management: A Model-Based Perspective, pp. 249-279. Springer, 2010.

We survey a recently introduced family of expressive extensions of Datalog, called Datalog+/-, which is a new framework for representing ontologies in the form of integrity constraints, and for query answering under such constraints. Datalog+/- is derived from Datalog by allowing existentially quantified variables in rule heads, and by enforcing suitable properties in rule bodies, to ensure decidable and efficient query answering. We first present different languages in the Datalog+/- family, providing tight complexity bounds for nearly all cases. We then show that such languages are general enough to capture the most common tractable ontology languages. In particular, Datalog+/- can express the DL-Lite family of description logics and F-Logic Lite. Datalog+/- is a natural and very general framework that can be employed in different contexts such as data integration and exchange.

Thomas Lukasiewicz
Uncertainty Reasoning for the Semantic Web
Tutorial paper in A. Polleres and T. Swift, editors, Proceedings of the 3rd International Conference on Web Reasoning and Rule Systems (RR 2009), pp. 26-39, Chantilly, Virginia, USA, October 2009. Volume 5837 of Lecture Notes in Computer Science, Springer, 2009.

Significant research activities have recently been directed towards the Semantic Web as a potential future substitute of the current World Wide Web. Many experts predict that the next huge step forward in Web information technology will be achieved by adding semantics to Web data. An important role in research towards the Semantic Web is played by formalisms and technologies for handling uncertainty and/or vagueness. In this paper, I first provide some motivating examples for handling uncertainty and/or vagueness in the Semantic Web. I then give an overview of some own recent formalisms for handling uncertainty and/or vagueness in the Semantic Web.

Thomas Lukasiewicz
Uncertainty in the Semantic Web
Invited paper in L. Godo and A. Pugliese, editors, Proceedings of the 3rd International Conference on Scalable Uncertainty Management (SUM 2009), pp. 2-11, Washington DC, USA, September 2009. Volume 5785 of Lecture Notes in Computer Science, Springer, 2009.

During the recent decade, significant research activities have been directed towards the Semantic Web as future substitute of the Web. Many experts predict that the next huge step forward in Web information technology will be achieved by adding semantics to Web data. An important role in research towards the Semantic Web is played by formalisms and technologies for handling uncertainty and/or vagueness. In this paper, I give an overview of some own recent formalisms for handling uncertainty and/or vagueness in the Semantic Web.

Włodzimierz Drabent, Thomas Eiter, Giovambattista Ianni, Thomas Krennwallner, Thomas Lukasiewicz, and Jan Małuszyński
Hybrid Reasoning with Rules and Ontologies
In F. Bry and J. Małuszyński, editors, Semantic Techniques for the Web: The REWERSE Perspective, pp. 1-49. Volume 5500 of Lecture Notes in Computer Science, Springer, 2009.

The purpose of this chapter is to report on work that has been done in the REWERSE project concerning hybrid reasoning with rules and ontologies. Two major streams of work have been pursued within REWERSE. They start from the predominant semantics of non-monotonic rules in logic programming. The one stream was an extension of non-monotonic logic programs under answer set semantics, with query interfaces to external knowledge sources. The other stream, in the spirit of the AL-log approach of enhanced deductive databases, was an extension of Datalog (with the well-founded semantics, which is predominant in the database area). The former stream led to so-called non-monotonic dl-programs and hex-programs, and the latter stream to hybrid well-founded semantics. Further variants and derivations of the formalisms (like a well-founded semantics for dl-programs, respecting probabilistic knowledge, priorities, etc.) have been conceived.

Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz
Datalog±: A Unified Approach to Ontologies and Integrity Constraints
Invited paper in R. Fagin, editor, Proceedings of the 12th International Conference on Database Theory (ICDT 2009), pp. 14-30, Saint-Petersburg, Russia, March 2009. Volume 361 of ACM International Conference Proceeding Series, ACM Press, 2009.

We report on a recently introduced family of expressive extensions of Datalog, called Datalog+/-, which is a new framework for representing ontological axioms in form of integrity constraints, and for query answering under such constraints. Datalog+/- is derived from Datalog by allowing existentially quantified variables in rule heads, and by enforcing suitable properties in rule bodies, to ensure decidable and efficient query answering. We first present different languages in the Datalog+/- family, providing tight complexity bounds for all cases but one (where we have a low complexity AC0 upper bound). We then show that such languages are general enough to capture the most common tractable ontology languages. In particular, we show that the DL-Lite family of description logics and F-Logic Lite are expressible in Datalog+/-. We finally show how stratified negation can be added to Datalog+/- while keeping ontology querying tractable in the data complexity. Datalog+/- is a natural and very general framework that can be successfully employed in different contexts such as data integration and exchange. This survey mainly summarizes two recent papers.

Andrea Calì and Thomas Lukasiewicz
An Approach to Probabilistic Data Integration for the Semantic Web
In P. C. G. da Costa, C. d'Amato, N. Fanizzi, K. B. Laskey, K. J. Laskey, T. Lukasiewicz, M. Nickles, and M. Pool, editors, Uncertainty Reasoning for the Semantic Web I, pp. 52-65. Volume 5327 of Lecture Notes in Computer Science, Springer, 2008.

Probabilistic description logic programs are a powerful tool for knowledge representation in the Semantic Web, which combine description logics, normal programs under the answer set or well-founded semantics, and probabilistic uncertainty. The task of data integration amounts to providing the user with access to a set of heterogeneous data sources in the same fashion as when querying a single database, that is, through a global schema, which is a common representation of all the underlying data sources. In this paper, we make use of probabilistic description logic programs to model expressive data integration systems for the Semantic Web, where constraints are expressed both over the data sources and the global schema. We describe different types of probabilistic data integration, which aim especially at applications in the Semantic Web.

Andrea Calì, Thomas Lukasiewicz, Livia Predoiu, and Heiner Stuckenschmidt
Rule-Based Approaches for Representing Probabilistic Ontology Mappings
In P. C. G. da Costa, C. d'Amato, N. Fanizzi, K. B. Laskey, K. J. Laskey, T. Lukasiewicz, M. Nickles, and M. Pool, editors, Uncertainty Reasoning for the Semantic Web I, pp. 66-87. Volume 5327 of Lecture Notes in Computer Science, Springer, 2008.

Using mappings between ontologies is a common way of approaching the semantic heterogeneity problem on the Semantic Web. To fit into the landscape of Semantic Web languages, a suitable logic-based representation formalism for mappings is needed, which allows to reason with ontologies and mappings in an integrated manner, and to deal with uncertainty and inconsistencies in automatically created mappings. We analyze the requirements for such a formalism, and propose to use frameworks that integrate description logic ontologies with probabilistic rules. We compare two such frameworks and show the advantages of using the probabilistic extensions of their deterministic counterparts. The two frameworks that we compare are tightly coupled probabilistic dl-programs, which tightly combine the description logics behind OWL DL resp. OWL Lite, disjunctive logic programs under the answer set semantics, and Bayesian probabilities, on the one hand, and generalized Bayesian dl-programs, which tightly combine the DLP-fragment of OWL Lite with Datalog (without negation and equality) based on the semantics of Bayesian networks, on the other hand.

Paulo C. G. da Costa, Kathryn B. Laskey, and Thomas Lukasiewicz
Uncertainty Representation and Reasoning in the Semantic Web
In J. Cardoso and M. D. Lytras, editors, Semantic Web Engineering in the Knowledge Society, pp. 315-340. Information Science Reference, October 2008.

This chapter is about uncertainty representation and reasoning for the Semantic Web (SW). We address the importance, key issues, state-of-the-art approaches, and current efforts of both the academic and business communities in their search for a practical, standard way of representing and reasoning with incomplete information in the Semantic Web. The focus is on why uncertainty representation and reasoning are necessary, its importance to the SW vision, and the major issues and obstacles to addressing uncertainty in a principled and standardized way. Although some would argue that uncertainty belongs in the "rule layer" of the SW, we concentrate especially on uncertain extensions of ontology languages for the Semantic Web.

Refereed Conference Papers

Tommaso Di Noia and Thomas Lukasiewicz
Introducing Ontological CP-Nets
In F. Bobillo, R. Carvalho, P. C. G. da Costa, N. Fanizzi, K. B. Laskey, K. J. Laskey, T. Lukasiewicz, T. Martin, M. Nickles, and M. Pool, editors, Proceedings of the 8th International Workshop on Uncertainty Reasoning for the Semantic Web (URSW 2012), pp. 90-93, Boston, USA, November 2012. Volume 900 of CEUR Workshop Proceedings, CEUR-WS.org, 2012.

Preference representation and reasoning is a key issue in many real-world scenarios. Currently, there are many approaches allowing preferences to be assessed in a qualitative or quantitative way. The most prominent qualitative approach for representing preferences are CP-nets. Their clear graphical structure unifies an easy representation of user desires with nice computational properties when computing the best outcome. Here, we introduce ontological CP-nets, which allow the representation of preferences using a CP-net over an ontological domain, i.e., variable values are logical formulas constrained relative to a background domain ontology.

Thomas Lukasiewicz, Maria Vanina Martinez, and Gerardo I. Simari
Consistent Answers in Probabilistic Datalog+/- Ontologies
In M. Krötzsch and U. Straccia, editors, Proceedings of the 6th International Conference on Web Reasoning and Rule Systems (RR 2012), pp. 156-171, Vienna, Austria, September 2012. Volume 7497 of Lecture Notes in Computer Science, Springer, 2012.

The Datalog+/- family of ontology languages is especially useful for representing and reasoning over lightweight ontologies, and has many applications in the context of query answering and information extraction for the Semantic Web. It is widely accepted that it is necessary to develop a principled way to handle uncertainty in this domain. In addition to uncertainty as an inherent aspect of the Web, one must also deal with forms of uncertainty due to inconsistency. In this paper, we take an important step in this direction by developing inconsistency-tolerant semantics for query answering in a probabilistic extension of Datalog+/-. The main contributions of this paper are: (i) extension and generalization to probabilistic ontologies of the well-known concepts of repairs and consistent answers to queries from databases; (ii) complexity analysis for the problems of consistency checking, repair identification, and consistent query answering; and (iii) adaptation of the intersection semantics (a sound heuristic for consistent answers) to probabilistic ontologies, yielding a subset of probabilistic Datalog+/- that is tractable modulo the cost of computing probabilities.

Thomas Lukasiewicz, Maria Vanina Martinez, Giorgio Orsi, and Gerardo I. Simari
Heuristic Ranking in Tightly Coupled Probabilistic Description Logics
In N. de Freitas and K. Murphy, editors, Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence (UAI 2012), pp. 554-563, Catalina Island, USA, August 2012. AUAI Press, 2012.

The Semantic Web effort has steadily been gaining traction in the recent years. In particular,Web search companies are recently realizing that their products need to evolve towards having richer semantic search capabilities. Description logics (DLs) have been adopted as the formal underpinnings for Semantic Web languages used in describing ontologies. Reasoning under uncertainty has recently taken a leading role in this arena, given the nature of data found on theWeb. In this paper, we present a probabilistic extension of the DL EL++ (which underlies the OWL2 EL profile) using Markov logic networks (MLNs) as probabilistic semantics. This extension is tightly coupled, meaning that probabilistic annotations in formulas can refer to objects in the ontology. We show that, even though the tightly coupled nature of our language means that many basic operations are data-intractable, we can leverage a sublanguage of MLNs that allows to rank the atomic consequences of an ontology relative to their probability values (called ranking queries) even when these values are not fully computed. We present an anytime algorithm to answer ranking queries, and provide an upper bound on the error that it incurs, as well as a criterion to decide when results are guaranteed to be correct.

Thomas Lukasiewicz, Maria Vanina Martinez, and Gerardo I. Simari
Inconsistency-Tolerant Query Rewriting for Linear Datalog+/-
In P. Barcelo and R. Pichler, editors, Proceedings of Datalog 2.0, pp. 123-134, Vienna, Austria, September 2012. Volume 7494 of Lecture Notes in Computer Science, Springer, 2012.

Inconsistency management in knowledge bases is an important problem that has been studied for a long time. During the recent years, additional interest in this topic has been sparked with the advent of the Semantic Web, which has made this problem even more relevant, since inconsistencies are very likely to occur in open environments such as the Web. Inconsistency-tolerant semantics to query answering have therefore become of special interest for representation and reasoning formalisms for the Semantic Web. Datalog+/- is a family of ontology languages that is in particular useful for representing and reasoning over lightweight ontologies in the Semantic Web. In this paper, we focus on inconsistency-tolerant query answering under the intersection semantics in linear Datalog+/-, a sublanguage of Datalog+/- that generalizes the DL-Lite family of tractable description logics (DLs). In particular, we show that query answering in linear Datalog+/- is first-order rewritable under this inconsistency-tolerant semantics, and therefore very efficiently computable in the data complexity.

Thomas Lukasiewicz, Maria Vanina Martinez, and Gerardo I. Simari
Inconsistency Handling in Datalog+/- Ontologies
In L. De Raedt, C. Bessière, D. Dubois, P. Doherty, P. Frasconi, F. Heintz, P. J. F. Lucas, editors, Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012), pp. 558-563, Montpellier, France, August 2012. Volume 242 of Frontiers in Artificial Intelligence and Applications, IOS Press, 2012.

The advent of the Semantic Web has made the problem of inconsistency management especially relevant. Datalog+/- is a family of ontology languages that is in particular useful for representing and reasoning over lightweight ontologies in the Semantic Web. In this paper, we study different semantics for query answering in inconsistent Datalog+/- ontologies. We develop a general framework for inconsistency management in Datalog+/- ontologies based on incision functions from belief revision, in which we can characterize several query answering semantics as special cases: (i) consistent answers, originally developed for relational databases and recently adopted for some classes of description logics (DLs), (ii) intersection semantics, a sound approximation of consistent answers, and (iii) lazy consistent answers, a novel alternative semantics that offers a good compromise between quality of answers and computation time. We also provide complexity results for query answering under the different semantics, including data tractability results.

Georg Gottlob, André Hernich, Clemens Kupke, and Thomas Lukasiewicz
Equality-Friendly Well-Founded Semantics and Applications to Description Logics
In Y. Kazakov, D. Lembo, and F. Wolter, editors, Proceedings of the 25th International Workshop on Description Logics (DL 2012), Rome, Italy, June 2012. Volume 846 of CEUR Workshop Proceedings, CEUR-WS.org, 2012.

We tackle the problem of defining a well-founded semantics (WFS) for Datalog rules with existentially quantified variables in their heads and negations in their bodies. In particular, we provide a 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.

Georg Gottlob, André Hernich, Clemens Kupke, and Thomas Lukasiewicz
Equality-Friendly Well-Founded Semantics and Applications to Description Logics
In J. Hoffmann and B. Selman, editors, Proceedings of the 26th National Conference on Artificial Intelligence (AAAI 2012), pp. 757-764, Toronto, Ontario, Canada, July 2012. AAAI Press, 2012.

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.

Georg Gottlob, Thomas Lukasiewicz, and Gerardo I. Simari
Answering Threshold Queries in Probabilistic Datalog+/- Ontologies
In S. Benferhat and J. Grant, editors, Proceedings of the 5th International Conference on Scalable Uncertainty Management (SUM 2011), pp. 401-414, Dayton, Ohio, October 2011. Volume 6929 of Lecture Notes in Computer Science, Springer, 2011.

The recently introduced Datalog+/- family of ontology languages is especially useful for representing and reasoning over lightweight ontologies, and is set to play a central role in the context of query answering and information extraction for the Semantic Web. Recently, it has become apparent that it is necessary to develop a principled way to handle uncertainty in this domain. In addition to uncertainty as an inherent aspect of the Web, one must also deal with forms of uncertainty due to inconsistency and incompleteness, uncertainty resulting from automatically processing Web data, as well as uncertainty stemming from the integration of multiple heterogeneous data sources. In this paper, we take an important step in this direction by developing the first probabilistic extension of Datalog+/-. This extension uses Markov logic networks as underlying probabilistic semantics. Here, we especially focus on scalable algorithms for answering threshold queries, which correspond to the question "what is the set of all atoms that are inferred from a given probabilistic ontology with a probability of at least p?". These queries are especially relevant to Web information extraction, since uncertain rules lead to uncertain facts, and only information with a certain minimum confidence is desired. We present two algorithms: a basic approach and one based on heuristics that is guaranteed to return sound results.

Georg Gottlob, Thomas Lukasiewicz, and Gerardo I. Simari
Conjunctive Query Answering in Probabilistic Datalog+/- Ontologies
In S. Rudolph and C. Gutierrez, editors, Proceedings of the 5th International Conference on Web Reasoning and Rule Systems (RR 2011), pp. 77-92, Galway, Ireland, August 2011. Volume 6902 of Lecture Notes in Computer Science, Springer, 2011.

Datalog+/- is a recently developed family of ontology languages that is especially useful for representing and reasoning over lightweight ontologies, and is set to play a central role in the context of query answering and information extraction for the Semantic Web. It has recently become apparent that it is necessary to develop a principled way to handle uncertainty in this domain; in addition to uncertainty as an inherent aspect of the Web, one must also deal with forms of uncertainty due to inconsistency and incompleteness, uncertainty resulting from automatically processing Web data, as well as uncertainty stemming from the integration of multiple heterogeneous data sources. In this paper, we present two algorithms for answering conjunctive queries over a probabilistic extension of guarded Datalog+/- that uses Markov logic networks as the underlying probabilistic semantics. Conjunctive queries ask: "what is the probability that a given set of atoms hold?". These queries are especially relevant to Web information extraction, since extractors often work with uncertain rules and facts, and decisions must be made based on the likelihood that certain facts are inferred. The first algorithm for answering conjunctive queries is a basic one using classical forward chaining (known as the chase procedure), while the second one is a backward chaining algorithm and works on a specific subset of guarded Datalog+/-; it can be executed as an anytime algorithm for greater scalability.

Claudia d'Amato, Nicola Fanizzi, Bettina Fazzinga, Georg Gottlob, and Thomas Lukasiewicz
Combining Semantic Web Search with the Power of Inductive Reasoning
In A. Deshpande and A. Hunter, editors, Proceedings of the 4th International Conference on Scalable Uncertainty Management (SUM 2010), pp. 137-150, Toulouse, France, September 2010. Volume 6379 of Lecture Notes in Computer Science, Springer, 2010.

With the introduction of the Semantic Web as a future substitute of the Web, the key task for the Web, namely, Web search, is evolving towards some novel form of Semantic Web search. A very promising recent approach to Semantic Web search is based on combining standard Web pages and search queries with ontological background knowledge, and using standard Web search engines as the main inference motor of Semantic Web search. In this paper, we continue this line of research. First, we further explore the completeness of the above Semantic web search. Second, and as the central contribution of this paper, we propose to further enhance this approach by the use of inductive reasoning techniques. This increases the robustness of Semantic Web search, as it adds the important ability to handle inconsistencies, noise, and incompleteness, which are all very likely to occur in distributed and heterogeneous environments such as the Web. In particular, inductive reasoning allows to infer (from training individuals) new knowledge, which is not logically deducible. We also report on a prototype implementation of the new approach based on inductive reasoning and its experimental evaluations.

Andrea Calì, Georg Gottlob, Michael Kifer, Thomas Lukasiewicz, and Andreas Pieris
Ontological Reasoning with F-Logic Lite and its Extensions
In M. Fox and D. Poole, editors, Proceedings of the 24th National Conference on Artificial Intelligence (AAAI 2010), pp. 1660-1665, Atlanta, Georgia, USA, July 2010. AAAI Press, 2010.

Answering queries posed over knowledge bases is a central problem in knowledge representation and database theory. In the database area, checking query containment is an important query optimization and schema integration technique. In knowledge representation it has been used for object classification, schema integration, service discovery, and more. In the presence of a knowledge base, the problem of query containment is strictly related to that of query answering; indeed, the two are reducible to each other; we focus on the latter, and our results immediately extend to the former.

Bettina Fazzinga, Giorgio Gianforme, Georg Gottlob, and Thomas Lukasiewicz
Semantic Web Search Based on Ontological Conjunctive Queries
In S. Link and H. Prade, editors, Proceedings of the 6th International Symposium on Foundations of Information and Knowledge Systems (FoIKS 2010), pp. 153-172, Sofia, Bulgaria, February 2010. Volume 5956 of Lecture Notes in Computer Science, Springer, 2010.

Many experts predict that the next huge step forward in Web information technology will be achieved by adding semantics to Web data, and will possibly consist of (some form of) the Semantic Web. In this paper, we present a novel approach to Semantic Web search, which is based on ontological conjunctive queries, and which combines standard Web search with ontological background knowledge, as it is, e.g., available in Semantic Web repositories. We show how standard Web search engines can be used as the main inference motor for processing ontology-based semantic search queries on the Web. We develop the formal model behind this approach and also provide an implementation in desktop search. Furthermore, we report on extensive experimental results.

Claudia d'Amato, Floriana Esposito, Nicola Fanizzi, Bettina Fazzinga, Georg Gottlob, and Thomas Lukasiewicz
Inductive Reasoning and Semantic Web Search
In S. Y. Shin, S. Ossowski, M. Schumacher, M. J. Palakal, and C.-C. Hung, editors, Proceedings of the 25th ACM Symposium on Applied Computing (SAC 2010), pp. 1446-1447, Sierre, Switzerland, March 2010. ACM Press, 2010.

Extensive research activities are recently directed towards the Semantic Web as a future form of the Web. Consequently, Web search as the key technology of the Web is evolving towards some novel form of Semantic Web search. A very promising recent approach to such Semantic Web search is based on combining standard Web search with ontological background knowledge and using standard Web search engines as the main inference motor of Semantic Web search. In this paper, we propose to further enhance this approach to Semantic Web search by the use of inductive reasoning. This adds the important ability to handle inconsistencies, noise, and incompleteness, which often occur in distributed and heterogeneous environments, such as the Web. We report on a prototype implementation of the new approach and extensive experimental results.

Claudia d'Amato, Nicola Fanizzi, Floriana Esposito, and Thomas Lukasiewicz
Inductive Query Answering and Concept Retrieval Exploiting Local Models
In B. Lazzerini, L. Jain, A. Abraham, F. Marcelloni, F. Herrera, and V. Loia, editors, Proceedings of the 9th International Conference on Intelligent Systems Design and Applications (ISDA 2009), pp. 1209-1214, Pisa, Italy, November/December 2009. IEEE Computer Society, 2009.

We present a classification method, founded in the instance-based learning and the disjunctive version space approach, for performing approximate retrieval from knowledge bases expressed in Description Logics. It is able to supply answers, even though they are not logically entailed by the knowledge base (e.g. because of its incompleteness or when there are inconsistent assertions). Moreover, the method may also induce new knowledge that can be employed to make the ontology population task semi-automatic. The method has been experimentally tested showing that it is sound and effective.

Claudia d'Amato, Nicola Fanizzi, Bettina Fazzinga, Georg Gottlob, and Thomas Lukasiewicz
Combining Semantic Web Search with the Power of Inductive Reasoning
In F. Bobillo, P. C. G. da Costa, C. d'Amato, N. Fanizzi, K. B. Laskey, K. J. Laskey, T. Lukasiewicz, T. Martin, M. Nickles, M. Pool, and P. Smrž, editors, Proceedings of the 5th International Workshop on Uncertainty Reasoning for the Semantic Web (URSW 2009), pp. 15-26, Washington DC, USA, October 2009. Volume 527 of CEUR Workshop Proceedings, CEUR-WS.org, 2009.

Extensive research activities are recently directed towards the Semantic Web as a future form of the Web. Consequently, Web search as the key technology of the Web is evolving towards some novel form of Semantic Web search. A very promising recent approach to such Semantic Web search is based on combining standard Web search with ontological background knowledge and using standard Web search engines as the main inference motor of Semantic Web search. In this paper, we propose to further enhance this approach to Semantic Web search by the use of inductive reasoning techniques. This adds especially the important ability to handle inconsistencies, noise, and incompleteness, which are very likely to occur in distributed and heterogeneous environments, such as the Web. We report on a prototype implementation of the new approach and experimental results.

Thomas Lukasiewicz and Azzurra Ragone
Combining Boolean Games with the Power of Ontologies for Automated Multi-Attribute Negotiation in the Semantic Web
In R. Baeza-Yates, J. Lang, S. Mitra, S. Parsons, and G. Pasi, editors, Proceedings of the 2009 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT 2009), pp. 395-402, Milan, Italy, September 2009. IEEE Computer Society, 2009.

Multi-attribute negotiation has been extensively studied from a game-theoretic viewpoint. In negotiation settings, utility functions are used to express agent preferences. Normal and extensive form games, however, have the drawback of requiring an explicit representation of utility functions, listing the utility values for all combinations of strategies. Therefore, several logical preference languages have been proposed, to specify multi-attribute utility functions in a compact way. Among these approaches, there are also Boolean games. In this paper, we introduce Boolean description logic games, which are a combination of Boolean games with ontological background knowledge, formulated using expressive description logics. In this way, it is possible to enhance the expressiveness of preference representation, maintaining the advantages of the game-theoretic approach. We include and discuss several generalizations, showing their practical usefulness within a service negotiation scenario. Furthermore, we also provide complexity results.

Claudia d'Amato, Nicola Fanizzi, Floriana Esposito, and Thomas Lukasiewicz
Approximate Classification of Semantically Annotated Web Resources Exploiting Pseudo-metrics Induced by Local Models
In R. Baeza-Yates, B. Berendt, E. Bertino, E.-P. Lim, and G. Pasi, editors, Proceedings of the 2009 IEEE/WIC/ACM International Conference on Web Intelligence (WI 2009), pp. 689-692, Milan, Italy, September 2009. IEEE Computer Society, 2009.

We present a classification method, founded in the instance-based learning and the disjunctive version space approach, for performing approximate retrieval from knowledge bases expressed in Description Logics. The method supplies answers even if the knowledge base of reference is inconsistent or incomplete. Moreover, the method may also induce new knowledge that can be suggested to the knowledge engineer, thus making the ontology population task semi-automatic.

Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz
Tractable Query Answering over Ontologies with Datalog±
In B. Cuenca Grau, I. Horrocks, B. Motik, and U. Sattler, editors, Proceedings of the 22nd International Workshop on Description Logics (DL 2009), Oxford, UK, July 2009. Volume 477 of CEUR Workshop Proceedings, CEUR-WS.org, 2009.

We present a family of expressive extensions of Datalog, called Datalog±, as a new paradigm for query answering over ontologies. The Datalog± family admits existentially quantified variables in rule heads, and has suitable restrictions to ensure highly efficient ontology querying. In particular, we show that query answering under so-called guarded Datalog± is PTIME-complete in data complexity, and that query answering under so-called linear Datalog± is in AC0 in data complexity. We also show how negative constraints and a general class of key constraints can be added to Datalog while keeping ontology querying tractable. We then show that linear Datalog±, enriched with a special class of key constraints, generalizes the well-known DL-Lite family of tractable description logics. Furthermore, the Datalog± family is of interest in its own right and can, moreover, be used in various contexts such as data integration and data exchange. This work is a short version of [8].

Thomas Lukasiewicz and Azzurra Ragone
A Combination of Boolean Games with Description Logics for Automated Multi-Attribute Negotiation
In B. Cuenca Grau, I. Horrocks, B. Motik, and U. Sattler, editors, Proceedings of the 22nd International Workshop on Description Logics (DL 2009), Oxford, UK, July 2009. Volume 477 of CEUR Workshop Proceedings, CEUR-WS.org, 2009.

Multi-attribute negotiation has been extensively studied from a game-theoretic viewpoint. In negotiation settings, utility functions are used to express agent preferences. Normal and extensive form games, however, have the drawback of requiring an explicit representation of utility functions, listing the utility values for all combinations of strategies. Therefore, several logical preference languages have been proposed, to specify multi-attribute utility functions in a compact way. Among these approaches, there are also Boolean games. In this paper, we introduce Boolean description logic games, which are a combination of Boolean games with ontological background knowledge, formulated using expressive description logics. In this way, it is possible to enhance the expressiveness of preference representation, maintaining the advantages of the game-theoretic approach. We include and discuss several generalizations, showing their practical usefulness within a service negotiation scenario. Furthermore, we also provide complexity results.

Andrea Calì, Georg Gottlob, and Thomas Lukasiewicz
A General Datalog-Based Framework for Tractable Query Answering over Ontologies
In J. Paredaens and J. Su, editors, Proceedings of the 28th ACM Symposium on Principles of Database Systems (PODS 2009), pp. 77-86, Providence, Rhode Island, USA, June/July 2009. ACM Press, 2009.

In this paper, we introduce a family of expressive extensions of Datalog, called Datalog+/-, as a new paradigm for query answering over ontologies. The Datalog+/- family admits existentially quantified variables in rule heads, and has suitable restrictions to ensure highly efficient ontology querying. We show in particular that Datalog+/- generalizes the DL-Lite family of tractable description logics, which are the most common tractable ontology languages in the context of the Semantic Web and databases. We also show how stratified negation can be added to Datalog+/- while keeping ontology querying tractable. Furthermore, the Datalog+/- family is of interest in its own right and can, moreover, be used in various contexts such as data integration and data exchange.

Claudia d'Amato, Nicola Fanizzi, and Thomas Lukasiewicz
Tractable Reasoning with Bayesian Description Logics
In S. Greco and T. Lukasiewicz, editors, Proceedings of the 2nd International Conference on Scalable Uncertainty Management (SUM 2008), pp. 146-159, Naples, Italy, October 2008. Volume 5291 of Lecture Notes in Computer Science, Springer, 2008.

The DL-Lite family of tractable description logics lies between the semantic web languages RDFS and OWL Lite. In this paper, we present a probabilistic generalization of the DL-Lite description logics, which is based on Bayesian networks. As an important feature, the new probabilistic description logics allow for flexibly combining terminological and assertional pieces of probabilistic knowledge. We show that the new probabilistic description logics are rich enough to properly extend both the DL-Lite description logics as well as Bayesian networks. We also show that satisfiability checking and query processing in the new probabilistic description logics is reducible to satisfiability checking and query processing in the DL-Lite family. Furthermore, we show that satisfiability checking and answering unions of conjunctive queries in the new logics can be done in LogSpace in the data complexity. For this reason, the new probabilistic description logics are very promising formalisms for data-intensive applications in the Semantic Web involving probabilistic uncertainty.

Thomas Lukasiewicz and Azzurra Ragone
Combining Boolean Games with the Power of Ontologies for Automated Multi-Attribute Negotiation in the Semantic Web
In R. L. Hernandez, T. Di Noia, and I. Toma, editors, Proceedings of the 2nd International Workshop on Service Matchmaking and Resource Retrieval in the Semantic Web (SMRR 2008), Karlsruhe, Germany, October 2008. Volume 416 of CEUR Workshop Proceedings, CEUR-WS.org, 2008.

Recently, multi-attribute negotiation has been extensively studied from a game-theoretic viewpoint. Since normal and extensive form games have the drawback of requiring an explicit representation of utility functions (listing the utility values for all combinations of strategies), logical preference languages have been proposed, which provide a convenient way to compactly specify multiattribute utility functions. Among these preference languages, there are also Boolean games. In this paper, towards automated multi-attribute negotiation in the Semantic Web, we introduce Boolean description logic games, which are a combination of Boolean games with ontological background knowledge, formulated in expressive description logics. We include and discuss several generalizations, and show how a travel and a service negotiation scenario can be formulated in Boolean description logic games, which shows their practical usefulness.

Nicola Fanizzi, Claudia d'Amato, Floriana Esposito, and Thomas Lukasiewicz
Representing Uncertain Concepts in Rough Description Logics via Contextual Indiscernibility Relations
In F. Bobillo, P. C. G. da Costa, C. d'Amato, N. Fanizzi, K. B. Laskey, K. J. Laskey, T. Lukasiewicz, T. Martin, M. Nickles, M. Pool, and P. Smrž, editors, Proceedings of the 4th International Workshop on Uncertainty Reasoning for the Semantic Web (URSW 2008), Karlsruhe, Germany, October 2008. Volume 423 of CEUR Workshop Proceedings, CEUR-WS.org, 2008.

We investigate on modeling uncertain concepts via rough description logics, which are an extension of traditional description logics by a simple mechanism to handle approximate concept definitions through lower and upper approximations of concepts based on a rough-set semantics. This allows to apply rough description logics for modeling uncertain knowledge. Since these approximations are ultimately grounded on an indiscernibility relationship, the paper explores possible logical and numerical ways for defining such relationships based on the considered knowledge. In particular, the notion of context is introduced, allowing for the definition of specific equivalence relationships, to be used for approximations as well as for determining similarity measures, which may be exploited for introducing a notion of tolerance in the indiscernibility.

Andrea Calì, Thomas Lukasiewicz, Livia Predoiu, and Heiner Stuckenschmidt
Tightly Integrated Probabilistic Description Logic Programs for Representing Ontology Mappings
In S. Hartmann and G. Kern-Isberner, editors, Proceedings of the 5th International Symposium on Foundations of Information and Knowledge Systems (FoIKS 2008), pp. 178-198, Pisa, Italy, February 2008. Volume 4932 of Lecture Notes in Computer Science, Springer, 2008.

Creating mappings between ontologies is a common way of approaching the semantic heterogeneity problem on the Semantic Web. To fit into the landscape of semantic web languages, a suitable, logic-based representation formalism for mappings is needed. We argue that such a formalism has to be able to deal with uncertainty and inconsistencies in automatically created mappings. We analyze the requirements for such a formalism, and we propose a novel approach to probabilistic description logic programs as such a formalism, which tightly combines disjunctive logic programs under the answer set semantics with both description logics and Bayesian probabilities. We define the language, and we show that it can be used to resolve inconsistencies and merge mappings from different matchers based on the level of confidence assigned to different rules. Furthermore, we explore the computational aspects of consistency checking and query processing in tightly integrated probabilistic description logic programs. We show that these problems are decidable and computable, respectively, and that they can be reduced to consistency checking and cautious/brave reasoning, respectively, in tightly integrated disjunctive description logic programs. We also analyze the complexity of consistency checking and query processing in the new probabilistic description logic programs in special cases. In particular, we present a special case of these problems with polynomial data complexity.

Andrea Calì, Thomas Lukasiewicz, Livia Predoiu, and Heiner Stuckenschmidt
A Framework for Representing Ontology Mappings under Probabilities and Inconsistency
In F. Bobillo, P. C. G. da Costa, C. d'Amato, N. Fanizzi, F. Fung, T. Lukasiewicz, T. Martin, M. Nickles, Y. Peng, M. Pool, P. Smrž, and P. Vojtáš, editors, Proceedings of the Third ISWC Workshop on Uncertainty Reasoning for the Semantic Web (URSW 2007), Busan, Korea, November 2007. Volume 327 of CEUR Workshop Proceedings, CEUR-WS.org, 2008.

Creating mappings between ontologies is a common way of approaching the semantic heterogeneity problem on the Semantic Web. To fit into the landscape of semantic web languages, a suitable, logic-based representation formalism for mappings is needed. We argue that such a formalism has to be able to deal with uncertainty and inconsistencies in automatically created mappings. We analyze the requirements for such a mapping language and present a formalism that combines tightly integrated description logic programs with independent choice logic for representing probabilistic information. We define the language, show that it can be used to resolve inconsistencies and merge mappings from different matchers based on the level of confidence assigned to different rules. We also analyze the computational aspects of consistency checking and query processing in tightly integrated probabilistic description logic programs.

Thomas Lukasiewicz and Umberto Straccia
Description Logic Programs under Probabilistic Uncertainty and Fuzzy Vagueness
In K. Mellouli, editor, Proceedings of the 9th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2007), pp. 187-198, Hammamet, Tunisia, October/November 2007. Volume 4724 of Lecture Notes in Computer Science, Springer, 2007.

This paper is directed towards an infrastructure for handling both uncertainty and vagueness in the Rules, Logic, and Proof layers of the Semantic Web. More concretely, we present probabilistic fuzzy description logic programs, which combine fuzzy description logics, fuzzy logic programs (with stratified nonmonotonic negation), and probabilistic uncertainty in a uniform framework for the Semantic Web. We define important concepts dealing with both probabilistic uncertainty and fuzzy vagueness, such as the expected truth value of a crisp sentence and the probability of a vague sentence. Furthermore, we describe a shopping agent example, which gives evidence of the usefulness of probabilistic fuzzy description logic programs in realistic web applications. In the extended report, we also provide algorithms for query processing in probabilistic fuzzy description logic programs, and we delineate a special case where query processing can be done in polynomial time in the data complexity.

Thomas Lukasiewicz
Tractable Probabilistic Description Logic Programs
In H. Prade and V.S. Subrahmanian, editors, Proceedings of the 1st International Conference on Scalable Uncertainty Management (SUM 2007), pp. 143-156, Washington DC, USA, October 2007. Volume 4772 of Lecture Notes in Computer Science, Springer, 2007.

We propose tractable probabilistic description logic programs (or probabilistic dl-programs) for the Semantic Web, which combine tractable description logics, normal programs under the answer set semantics, and probabilities. In particular, we introduce the total well-founded semantics for probabilistic dl-programs. Contrary to the previous answer set and well-founded semantics, it is defined for all probabilistic dl-programs and all probabilistic queries. Furthermore, tight (resp., tight literal) query processing under the total well-founded semantics coincides with tight (resp., tight literal) query processing under the previous well-founded (resp., answer set) semantics whenever the latter is defined. We then present an anytime algorithm for tight query processing in probabilistic dl-programs under the total well-founded semantics. We also show that tight literal query processing in probabilistic dl-programs under the total well-founded semantics can be done in polynomial time in the data complexity and is complete for EXP in the combined complexity. Finally, we describe an application of probabilistic dl-programs in probabilistic data integration for the Semantic Web.

Thomas Lukasiewicz and Umberto Straccia
Top-k Retrieval in Description Logic Programs under Vagueness for the Semantic Web
In H. Prade and V.S. Subrahmanian, editors, Proceedings of the 1st International Conference on Scalable Uncertainty Management (SUM 2007), pp. 16-30, Washington DC, USA, October 2007. Volume 4772 of Lecture Notes in Computer Science, Springer, 2007.

Description logics (DLs) and logic programs (LPs) are important representation languages for the Semantic Web. In this paper, we address an emerging problem in such languages, namely, the problem of evaluating ranked top-k queries. Specifically, we show how to compute the top-k answers in a data-complexity tractable combination of DLs and LPs under vagueness.

Andrea Calì and Thomas Lukasiewicz
Tightly Integrated Probabilistic Description Logic Programs for the Semantic Web
In V. Dahl and I. Niemelä, editors, Proceedings of the 23rd International Conference on Logic Programming (ICLP 2007), pp. 428-429, Porto, Portugal, September 2007. Volume 4670 of Lecture Notes in Computer Science, Springer, 2007.

We present a novel approach to probabilistic description logic programs for the Semantic Web, where a tight integration of disjunctive logic programs under the answer set semantics with description logics is generalized by probabilistic uncertainty. The approach has a number of nice features. In particular, it allows for a natural probabilistic data integration and for a natural representation of ontology mappings under probabilistic uncertainty and inconsistency. It also provides a natural integration of a situation-calculus based language for reasoning about actions with both description logics and probabilistic uncertainty.

Thomas Lukasiewicz
A Novel Combination of Answer Set Programming with Description Logics for the Semantic Web
In E. Franconi, M. Kifer, and W. May, editors, Proceedings of the 4th European Semantic Web Conference (ESWC 2007), pp. 384-398, Innsbruck, Austria, June 2007. Volume 4519 of Lecture Notes in Computer Science, Springer, 2007.

We present a novel combination of disjunctive logic programs under the answer set semantics with description logics for the Semantic Web. The combination is based on a well-balanced interface between disjunctive logic programs and description logics, which guarantees the decidability of the resulting formalism without assuming syntactic restrictions. We show that the new formalism has very nice semantic properties. In particular, it faithfully extends both disjunctive programs and description logics. Furthermore, we describe algorithms for reasoning in the new formalism, and we give a precise picture of its computational complexity. We also provide a special case with polynomial data complexity.

Thomas Lukasiewicz and Umberto Straccia
Tightly Integrated Fuzzy Description Logic Programs under the Answer Set Semantics for the Semantic Web
In M. Marchiori, J. Z. Pan, and C. de Sainte Marie, editors, Proceedings of the 1st International Conference on Web Reasoning and Rule Systems (RR 2007), pp. 289-298, Innsbruck, Austria, June 2007. Volume 4524 of Lecture Notes in Computer Science, Springer, 2007.

We present a novel approach to fuzzy dl-programs under the answer set semantics, which is a tight integration of fuzzy disjunctive programs under the answer set semantics with fuzzy description logics. From a different perspective, it is a generalization of tightly integrated disjunctive dl-programs by fuzzy vagueness in both the description logic and the logic program component. We show that the new formalism faithfully extends both fuzzy disjunctive programs and fuzzy description logics, and that under suitable assumptions, reasoning in the new formalism is decidable. Furthermore, we present a polynomial reduction of certain fuzzy dl-programs to tightly integrated disjunctive dl-programs. We also provide a special case of fuzzy dl-programs for which deciding consistency and query processing have both a polynomial data complexity.

Alessandro Farinelli, Alberto Finzi, and Thomas Lukasiewicz
Team Programming in Golog under Partial Observability
In M. M. Veloso, editor, Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), pp. 2097-2102, Hyderabad, India, January 2007. AAAI Press / IJCAI, 2007.

In this paper, we present the agent programming language TeamGolog, which is a novel approach to programming a team of cooperative agents under partial observability. Every agent is associated with a partial control program in Golog, which is completed by the TeamGolog interpreter in an optimal way by assuming a decision-theoretic semantics. The approach is based on the key concepts of a synchronization state and a communication state, which allow the agents to passively resp. actively coordinate their behavior, while keeping their belief states, observations, and activities invisible to the other agents. We show the usefulness of the approach in a rescue simulated domain.

Thomas Lukasiewicz
Fuzzy Description Logic Programs under the Answer Set Semantics for the Semantic Web
In T. Eiter, E. Franconi, R. Hodgson, and S. Stephens, editors, Proceedings of the 2nd International Conference on Rules and Rule Markup Languages for the Semantic Web (RuleML-2006), pp. 89-96, Athens, Georgia, USA, November 2006. IEEE Computer Society, 2006.

Vagueness and imprecision abound in multimedia information processing and retrieval. In this paper, towards dealing with vagueness and imprecision in the reasoning layers of the Semantic Web, we present an approach to fuzzy description logic programs under the answer set semantics. We generalize normal description logic programs (dl-programs) under the answer set semantics by fuzzy vagueness and imprecision. We define a canonical semantics of positive and stratified fuzzy dl-programs in terms of a unique least model and iterative least models, respectively. We then define the answer set semantics of general fuzzy dl-programs, and show in particular that all answer sets of a fuzzy dl-program are minimal models, and that the answer set semantics of positive and stratified fuzzy dl-programs coincides with their canonical least model and iterative least model semantics, respectively. Furthermore, we also provide a characterization of the canonical semantics of positive and stratified fuzzy dl-programs in terms of a fixpoint and an iterative fixpoint semantics, respectively.

Andrea Calì and Thomas Lukasiewicz
An Approach to Probabilistic Data Integration for the Semantic Web
In P. C. G. da Costa, K. B. Laskey, K. J. Laskey, F. Fung, and M. Pool, editors, Proceedings of the ISWC-2006 Workshop on Uncertainty Reasoning for the Semantic Web (URSW 2006), Athens, Georgia, USA, November 2006. Volume 218 of CEUR Workshop Proceedings, CEUR-WS.org, 2006.

In previous work, we have introduced probabilistic description logic programs for the Semantic Web, which combine description logics, normal programs under the answer set (resp., well-founded) semantics, and probabilistic uncertainty. In this paper, we continue this line of research. We propose an approach to probabilistic data integration for the Semantic Web that is based on probabilistic description logic programs, where probabilistic uncertainty is used to handle inconsistencies between different data sources. It is inspired by recent works on probabilistic data integration in the database and web community.

Thomas Lukasiewicz and Jörg Schellhase
Preferences, Links, and Probabilities for Ranking Objects in Ontologies
In P. C. G. da Costa, K. B. Laskey, K. J. Laskey, F. Fung, and M. Pool, editors, Proceedings of the ISWC-2006 Workshop on Uncertainty Reasoning for the Semantic Web (URSW 2006), Athens, Georgia, USA, November 2006. Volume 218 of CEUR Workshop Proceedings, CEUR-WS.org, 2006.

In previous work, we have introduced variable-strength conditional preferences for ranking objects in ontologies. In this paper, we continue this line of research. We propose a new ranking of objects, which integrates this user-defined preference ranking of objects with Google's importance ranking (called PageRank) based on the link structure between the objects. We also propose to use probabilistic description logics based on Bayesian networks and the description logic DL-Lite to compute the ranking of incompletely specified objects.

Alberto Finzi and Thomas Lukasiewicz
Adaptive Multi-Agent Programming in GTGolog
In G. Brewka, S. Coradeschi, A. Perini, and P. Traverso, editors, Proceedings of the 17th biennial European Conference on Artificial Intelligence (ECAI 2006), pp. 753-754, Riva del Garda, Italy, August/September 2006. IOS Press, 2006.

We present a novel approach to adaptive multi-agent programming, which is based on an integration of the agent programming language GTGolog with adaptive dynamic programming techniques. GTGolog combines explicit agent programming in Golog with game-theoretic multi-agent planning in stochastic games. In GTGolog, the transition probabilities and reward values of the domain must be provided with the model. The adaptive generalization of GTGolog proposed here is directed towards letting the agents themselves explore and adapt these data. We use high-level programs for the generation of both abstract states and optimal policies.

Thomas Lukasiewicz and Jörg Schellhase
Variable-Strength Conditional Preferences for Matchmaking in Description Logics
In P. Doherty, J. Mylopoulos, and C. Welty, editors, Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR 2006), pp. 164-174, Lake District, UK, June 2006. AAAI Press, 2006.

We present an approach to variable-strength conditional preferences for matchmaking and ranking objects in description logics. In detail, we introduce conditional preference bases, which consist of a description logic knowledge base and a finite set of variable-strength conditional preferences, and which are associated with a formal semantics based on ranking functions. We then define the notions of consistency and preferential entailment for conditional preference bases, which strictly generalize epsilon-consistency and entailment in Pearl's System Z+ in default reasoning from conditional knowledge bases, respectively. We also describe some semantic properties of preferential entailment. We then show how preferential entailment can be used to define a distance measure between two conditional preference bases. We also define functions for ranking objects relative to a conditional preference base, and we describe an application in the area of literature search. Finally, we provide algorithms for solving the main computational tasks related to conditional preference bases.

Thomas Lukasiewicz and Jörg Schellhase
Variable-Strength Conditional Preferences for Ranking Objects in Ontologies
In Y. Sure and J. Domingue, editors, Proceedings of the 3rd European Semantic Web Conference (ESWC 2006), pp. 288-302, Budva, Montenegro, June 2006. Volume 4011 of Lecture Notes in Computer Science, Springer, 2006.

We introduce conditional preference bases as a means for ranking objects in ontologies. Conditional preference bases consist of a description logic knowledge base and a finite set of variable-strength conditional preferences. They are inspired by Goldszmidt and Pearl's approach to default reasoning from conditional knowledge bases in System Z+. We define a notion of consistency for conditional preference bases, and show how consistent conditional preference bases can be used for ranking objects in ontologies. We also provide algorithms for computing the rankings. To give evidence of the usefulness of this approach in practice, we describe an application in the area of literature search.

Alberto Finzi and Thomas Lukasiewicz
Adaptive Multi-Agent Programming in GTGolog
In C. Freksa, M. Kohlhase, and K. Schill, editors, Proceedings of the 29th Annual German Conference on Artificial Intelligence (KI 2006), pp. 389-403, Bremen, Germany, June 2006. Volume 4314 of Lecture Notes in Computer Science, Springer, 2007.

We present a novel approach to adaptive multi-agent programming, which is based on an integration of the agent programming language GTGolog with adaptive dynamic programming techniques. GTGolog combines explicit agent programming in Golog with multi-agent planning in stochastic games. A drawback of this framework, however, is that the transition probabilities and reward values of the domain must be known in advance and then cannot change anymore. But such data is often not available in advance and may also change over the time. The adaptive generalization of GTGolog in this paper is directed towards letting the agents themselves explore and adapt these data, which is more useful for realistic applications. We use high-level programs for generating both abstract states and optimal policies, which benefits from the deep integration between action theory and high-level programs in the Golog framework.

Alberto Finzi and Thomas Lukasiewicz
Game-Theoretic Agent Programming in Golog under Partial Observability
In C. Freksa, M. Kohlhase, and K. Schill, editors, Proceedings of the 29th Annual German Conference on Artificial Intelligence (KI 2006), pp. 113-127, Bremen, Germany, June 2006. Volume 4314 of Lecture Notes in Computer Science, Springer, 2007.

We present the agent programming language POGTGolog, which integrates explicit agent programming in Golog with game-theoretic multi-agent planning in partially observable stochastic games. It deals with the case of one team of cooperative agents under partial observability, where the agents may have different initial belief states and not necessarily the same rewards. POGTGolog allows for specifying a partial control program in a high-level logical language, which is then completed by an interpreter in an optimal way. To this end, we define a formal semantics of POGTGolog programs in terms of Nash equilibria, and we specify a POGTGolog interpreter that computes one of these Nash equilibria. We illustrate the usefulness of POGTGolog along a rugby scenario.

Thomas Lukasiewicz
Stratified Probabilistic Description Logic Programs
In P. C. G. da Costa, K. B. Laskey, K. J. Laskey, and M. Pool, editors, Proceedings of the ISWC-2005 Workshop on Uncertainty Reasoning for the Semantic Web (URSW 2005), pp. 87-97, Galway, Ireland, November 2005. Volume 173 of CEUR Workshop Proceedings, CEUR-WS.org, 2006.

In previous work, we have introduced probabilistic description logic programs (or pdl-programs), which are a combination of description logic programs (or dl-programs) under the answer set and well-founded semantics with Poole's independent choice logic. Such programs are directed towards sophisticated representation and reasoning techniques that allow for probabilistic uncertainty in the Rules, Logic, and Proof layers of the Semantic Web. In this paper, we continue this line of research. We concentrate on the special case of stratified probabilistic description logic programs (or spdl-programs). In particular, we present an algorithm for query processing in such pdl-programs, which is based on a reduction to computing the canonical model of stratified dl-programs.

Alberto Finzi and Thomas Lukasiewicz
Game-Theoretic Reasoning about Actions in Nonmonotonic Causal Theories
In C. Baral, G. Greco, N. Leone, and G. Terracina, editors, Proceedings of the 8th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2005), pp. 185-197, Diamante, Cosenza, Italy, September 2005. Volume 3662 of Lecture Notes in Computer Science, Springer, 2005.

We present the action language GC+ for reasoning about actions in multi-agent systems under probabilistic uncertainty and partial observability, which is an extension of the action language C+ that is inspired by partially observable stochastic games (POSGs). We provide a finite-horizon value iteration for this framework and show that it characterizes finite-horizon Nash equilibria. We also describe how the framework can be implemented on top of nonmonotonic causal theories. We then present acyclic action descriptions in GC+ as a special case where transitions are computable in polynomial time. We also give an example that shows the usefulness of our approach in practice.

Thomas Lukasiewicz
Probabilistic Description Logic Programs
In L. Godo, editor, Proceedings of the 8th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2005), pp. 737-749, Barcelona, Spain, July 2005. Volume 3571 of Lecture Notes in Computer Science, Springer, 2005.

Towards sophisticated representation and reasoning techniques that allow for probabilistic uncertainty in the Rules, Logic, and Proof layers of the Semantic Web, we present probabilistic description logic programs (or pdl-programs), which are a combination of description logic programs (or dl-programs) under the answer set semantics and the well-founded semantics with Poole's independent choice logic.We show that query processing in such pdl-programs can be reduced to computing all answer sets of dl-programs and solving linear optimization problems, and to computing the well-founded model of dl-programs, respectively. Furthermore, we show that the answer set semantics of pdl-programs is a refinement of the well-founded semantics of pdl-programs.

Alberto Finzi and Thomas Lukasiewicz
Game-Theoretic Golog under Partial Observability
In F. Dignum, V. Dignum, S. Koenig, S. Kraus, M. Pechoucek, M. Singh, D. Steiner, S. Thompson, and M. Wooldridge, editors, Proceedings of the 4th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2005), pp. 1301-1302, Utrecht, The Netherlands, July 2005. ACM Press, 2005.

We present the agent programming language POGTGolog, which combines explicit agent programming in Golog with game-theoretic multi-agent planning in a special kind of partially observable stochastic games (POSGs). The approach allows for partially specifying a high-level control program for a system of multiple agents, and for optimally filling in missing details by viewing it as a generalization of a special POSG and computing a Nash equilibrium.

Thomas Lukasiewicz
Nonmonotonic Probabilistic Logics under Variable-Strength Inheritance with Overriding: Algorithms and Implementation in NMPROBLOG
In F. G. Cozman, R. Nau, and T. Seidenfeld, editors, Proceedings of the 4th International Symposium on Imprecise Probabilities and their Applications (ISIPTA 2005), pp. 230-239, CMU, Pittsburgh, PA, USA, July 2005.

In previous work, I have introduced nonmonotonic probabilistic logics under variable-strength inheritance with overriding. They are formalisms for probabilistic reasoning from sets of strict logical, default logical, and default probabilistic sentences, which are parameterized through a value lambda in [0,1] that describes the strength of the inheritance of default probabilistic knowledge. In this paper, I continue this line of research. I present algorithms for deciding consistency of strength lambda and for computing tight consequences of strength lambda, which are based on reductions to the standard problems of deciding satisfiability and of computing tight logical consequences in model-theoretic probabilistic logic. Furthermore, I describe an implementation of these algorithms in the system NMPROBLOG.

Alberto Finzi and Thomas Lukasiewicz
Game-Theoretic Agent Programming in Golog under Partial Observability
In P. Gmytrasiewicz and S. Parsons, editors, Proceedings of the IJCAI-2005 Workshop on Game-Theoretic and Decision-Theoretic Agents (GTDT 2005), July 2005.

In this paper, we present the agent programming language POGTGolog, which is a combination of explicit agent programming in Golog with game-theoretic multi-agent planning in a special kind of partially observable stochastic games (POSGs). It is a generalization of the agent programming language GTGolog by partial observability. The approach allows for partially specifying a high-level control program for a system of multiple agents, and for optimally filling in missing details by viewing it as a generalization of a special POSG and computing a Nash equilibrium. We illustrate this approach along a robotic rugby example.

Thomas Eiter, Thomas Lukasiewicz, Roman Schindlauer, and Hans Tompits
Well-Founded Semantics for Description Logic Programs in the Semantic Web
In G. Antoniou and H. Boley, editors, Proceedings of the 3rd International Workshop on Rules and Rule Markup Languages for the Semantic Web (RuleML 2004), pp. 81-97, Hiroshima, Japan, November 2004. Volume 3323 of Lecture Notes in Computer Science, Springer, 2004.

In previous work, towards the integration of rules and ontologies in the SemanticWeb, we have proposed a combination of logic programming under the answer set semantics with the description logics SHIF(D) and SHOIN(D), which underly the Web ontology languages OWL Lite and OWL DL, respectively. More precisely, we have introduced description logic programs (or dl-programs), which consist of a description logic knowledge base L and a finite set of description logic rules P, and we have defined their answer set semantics. In this paper, we continue this line of research. Here, as a central contribution, we present the well-founded semantics for dl-programs, and we analyze its semantic properties. In particular, we show that it generalizes the well-founded semantics for ordinary normal programs. Furthermore, we show that in the general case, the well-founded semantics of dl-programs is a partial model that approximates the answer set semantics, whereas in the positive and the stratified case, it is a total model that coincides with the answer set semantics. Finally, we also provide complexity results for dl-programs under the well-founded semantics.

Alberto Finzi and Thomas Lukasiewicz
Relational Markov Games
In J. Alferes and J. Leite, editors, Proceedings of the 9th European Conference on Logics in Artificial Intelligence (JELIA 2004), pp. 320-333, Lisbon, Portugal, September 2004. Volume 3229 of Lecture Notes in Computer Science, Springer, 2004.

Towards a compact and elaboration-tolerant first-order representation of Markov games, we introduce relational Markov games, which combine standard Markov games with first-order action descriptions in a stochastic variant of the situation calculus. We focus on the zero-sum two-agent case, where we have two agents with diametrically opposed goals. We also present a symbolic value iteration algorithm for computing Nash policy pairs in this framework.

Alberto Finzi and Thomas Lukasiewicz
Game-Theoretic Agent Programming in Golog
In R. López de Mántaras and L. Saitta, editors, Proceedings of the 16th biennial European Conference on Artificial Intelligence (ECAI 2004), pp. 23-27, Valencia, Spain, August 2004. IOS Press, 2004.

We present the agent programming language GTGolog, which integrates explicit agent programming in Golog with game-theoretic multi-agent planning in Markov games. It is a generalization of DTGolog to a multi-agent setting, where we have two competing single agents or two competing teams of agents. The language allows for specifying a control program for a single agent or a team of agents in a high-level logical language. The control program is then completed by an interpreter in an optimal way against another single agent or another team of agents, by viewing it as a generalization of a Markov game, and computing a Nash strategy. We illustrate the usefulness of this approach along a robotic soccer example.

Luca Iocchi, Thomas Lukasiewicz, Daniele Nardi, and Riccardo Rosati
Reasoning about Actions with Sensing under Qualitative and Probabilistic Uncertainty
In R. López de Mántaras and L. Saitta, editors, Proceedings of the 16th biennial European Conference on Artificial Intelligence (ECAI 2004), pp. 818-822, Valencia, Spain, August 2004. IOS Press, 2004.

We focus on the aspect of sensing in reasoning about actions under qualitative and probabilistic uncertainty. We extend an A-related action language by actions with nondeterministic and probabilistic effects, and define a formal semantics in terms of deterministic, nondeterministic, and probabilistic transitions between epistemic states. We then introduce the notions of a conditional plan and its goodness in this framework, and we formulate the conditional planning problem. We present an algorithm for solving it, which is proved to be sound and complete in the sense that it produces all optimal plans. We also report on a first prototype implementation of this algorithm. An application in a robotic-soccer scenario underlines the usefulness of our formalism in realistic applications.

Thomas Eiter, Thomas Lukasiewicz, Roman Schindlauer, and Hans Tompits
Combining Answer Set Programming with Description Logics for the Semantic Web
In D. Dubois, C.Welty, and M.-A.Williams, editors, Proceedings of the 9th International Conference on Principles of Knowledge Representation and Reasoning (KR 2004), pp. 141-151, Whistler, Canada, June 2004. AAAI Press, 2004.

Towards the integration of rules and ontologies in the Semantic Web, we propose a combination of logic programming under the answer set semantics with the description logics SHIF(D) and SHOIN(D), which underly the Web ontology languages OWL Lite and OWL DL, respectively. This combination allows for building rules on top of ontologies but also, to a limited extent, building ontologies on top of rules. We introduce description logic programs (dl-programs), which consist of a description logic knowledge base L and a finite set of description logic rules (dl-rules) P. Such rules are similar to usual rules in logic programs with negation as failure, but may also contain queries to L, possibly default negated, in their bodies. We define Herbrand models for dl-programs, and show that satisfiable positive dl-programs have a unique least Herbrand model. More generally, consistent stratified dl-programs can be associated with a unique minimal Herbrand model that is characterized through iterative least Herbrand models. We then generalize the (unique) minimal Herbrand model semantics for positive and stratified dl-programs to a strong answer set semantics for all dl-programs, which is based on a reduction to the least model semantics of positive dl-programs. We also define a weak answer set semantics based on a reduction to the answer sets of ordinary logic programs. Strong answer sets are weak answer sets, and both properly generalize answer sets of ordinary normal logic programs. We then give fixpoint characterizations for the (unique) minimal Herbrand model semantics of positive and stratified dl-programs, and show how to compute these models by finite fixpoint iterations. Furthermore, we give a precise picture of the complexity of deciding strong and weak answer set existence for a dl-program.

Thomas Lukasiewicz
Weak Nonmonotonic Probabilistic Logics
In D. Dubois, C.Welty, and M.-A.Williams, editors, Proceedings of the 9th International Conference on Principles of Knowledge Representation and Reasoning (KR 2004), pp. 23-33, Whistler, Canada, June 2004. AAAI Press, 2004.

Towards probabilistic formalisms for resolving local inconsistencies under model-theoretic probabilistic entailment, we present probabilistic generalizations of Pearl's entailment in System Z and Lehmann's lexicographic entailment. We then analyze the nonmonotonic and semantic properties of the new notions of entailment. In particular, we show that they satisfy the rationality postulates of System P and the property of Rational Monotonicity. Moreover, we show that model-theoretic probabilistic entailment is stronger than the new notion of lexicographic entailment, which in turn is stronger than the new notion of entailment in System Z. As an important feature of the new notions of entailment in System Z and lexicographic entailment, we show that they coincide with model-theoretic probabilistic entailment whenever there are no local inconsistencies. We also show that the new notions of entailment in System Z and lexicographic entailment are proper generalizations of their classical counterparts. Finally, we present algorithms for reasoning under the new formalisms, and we give a precise picture of its computational complexity.

Luca Iocchi, Thomas Lukasiewicz, Daniele Nardi, and Riccardo Rosati
Qualitative and Probabilistic Uncertainty in Reasoning about Actions with Sensing
In J. Delgrande and T. Schaub, editors, Proceedings of the 10th International Workshop on Non-Monotonic Reasoning (NMR 2004), pp. 240-248, Whistler, Canada, June 2004.

We present the description logic PN-ALCK_NF^alpha for reasoning about actions with sensing under qualitative and probabilistic uncertainty, which is an extension of the description logic ALCK_NF^alpha by actions with nondeterministic and probabilistic effects. We define a formal semantics of PN-ALCK_NF^alpha in terms of deterministic, nondeterministic, and probabilistic transitions between epistemic states, which are sets of possible states of the world. We introduce the notions of a conditional plan and its goodness under qualitative and probabilistic uncertainty. We then formulate the problem of conditional planning in this framework, and we present an algorithm for solving it. This algorithm is based on a reduction to reasoning in description logics, and is shown to be sound and complete in the sense that it generates all optimal plans. We also describe an application in a robotic-soccer scenario.

Thomas Eiter and Thomas Lukasiewicz
Probabilistic Reasoning about Actions in Nonmonotonic Causal Theories
In C. Meek and U. Kjaerulff, editors, Proceedings of the 19th Conference on Uncertainty in Artificial Intelligence (UAI 2003), pp. 192-199, Acapulco, Mexico, August 2003. Morgan Kaufmann, 2003.

We present the language PC+ for probabilistic reasoning about actions, which is a generalization of the action language C+ that allows to deal with probabilistic as well as nondeterministic effects of actions. We define a formal semantics of PC+ in terms of probabilistic transitions between sets of states. Using a concept of a history and its belief state, we then show how several important problems in reasoning about actions can be concisely formulated in our formalism.

Alberto Finzi and Thomas Lukasiewicz
Structure-Based Causes and Explanations in the Independent Choice Logic
In C. Meek and U. Kjaerulff, editors, Proceedings of the 19th Conference on Uncertainty in Artificial Intelligence (UAI 2003), pp. 225-232, Acapulco, Mexico, August 2003. Morgan Kaufmann, 2003.

This paper is directed towards combining Pearl's structural-model approach to causal reasoning with high-level formalisms for reasoning about actions. More precisely, we present a combination of Pearl's structural-model approach with Poole's independent choice logic. We show how probabilistic theories in the independent choice logic can be mapped to probabilistic causal models. This mapping provides the independent choice logic with appealing concepts of causality and explanation from the structural-model approach. We illustrate this along Halpern and Pearl's sophisticated notions of actual cause, explanation, and partial explanation. This mapping also adds first-order modeling capabilities and explicit actions to the structural-model approach.

Thomas Lukasiewicz
Probabilistic Lexicographic Entailment under Variable-Strength Inheritance with Overriding
In N. L. Zhang and T. D. Nielsen, editors, Proceedings of the 7th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2003), pp. 576-587, Aalborg, Denmark, July 2003. Volume 2711 of Lecture Notes in Computer Science, Springer, 2003.

In previous work, I have presented approaches to nonmonotonic probabilistic reasoning, which is a probabilistic generalization of default reasoning from conditional knowledge bases. In this paper, I continue this exciting line of research. I present a new probabilistic generalization of Lehmann's lexicographic entailment, called lex_lambda-entailment, which is parameterized through a value lambda in [0,1] that describes the strength of the inheritance of purely probabilistic knowledge. Roughly, the new notion of entailment is obtained from logical entailment in model-theoretic probabilistic logic by adding (i) the inheritance of purely probabilistic knowledge of strength lambda, and (ii) a mechanism for resolving inconsistencies due to the inheritance of logical and purely probabilistic knowledge. I also explore the semantic properties of lex_lambda-entailment.

Rosalba Giugno and Thomas Lukasiewicz
P-SHOQ(D): A Probabilistic Extension of SHOQ(D) for Probabilistic Ontologies in the Semantic Web
In S. Flesca, S. Greco, N. Leone, and G. Ianni, editors, Proceedings of the 8th European Conference on Logics in Artificial Intelligence (JELIA 2002), pp. 86-97, Cosenza, Italy, September 2002. Volume 2424 of Lecture Notes in Computer Science, Springer, 2002.

Ontologies play a central role in the development of the Semantic Web, as they provide precise definitions of shared terms in web resources. One important web ontology language is DAML+OIL; it has a formal semantics and a reasoning support through a mapping to the expressive description logic with the addition of inverse roles. In this paper, we present a probabilistic extension of SHOQ(D), called P-SHOQ(D), to allow for dealing with probabilistic ontologies in the Semantic Web. The description logic P-SHOQ(D) is based on the notion of probabilistic lexicographic entailment from probabilistic default reasoning. It allows to express rich probabilistic knowledge about concepts and instances, as well as default knowledge about concepts. We also present sound and complete reasoning techniques for P-SHOQ(D), which are based on reductions to classical reasoning in SHOQ(D) and to linear programming, and which show in particular that reasoning in P-SHOQ(D) is decidable.

Thomas Eiter and Thomas Lukasiewicz
Causes and Explanations in the Structural-Model Approach: Tractable Cases
In A. Darwiche and N. Friedman, editors, Proceedings of the 18th Conference on Uncertainty in Artificial Intelligence (UAI 2002), pp. 146-153, Edmonton, Canada, August 2002. Morgan Kaufmann, 2002.

In this paper, we continue our research on the algorithmic aspects of Halpern and Pearl's causes and explanations in the structural-model approach. To this end, we present new characterizations of weak causes for certain classes of causal models, which show that under suitable restrictions deciding causes and explanations is tractable. To our knowledge, these are the first explicit tractability results for the structural-model approach.

Thomas Eiter and Thomas Lukasiewicz
Complexity Results for Explanations in the Structural-Model Approach
In D. Fensel, F. Giunchiglia, D. McGuinness, and M.-A. Williams, editors, Proceedings of the Eighth International Conference on Principles of Knowledge Representation and Reasoning (KR 2002), pp. 49-60, Toulouse, France, April 2002. Morgan Kaufmann, 2002.

We analyze the computational complexity of Halpern and Pearl's (causal) explanations in the structural-model approach, which are based on their notions of weak and actual causality. In particular, we give a precise picture of the complexity of deciding explanations, alpha-partial explanations, and partial explanations, and of computing the explanatory power of partial explanations. Moreover, we analyze the complexity of deciding whether an explanation or an alpha-partial explanation over certain variables exists. We also analyze the complexity of deciding explanations and partial explanations in the case of succinctly represented context sets, and the complexity of deciding explanations in the general case of situations. All complexity results are derived for the general case, as well as for the restriction to the case of binary causal models, in which all endogenous variables may take only two values. To our knowledge, no complexity results for explanations in the structural-model approach have been derived so far. Our results give insight into the computational structure of Halpern and Pearl's explanations, and pave the way for efficient algorithms and implementations.

Thomas Lukasiewicz
Nonmonotonic Probabilistic Logics between Model-Theoretic Probabilistic Logic and Probabilistic Logic under Coherence
In S. Benferhat and E. Giunchiglia, editors, Proceedings of the 9th International Workshop on Non-Monotonic Reasoning (NMR 2002), pp. 265-274, Toulouse, France, April 2002.

Recently, it has been shown that probabilistic entailment under coherence is weaker than model-theoretic probabilistic entailment. Moreover, probabilistic entailment under coherence is a generalization of default entailment in System P. In this paper, we continue this line of research by presenting probabilistic generalizations of more sophisticated notions of classical default entailment that lie between model-theoretic probabilistic entailment and probabilistic entailment under coherence. That is, the new formalisms properly generalize their counterparts in classical default reasoning, they are weaker than model-theoretic probabilistic entailment, and they are stronger than probabilistic entailment under coherence. The new formalisms are useful especially for handling probabilistic inconsistencies related to conditioning on zero events. They can also be applied for probabilistic belief revision. More generally, in the same spirit as a similar previous paper, this paper sheds light on exciting new formalisms for probabilistic reasoning beyond the well-known standard ones.

Veronica Biazzo, Angelo Gilio, Thomas Lukasiewicz, and Giuseppe Sanfilippo
Probabilistic Logic under Coherence, Model-Theoretic Probabilistic Logic, and Default Reasoning
In S. Benferhat and P. Besnard, editors, Proceedings of the 6th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2001), pp. 290-302, Toulouse, France, September 2001. Volume 2143 of Lecture Notes in Computer Science, Springer, 2001.

We study probabilistic logic under the viewpoint of the coherence principle of de Finetti. In detail, we explore the relationship between coherence-based and model-theoretic probabilistic logic. Interestingly, we show that the notions of g-coherence and of g-coherent entailment can be expressed by combining notions in model-theoretic probabilistic logic with concepts from default reasoning. Crucially, we even show that probabilistic reasoning under coherence is a probabilistic generalization of default reasoning in system P. That is, we provide a new probabilistic semantics for system P, which is neither based on infinitesimal probabilities nor on atomic-bound (or also big-stepped) probabilities. These results also give new insight into default reasoning with conditional objects.

Thomas Lukasiewicz
Fixpoint Characterizations for Many-Valued Disjunctive Logic Programs with Probabilistic Semantics
In T. Eiter, W. Faber, and M. Truszczynski, editors, Proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2001), pp. 336-350, Vienna, Austria, September 2001. Volume 2173 of Lecture Notes in Computer Science, Springer, 2001.

In this paper, we continue to explore many-valued disjunctive logic programs with probabilistic semantics. In particular, we newly introduce the least model state semantics for such programs. We show that many-valued disjunctive logic programs under the semantics of minimal models, perfect models, stable models, and least model states can be unfolded to equivalent classical disjunctive logic programs under the respective semantics. Thus, existing technology for classical disjunctive logic programming can be used to implement many-valued disjunctive logic programming. Using these results on unfolding many-valuedness, we then give many-valued fixpoint characterizations for the set of all minimal models and the least model state. We also describe an iterative fixpoint characterization for the perfect model semantics under finite local stratification.

Thomas Eiter and Thomas Lukasiewicz
Complexity Results for Structure-Based Causality
In B. Nebel, editor, Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI-01), pp. 35-40, Seattle, Washington, USA, August 2001. Morgan Kaufmann, 2001. IJCAI-01 Distinguished Paper Award (best paper of 796 submitted and 197 accepted papers at IJCAI-01).

We analyze the computational complexity of causal relationships in Pearl's structural models, where we focus on causality between variables, event causality, and probabilistic causality. In particular, we analyze the complexity of the sophisticated notions of weak and actual causality by Halpern and Pearl. In the course of this, we also prove an open conjecture by Halpern and Pearl, and establish other semantic results. To our knowledge, no complexity aspects of causal relationships have been considered so far, and our results shed light on this issue.

Thomas Lukasiewicz
Probabilistic Logic Programming under Inheritance with Overriding
In J. S. Breese and D. Koller, editors, Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence (UAI 2001), pp. 329-336, Seattle, Washington, USA, August 2001. Morgan Kaufmann, 2001.

We present probabilistic logic programming under inheritance with overriding. This approach is based on new notions of entailment for reasoning with conditional constraints, which are obtained from the classical notion of logical entailment by adding inheritance with overriding. This is done by using recent approaches to probabilistic default reasoning with conditional constraints. We analyze the semantic properties of the new entailment relations. We also present algorithms for probabilistic logic programming under inheritance with overriding, and we analyze its complexity in the propositional case.

Veronica Biazzo, Angelo Gilio, Thomas Lukasiewicz, and Giuseppe Sanfilippo
Probabilistic Logic under Coherence: Complexity and Algorithms
In G. de Cooman, T. L. Fine, and T. Seidenfeld, editors, Proceedings of the 2nd International Symposium on Imprecise Probabilities and their Applications (ISIPTA 2001), pp. 51-61, Ithaca, New York, USA, June 2001.

We study probabilistic logic under the viewpoint of the coherence principle of de Finetti. In detail, we explore the relationship between coherence-based and classical model-theoretic probabilistic logic. Interestingly, we show that the notions of g-coherence and of g-coherent entailment can be expressed by combining notions in model-theoretic probabilistic logic with concepts from default reasoning. Using these results, we analyze the computational complexity of probabilistic reasoning under coherence. Moreover, we present new algorithms for deciding g-coherence and for computing tight g-coherent intervals, which reduce these tasks to standard reasoning tasks in model-theoretic probabilistic logic. Thus, efficient techniques for model-theoretic probabilistic reasoning can immediately be applied for probabilistic reasoning under coherence, for example, column generation techniques. We then describe two other interesting techniques for efficient model-theoretic probabilistic reasoning in the conjunctive case.

Thomas Eiter and Thomas Lukasiewicz
New Tractable Cases in Default Reasoning from Conditional Knowledge Bases
In M. Ojeda-Aciego, I. P. de Guzmán, G. Brewka, and L. M. Pereira, editors, Proceedings of the 7th European Workshop on Logics in Artificial Intelligence (JELIA 2000), pp. 313-328, Málaga, Spain, September 29 - October 2, 2000. Volume 1919 of Lecture Notes in Computer Science, Springer, 2000.

We present new tractable cases for default reasoning from conditional knowledge bases. In detail, we introduce q-Horn conditional knowledge bases, which allow for a limited use of disjunction.We show that previous tractability results for epsilon-entailment, proper epsilon-entailment, and z- and z+-entailment in the Horn case can be extended to the q-Horn case. Moreover, we present feedback-free-Horn conditional knowledge bases, which constitute a new, meaningful class of conditional knowledge bases. We show that the maximum entropy approach and lexicographic entailment are tractable in the feedback-free-Horn case. Our results complement and extend previous results, and contribute in refining the tractability / intractability frontier of default reasoning from conditional knowledge bases.

Thomas Lukasiewicz
Credal Networks under Maximum Entropy
In C. Boutilier and M. Goldszmidt, editors, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence (UAI 2000), pp. 363-370, Stanford, California, USA, July 2000. Morgan Kaufmann, 2000.

We apply the principle of maximum entropy to select a unique joint probability distribution from the set of all joint probability distributions specified by a credal network. In detail, we start by showing that the unique joint distribution of a Bayesian tree coincides with the maximum entropy model of its conditional distributions. This result, however, does not hold anymore for general Bayesian networks. We thus present a new kind of maximum entropy models, which are computed sequentially. We then show that for all general Bayesian networks, the sequential maximum entropy model coincides with the unique joint distribution. Moreover, we apply the new principle of sequential maximum entropy to interval Bayesian networks and more generally to credal networks. We especially show that this application is equivalent to a number of small local entropy maximizations.

Thomas Eiter and Thomas Lukasiewicz
Complexity Results for Default Reasoning from Conditional Knowledge Bases
In A. G. Cohn, F. Giunchiglia, and B. Selman, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the Seventh International Conference (KR 2000), pp. 62-73, Breckenridge, Colorado, USA, April 2000. Morgan Kaufmann, 2000.

Conditional knowledge bases have been proposed as belief bases that include defeasible rules (also called defaults) of the form "phi->psi", which informally read as "generally, if phi then psi". Such rules may have exceptions, which can be handled in different ways. A number of entailment semantics for conditional knowledge bases have been proposed in the literature. However, while the semantic properties and interrelationships of these formalisms are quite well understood, about their algorithmic properties only partial results are known so far. In this paper, we fill these gaps and draw a precise picture of the complexity of default reasoning from conditional knowledge bases: Given a conditional knowledge base KB and a default "phi->psi", does KB entail "phi->psi"? We classify the complexity of this problem for a number of well-known approaches (including Goldszmidt et al.'s maximum entropy approach and Geffner's conditional entailment). We consider the general propositional case as well as syntactic restrictions (in particular, to Horn and literal-Horn conditional knowledge bases). Furthermore, we analyze the effect of precomputing rankings for the respective approaches. Our results complement and extend previous results, and contribute in exploring the tractability / intractability frontier of default reasoning from conditional knowledge bases.

Thomas Lukasiewicz
Probabilistic Default Reasoning with Conditional Constraints
In C. Baral, and M. Truszczynski, editors, Proceedings of the Eighth International Workshop on Non-Monotonic Reasoning (NMR 2000), Breckenridge, Colorado, USA, April 2000. Linköping Electronic Articles in Computer and Information Science, Vol. 5 (2000): nr 024.

We propose a combination of probabilistic reasoning from conditional constraints with approaches to default reasoning from conditional knowledge bases. In detail, we generalize the notions of Pearl's entailment in system Z, Lehmann's lexicographic entailment, and Geffner's conditional entailment to conditional constraints. We give some examples that show that the new notions of z-, lexicographic, and conditional entailment have similar properties like their classical counterparts. Moreover, we show that the new notions of z-, lexicographic, and conditional entailment are proper generalizations of both their classical counterparts and the classical notion of logical entailment for conditional constraints.

Thomas Eiter, Thomas Lukasiewicz, and Michael Walter
Extension of the Relational Algebra to Probabilistic Complex Values
In K.-D. Schewe and B. Thalheim, editors, Proceedings of the International Symposium on Foundations of Information and Knowledge Systems (FoIKS 2000), Burg (Spreewald), Germany, February 2000. Volume 1762 of Lecture Notes in Computer Science, pp. 94-115, Springer, 2000.

We present a probabilistic data model for complex values. More precisely, we introduce probabilistic complex value relations, which combine the concept of probabilistic relations with the idea of complex values in a uniform framework. We then define an algebra for querying database instances, which comprises the operations of selection, projection, renaming, join, Cartesian product, union, intersection, and difference. We finally show that most of the query equivalences of classical relational algebra carry over to our algebra on probabilistic complex value relations. Hence, query optimization techniques for classical relational algebra can easily be applied to optimize queries on probabilistic complex value relations.

Thomas Lukasiewicz
Many-Valued Disjunctive Logic Programs with Probabilistic Semantics
In M. Gelfond, N. Leone, and G. Pfeifer, editors, Proceedings of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 1999), El Paso, Texas, USA, December 1999. Volume 1730 of Lecture Notes in Computer Science, pp. 277-289, Springer, 1999.

We present many-valued disjunctive logic programs in which classical disjunctive logic program clauses are extended by a truth value that respects the material implication. Interestingly, these many-valued disjunctive logic programs have both a probabilistic semantics in probabilities over possible worlds and a truth-functional semantics. We then define minimal, perfect, and stable models and show that they have the same properties like their classical counterparts. In particular, perfect and stable models are always minimal models. Under local stratification, the perfect model semantics coincides with the stable model semantics. Finally, we show that some special cases of propositional many-valued disjunctive logic programming under minimal, perfect, and stable model semantics have the same complexity like their classical counterparts.

Thomas Lukasiewicz and Gabriele Kern-Isberner
Probabilistic Logic Programming under Maximum Entropy
In A. Hunter and S. Parsons, editors, Proceedings of the 5th European Conference on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 1999), London, UK, July 1999. Volume 1638 of Lecture Notes in Computer Science, pp. 279-292, Springer, 1999.

In this paper, we focus on the combination of probabilistic logic programming with the principle of maximum entropy. We start by defining probabilistic queries to probabilistic logic programs and their answer substitutions under maximum entropy. We then present an efficient linear programming characterization for the problem of deciding whether a probabilistic logic program is satisfiable. Finally, and as a central contribution of this paper, we introduce an efficient technique for approximative probabilistic logic programming under maximum entropy. This technique reduces the original entropy maximization task to solving a modified and relatively small optimization problem.

Thomas Lukasiewicz
Probabilistic and Truth-Functional Many-Valued Logic Programming
In Proceedings of the 29th IEEE International Symposium on Multiple-Valued Logic (ISMVL 1999), pp. 236-241, Freiburg, Germany, May 1999. IEEE Computer Society, 1999.

We introduce probabilistic many-valued logic programs in which the implication connective is interpreted as material implication. We show that probabilistic many-valued logic programming is computationally more complex than classical logic programming. More precisely, some deduction problems that are P-complete for classical logic programs are shown to be co-NP-complete for probabilistic many-valued logic programs. We then focus on many-valued logic programming in Pr_n* as an approximation of probabilistic many-valued logic programming. Surprisingly, many-valued logic programs in Pr_n* have both a probabilistic semantics in probabilities over a set of possible worlds and a truth-functional semantics in the finite-valued Lukasiewicz logics L_n. Moreover, many-valued logic programming in Pr_n* has a model and fixpoint characterization, a proof theory, and computational properties that are very similar to those of classical logic programming.

Thomas Lukasiewicz
Many-Valued First-Order Logics with Probabilistic Semantics
In G. Gottlob, E. Grandjean, and K. Seyr, editors, Proceedings of the Annual Conference of the European Association for Computer Science Logic (CSL 1998), Brno, Czech Republic, August 1998. Volume 1584 of Lecture Notes in Computer Science, pp. 415-429, Springer, 1999.

We present n-valued first-order logics with a purely probabilistic semantics. We then introduce a new probabilistic semantics of n-valued first-order logics that lies between the purely probabilistic semantics and the truth-functional semantics of the n-valued Lukasiewicz logics L_n. Within this semantics, closed formulas of classical first-order logics that are logically equivalent in the classical sense also have the same truth value under all n-valued interpretations. Moreover, this semantics is shown to have interesting computational properties. More precisely, n-valued logical consequence in disjunctive logic programs with n-valued disjunctive facts can be reduced to classical logical consequence in n-1 layers of classical disjunctive logic programs. Moreover, we show that n-valued logic programs have a model and a fixpoint semantics that are very similar to those of classical logic programs. Finally, we show that some important deduction problems in n-valued logic programs have the same computational complexity like their classical counterparts.

Thomas Lukasiewicz
Probabilistic Logic Programming
In H. Prade, editor, Proceedings of the 13th biennial European Conference on Artificial Intelligence (ECAI 1998), pp. 388-392, Brighton, UK, August 1998. J. Wiley & Sons, 1998.

We present a new approach to probabilistic logic programs with a possible worlds semantics. Classical program clauses are extended by a subinterval of [0,1] that describes the range for the conditional probability of the head of a clause given its body. We show that deduction in the defined probabilistic logic programs is computationally more complex than deduction in classical logic programs. More precisely, restricted deduction problems that are P-complete for classical logic programs are already NP-hard for probabilistic logic programs. We then elaborate a linear programming approach to probabilistic deduction that is efficient in interesting special cases. In the best case, the generated linear programs have a number of variables that is linear in the number of ground instances of purely probabilistic clauses in a probabilistic logic program.

Thomas Lukasiewicz
Magic Inference Rules for Probabilistic Deduction under Taxonomic Knowledge
In G. F. Cooper and S. Moral, editors, Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence (UAI 1998), pp. 354-361, Madison, Wisconsin, USA, July 1998. Morgan Kaufmann, 1998.

We present locally complete inference rules for probabilistic deduction from taxonomic and probabilistic knowledge bases over conjunctive events. Crucially, in contrast to similar inference rules in the literature, our inference rules are locally complete for conjunctive events and under additional taxonomic knowledge. We discover that our inference rules are extremely complex and that it is at first glance not clear at all where the deduced tightest bounds come from. Moreover, analyzing the global completeness of our inference rules, we find examples of globally very incomplete probabilistic deductions. More generally, we even show that all systems of inference rules for taxonomic and probabilistic knowledge bases over conjunctive events are globally incomplete. We conclude that probabilistic deduction by the iterative application of inference rules on interval restrictions for conditional probabilities, even though considered very promising in the literature so far, seems very limited in its field of application.

Thomas Lukasiewicz
Probabilistic Deduction with Conditional Constraints over Basic Events
In A. G. Cohn, L. K. Schubert, and S. C. Shapiro, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the 6th International Conference (KR 1998), pp. 380-391, Trento, Italy, June 1998. Morgan Kaufmann, 1998.

We show that probabilistic deduction with conditional constraints over basic events is NP-hard. We then focus on the special case of probabilistic deduction in conditional constraint trees. We elaborate very efficient and globally complete techniques for probabilistic deduction. More precisely, for exact conditional constraint trees, we present a local approach to globally complete probabilistic deduction, which runs in linear time in the size of the conditional constraint trees. For general conditional constraint trees, we show that globally complete probabilistic deduction can be done by solving global nonlinear programs. We elaborate how these nonlinear programs can be transformed into equivalent linear programs, which are solvable in polynomial time in the size of the conditional constraint trees.

Thomas Lukasiewicz
Efficient Global Probabilistic Deduction from Taxonomic and Probabilistic Knowledge-Bases over Conjunctive Events
In F. Golshani and K. Makki, editors, Proceedings of the 6th International ACM Conference on Information and Knowledge Management (CIKM 1997), pp. 75-82, Las Vegas, Nevada, USA, November 1997. ACM Press, 1997.

We present a new, efficient linear programming approach to probabilistic deduction from probabilistic knowledge bases over conjunctive events. We show that this approach enables us to solve the classical problem of probabilistic deduction along a chain of basic events in polynomial time in the length of the chain. We then elaborate how taxonomic knowledge can be exploited in our new approach for an increased efficiency. We also present important new results for the classical linear programming approach to probabilistic deduction under taxonomic knowledge.

Thomas Lukasiewicz, Werner Kießling, Gerhard Köstler, and Ulrich Güntzer
Taxonomic and Uncertain Integrity Constraints in Object-Oriented Databases - the TOP Approach
In N. Pisinou, A. Silberschatz, E. K. Park, and K. Makki, editors, Proceedings of the 4th International Conference on Information and Knowledge Management (CIKM 1995), pp. 241-249, Baltimore, Maryland, USA, November 1995. ACM Press, 1995.

We present a coherent modeling and reasoning methodology to extend object-oriented databases towards taxonomic and uncertain integrity constraints. Our so-called TOP database model enriches current ISA-hierarchies by more general t-classes to improve conceptual modeling. The t-classes themselves are then integrated with probabilistic constraints to express uncertainty. We give an efficient algorithm for checking the modeling-consistency of a probabilistic knowledge base. As a typical application domain for TOP, we exemplify how various aspects of a portfolio management system can be modeled. We also demonstrate that recent probabilistic inference methods, relying on a careful interaction between taxonomic and uncertain knowledge, can be applied in this context.

Thomas Lukasiewicz
Uncertain Reasoning in Concept Lattices
In C. Froidevaux and J. Kohlas, editors, Proceedings of the 3rd European Conference on Symbolic and Quantative Approaches to Reasoning and Uncertainty (ECSQARU 1995), Fribourg, Switzerland, July 1995. Volume 946 of Lecture Notes in Computer Science, pp. 293-300, Springer, 1995.

This paper presents concept lattices as a natural representation of class hierarchies in object-oriented databases and frame-based knowledge representations. We show how to extend concept lattices by uncertainty in the form of conditional probabilities. We illustrate that uncertain reasoning within the hierarchical structure of concept lattices can be performed efficiently and makes uncertain conclusions more precise.

Werner Kießling, Thomas Lukasiewicz, Gerhard Köstler, and Ulrich Güntzer
The TOP Database Model - Taxonomy, Object-Orientation and Probability
In Proceedings of the International Workshop on Uncertainty in Databases and Deductive Systems, pp. 71-82, Ithaca, New York, USA, November 1994.

We propose to extend object-oriented databases by a language to specify taxonomic knowledge over so-called t-classes, which are compatible with, but more expressive than existent ISA-hierarchies. Separated from, but closely coupled with such taxonomic knowledge, we offer uncertain constraints in the form of a probabilistic language. The information content of such taxonomic and probabilistic knowledge can be visualized naturally by special Hasse-diagrams. A project to build a TOP-prototype using object-oriented technology like OMT and O2, deductive technology like Datalog S and CORAL, and uncertain technology from our DUCK experience is under way.