DL ON FRIDAY, JULY 18TH

ABSTRACT. Amsterdam-style logicians view modal logic as a fragment of classical logic, and description logicians view their own formalisms in much the same way. Moreover, first-order logic itself can be viewed as a modest fragment of the higher-order logics of Frege and Russell, a fragment with useful model-theoretic properties. All in all, the fine structure of logic is a key topic in contemporary research, as the intensive study of (say) the 2-variable and various guarded fragments attest.

In this talk I want to consider the role of logical fragments in applications. I will focus on applications in natural language, as this is an area rich in non-monotonic and defeasible inference. Moreover, as my perspective is that of computational (rather than theoretical) linguistics, I am interested in efficient solutions to computational tasks - that is, in fragments of computation. Drawing on a running example involving applications of description logic and classical planning to a dialogue system, I will discuss the role of computation to provide 'pragmatic glue' that lets us work with small well-explored logical fragments, while simultaneously providing the dynamics required to model various forms of non-monotonicity.

ABSTRACT. In the last 20 years many proposals have been made to incorporate non-monotonic reasoning into description logics, ranging from approaches based on default logic and circumscription to those based on preferential semantics. In particular, the non-monotonic description logic ALC+Tmin uses a combination of the preferential semantics with minimization of a certain kind of concepts, which represent atypical instances of a class of elements. One of its drawbacks is that it suffers from the problem known as the property blocking inheritance, which can be seen as a weakness from an inferential point of view. In this paper we propose an extension of ALC+Tmin, namely ALC+T+min, with the purpose to solve the mentioned problem. In addition, we show the close connection that exists between ALC+T+min and concept-circumscribed knowledge bases. Finally, we study the complexity of deciding the classical reasoning tasks in ALC+T+min.

ABSTRACT. Nonmonotonic Description Logic (DL-) programs couple nonmonotonic logic programs with DL-ontologies through queries in a loose way which may lead to inconsistency, i.e., lack of an answer set. Recently defined repair answer sets remedy this but a straightforward computation method lacks practicality. We present a novel evaluation algorithm for deletion repair answer sets based on support sets, which reduces evaluation of DL-Lite_A ontology queries to constraint matching. This leads to significant performance gains towards inconsistency management in practice.

ABSTRACT. The semantic web is an open and distributed environment in which it is hard to guarantee consistency of knowledge and information. Under the standard two-valued semantics everything is entailed if knowledge and information is inconsistent. The semantics of the paraconsistent logic LP offers a solution. However, if the available knowledge and information is consistent, the set of conclusions entailed under the three-valued semantics of the paraconsistent logic LP is smaller than the set of conclusions entailed under the two-valued semantics. Preferring conflict-minimal three-valued interpretations eliminates this difference.

Preferring conflict-minimal interpretations introduces non-monotonicity. To handle the non-monotonicity, this paper proposes an assumption-based argumentation system. Assumptions needed to close branches of a semantic tableaux form the arguments. Stable extensions of the set of derived arguments correspond to conflict minimal interpretations and conclusions entailed by all conflict-minimal interpretations are supported by arguments in all stable extensions.

ABSTRACT. Recently several inconsistency-tolerant semantics have been introduced for querying inconsistent description logic knowledge bases. Most of these semantics rely on the notion of a repair, defined as an inclusion-maximal subset of the facts (ABox) which is consistent with the ontology (TBox). In this paper, we study variants of two popular inconsistency-tolerant semantics obtained by replacing classical repairs by various types of preferred repair. We analyze the complexity of query answering under the resulting semantics, focusing on the lightweight logic DL-Lite_R. Unsurprisingly, query answering is intractable in all cases, but we nonetheless identify one notion of preferred repair, based upon priority levels, whose data complexity is "only" coNP-complete. This leads us to propose an approach combining incomplete tractable methods with calls to a SAT solver. An experimental evaluation of the approach shows good scalability on realistic cases.

ABSTRACT. We investigate various types of query rewriting over ontologies given in the standard temporal logic LTL as well as combinations of LTL with DL-Lite logics. In particular, we consider FO(<)-rewritings that can use the temporal precedence relation, FO(<,+)-rewritings that can also employ the arithmetic predicate PLUS, and rewritings to finite automata with data given on the automaton tape.

ABSTRACT. Temporal query abduction is the problem of hypothesizing a minimal set of temporal data which, given some fixed background knowledge, warrants the entailment of the query. This problem formally underlies a variety of forms of explanatory and diagnostic reasoning in the context of time series data, data streams, or otherwise temporally annotated structured information. In this paper, we consider (temporally ordered) data represented in Description Logics from the popular DL-Lite family and Temporal Query Language, based on the combination of LTL with conjunctive queries. In this defined setting, we study the complexity of temporal query abduction, assuming different restrictions on the problem and minimality criteria for abductive solutions. As a result, we draw several revealing demarcation lines between NP-, DP- and PSpace-complete variants of the problem.

ABSTRACT. We design and investigate a new interval based temporal description logic, EL-Lambda, which is based on an Annotated Logic introduced by Kifer, AL, and motivated by life-science applications. We show how a subset of the logic can be captured as the EL fragment of AL, EL-AL, and then go on to show how we can extend this representation to capture further temporal entailments. We show that both EL-AL and EL-Lambda maintain the same tractable complexity bounds for reasoning as EL and finally provide an example of how the logic can be utilised for the Drosophila developmental ontology.

ABSTRACT. Representing temporal data in conceptual data models and ontologies is required by various application domains, and for it to be useful for modelling precision and useful with automated reasoners, a language that is expressive enough to capture the required operational semantics of the time-varying information is essential. Temporal modelling languages have little support for temporal attributes, if at all, yet attributes are a standard element in the widely used conceptual modelling languages such as EER and UML. This hiatus prevents one to utilise a complete temporal conceptual data model and keep track of evolving values of data and its interaction with temporal classes. A rich axiomatization of fully temporized attributes is possible with a minor extension to the already very expressive description logic language DLRUS . We formalize the notion of transition of attributes, and their interaction with transition of classes. The transition specified for attributes are extension, evolution, and arbitrary quantitative extension.

ABSTRACT. The paper contributes to the recent enterprise of temporalizing and streamifiying ontology based data access (OBDA) by discussing rewritability and unfoldability aspects for DL-Lite instantiations of the new query-language framework STARQL. In particular, it demonstrates how STARQL queries can be rewritten and unfolded into queries expressed in one of the early relational stream query languages, the continuous query language CQL.

ABSTRACT. We study the fuzzy extension of FL_0 with semantics based on the Gödel t-norm. We show that gfp-subsumption w.r.t. a finite set of primitive definitions can be characterized by a relation on weighted automata, and use this result to provide tight complexity bounds for reasoning in this logic.

ABSTRACT. The complexity of reasoning in fuzzy description logics over finite lattices usually does not exceed that of the underlying classical DLs. This has recently been shown for the logics between L-IALC and L-ISCHI using a combination of automata- and tableau-based techniques. In this paper, this approach is modified to deal with nominals and constants in L-ISCHOI. Reasoning w.r.t. general TBoxes is ExpTime-complete, and PSpace-completeness is shown under the restriction to acyclic terminologies in two sublogics. The latter implies two previously unknown complexity results for the classical DLs ALCHO and SO.

ABSTRACT. To overcome the inability of Description Logics (DLs) to represent vague or imprecise information, several fuzzy extensions have been proposed in the literature. In this context, an important family of reasoning algorithms for fuzzy DLs is based on a combination of tableau algorithms and Operational Research (OR) problems, specifically using Mixed Integer Linear Programming (MILP).

In this paper, we present a MILP-based tableau procedure that allows to reason within fuzzy ALCB, i.e., ALCB with individual value restrictions. Interestingly, unlike classical tableau procedures, our tableau algorithm is deterministic, in the sense that it defers the inherent non-determinism in ALCB to a MILP solver.

ABSTRACT. In recent years many FDLs based on infinite t-norms have been proved to be undecidable. On the other hand, several FDLs based on finite t-norms, not only have been proved to be decidable, but they have been proved to belong to the same complexity classes as the corresponding crisp DLs. On the light of such results, a question that naturally arises is whether the finite-valued fuzzy framework is really more complex than the old crisp-valued formalism. The aim of this work is to analyze some of the complexity sources that are not present in the crisp framework. To this end, we will consider FDL languages with low expressivity that allow us to observe how the need for more complex deciding strategies, not required in the crisp framework, arises in many-valued FDLs.

ABSTRACT. In the last few years, the complexity of reasoning in fuzzy description logics has been studied in depth. Surprisingly, despite being arguably the simplest form of fuzzy semantics, not much is known about the complexity of reasoning in fuzzy description logics using the Gödel t-norm. It was recently shown that in the logic G-IALC under witnessed model semantics, all standard reasoning problems can be solved in exponential time, matching the complexity of reasoning in classical ALC. We show that this also holds under general model semantics.

ABSTRACT. Rough Description Logics have recently been studied as a means for representing and reasoning with imprecise knowledge. Real-world applications need to exploit reasoning over such knowledge in an efficient way. We describe how the combined approach to query answering can be extended to the rough setting. In particular, we extend both the canonical model and the rewriting procedure such that rough queries over rough EL ontologies can be answered by considering this information alone.

ABSTRACT. We present Bayesian Description Logics (BDLs): an extension of Description Logics with contextual probabilities encoded in a Bayesian network (BN). Classical DL reasoning tasks are extended to consider also the contextual and probabilistic information in BDLs. A complexity analysis of these problems shows that, for propositionally closed DLs, this extension comes without cost, while for tractable DLs the complexity is affected by the cost of reasoning in the BN.

ABSTRACT. Dealing with uncertainty is a very important issue in description logics (DLs). In this paper, we present PrDL-lite N bool a new probabilistic extension of DL-Lite N bool, known as a very expressive DL-Lite, by supporting the belief degree interval in a single axiom or a set of axioms connected with conjunction (by ∧) or disjunction (by ∨) operators. The PrDL-lite N bool semantics is based on DL-Lite N bool features which are a new alternative semantics for DL-lite N bool having a finite structure and its number is always finite unlike classical models. PrDL-lite N bool also supports terminological and assertional probabilistic knowledge and the reasoning tasks (satisfiability, deciding the entailment, computing tight interval for entailment) are achieved by solving linear optimization problems. A prototype of the approach is implemented using OWLAPI for knowledge base creation, Pellet for reasoning and LpSolve for solving the linear programs.

ABSTRACT. This paper investigates how to restrict the spread of sensitive information. This work is situated in a military context, and provides a tractable method to decide what semantic information to share, with whom, and how. The latter decision is supported by obfuscation, where a related concept or fact may be shared instead of the original. We consider uncertain information, and utilise Subjective Logic as an underlying formalism to further obfuscate concepts, and reason about obfuscated concepts.

ABSTRACT. Several attempts have been made to develop similarity measures for ontologies. Motivated by finding problems in existing measures, we design a new family of measures to address these problems. We carry out two sets of empirical studies. Firstly, to explore how good the new measures are by comparing them to human judgments of similarity. Secondly, we investigate how likely it is to encounter specific task-oriented problems when using a bad similarity measure.

ABSTRACT. In Description Logics (DL) knowledge bases (KBs) information is typically captured by crisp concepts. For many applications querying the KB by crisp query concepts is too restrictive. A controlled way of gradually relaxing a query concept can be achieved by the use of concept similarity. We formalize the task of instance query answering for crisp DL KBs using concepts relaxed by concept similarity measures (CSM). For the DL EL we investigate computation algorithms for this task, their complexity and properties for the employed CSM in case unfoldable TBoxes or general TBoxes are used.

ABSTRACT. We study the closely related problems of rewriting disjunctive datalog programs and non-Horn DL ontologies into plain datalog programs that entail the same facts for every dataset. We first propose the class of markable disjunctive datalog programs, which is efficiently recognisable and admits polynomial rewritings into datalog. Markability naturally extends to SHI ontologies, and markable ontologies admit (possibly exponential) datalog rewritings. We then turn our attention to resolution-based rewriting techniques. We devise an enhanced rewriting procedure for disjunctive datalog, and propose a second class of SHI ontologies that admits exponential datalog rewritings via resolution. Finally, we evaluate the feasibility of our techniques over a large corpus of ontologies, with encouraging results.

ABSTRACT. This paper further investigates the succinctness landscape of query rewriting in OWL 2 QL. We clarify the size of positive existential (PE), non-recursive datalog (NDL), and first order (FO) rewritings for various classes of tree-like conjunctive queries, ranging from linear queries up to bounded treewidth queries. More specifically, we establish a superpolynomial lower bound on the size of PE rewritings that holds already for linear queries and TBoxes of depth 2. For NDL-rewritings, we show that polynomial-size rewritings always exist for tree-shaped queries with a bounded number of leaves (and arbitrary TBoxes), and for bounded treewidth queries and bounded depth TBoxes. Finally, we show that the succinctness problems concerning FO-rewritings are equivalent to well-known problems in Boolean circuit complexity. Along with known results, this yields a complete picture of the succinctness landscape for the considered classes of queries and TBoxes.