The paper introduces a worst-case optimal tableau algorithm for reasoning with Forest Logic Programs, a decidable fragment of Open Answer Set Programming. FoLPs are a useful device for tight integration of the Description Logic and the Logic Programming worlds: reasoning with the DL SHOQ can be simulated within the fragment. The algorithm reuses a knowledge compilation technique previously introduced, but improves on previous results by decreasing the worst-case running time with one exponential level. The decrease in complexity is due to the usage in conjunction of a new redundancy and of a new caching rule.

In ontology-based data access (OBDA), ontologies are used as an interface for querying instance data. Since in typical applications the size of the data is much larger than the size of the ontology and query, data complexity is the most important complexity measure. In this paper, we propose a new method for investigating data complexity in OBDA: instead of classifying whole logics according to their complexity, we aim at classifying each individual ontology within a given master language. Our results include a P/coNP-dichotomy theorem for ontologies of depth one in the description logic ALCFI, the equivalence of a P/coNP-dichotomy theorem for ALC/ALCI-ontologies of unrestricted depth to the famous dichotomy conjecture for CSPs by Feder and Vardi, and a non-P/coNP-dichotomy theorem for ALCF-ontologies.

While query answering in the presence of description logic (DL) ontologies is a well-studied problem, questions of static analysis such as query containment and query optimization have received less attention. In this paper, we study a rather general version of query containment that, unlike the classical version, cannot be reduced to query answering. First, we allow a restriction to be placed on the vocabulary used in the instance data, which can result in shorter equivalent queries; and second, we allow each query its own ontology rather than assuming a single ontology for both queries, which is crucial in applications to versioning and modularity. We also study global minimization of queries in the presence of DL ontologies, which is more subtle than for classical databases as minimal queries need not be isomorphic.

The EL family of description logics (DLs) has been designed to provide a restricted syntax for commonly used DL constructors with the goal to guarantee polynomial complexity of reasoning. Yet, polynomial complexity does not always mean that the underlying reasoning procedure is efficient inpractice. In this paper we consider a simple DL ELO from the EL family that admits nominals, and argue that existing polynomial reasoning procedures for ELO can be impractical for many realistic ontologies. To solve the problem, we describe an optimization strategy in which the inference rules required for reasoning with nominals are avoided as much as possible. The optimized procedure is evaluated within the reasoner ELK and demonstrated to perform well in practice.

Answer Set Programming (ASP) is a fully-declarative logic programming paradigm, which has been proposed in the area of knowledge representation and non-monotonic reasoning. Nowadays, the formal properties of ASP are well-understood, efficient ASP systems are available, and, recently, ASP has been employed in a few industrial applications. However, ASP technology is not mature for a successful exploitation in industry yet; mainly because ASP technologies are not integrated in the well-assessed development processes and platforms which are tailored for imperative/object-oriented programming languages. In this paper we present a new programming framework blending ASP with Java. The framework is based on JASP, an hybrid language that transparently supports a bilateral interaction between ASP and Java. JASP specifications are compliant with the JPA standard to perfectly fit extensively-adopted enterprise application technologies. The framework also encompasses an implementation of JASP as a plug-in for the Eclipse platform, called JDLV, which includes a compiler from JASP to Java. Moreover, we show a real-world application developed with JASP and JDLV, which highlights the effectiveness of our ASP–Java integration framework.

In software testing, the small-scope hypothesis states that a high proportion of errors can be found by testing a program for all test inputs within some small scope. In this paper, we evaluate the small-scope hypothesis for answer-set programming (ASP). To this end, we follow work in traditional testing and base our evaluation on mutation analysis. In fact, we show that a rather limited scope is sufficient for testing ASP encodings from a representative set of benchmark problems. Our experimental evaluation facilitates effective methods for testing in ASP. Also, it gives some justification to analyse programs at the propositional level after grounding them over a small domain.

This paper presents a characterisation of and definitions for the phenomenon of masking in the context of justifications for entailments in ontologies. In essence masking is present within a justification, over a set of justifications, or over a complete ontology when the number of justifications for an entailment does not reflect the number of reasons for that entailment. Four types of masking are defined in this paper: Internal Masking, Cross Masking, External Masking and Shared Core Masking. The results of an empirical study are presented which shows that the phenomenon of masking is prevalent throughout ontologies with non-trivial entailments in the NCBO BioPortal corpus. Out of 72 ontologies, 53 exhibited some form of masking, with 9 ontologies exhibiting internal masking, 23 ontologies exhibiting external masking, and 53 ontologies exhibiting shared core masking.

A bipolar framework is introduced for combining agents' beliefs so as to enable them to reach a common shared position or viewpoint. Our approach exploits the truth-gaps inherent to propositions involving vague concepts, by allowing agents to soften directly conflicting opinions. To this end we adopt a bipolar truth-model for propositional logic characterised by lower and upper valuations on the sentences of the language. According to this model sentences may be absolutely true, absolutely false or borderline (i.e. neither absolutely true nor absolutely false). The added flexibility of a possible truth-gap between absolutely true and absolutely false allows agents with inconsistent viewpoints, in which a proposition p is absolutely true according to one view and absolutely false according to the other, to reach a compromise position in which p is borderline. Within this framework four combination operators are proposed for combining different viewpoints as represented by different valuation pairs. Intuitively, these correspond to compromise positions with different levels of semantic precision (or vagueness). Kleene belief pairs are then introduced as lower and upper measures quantifying epistemic uncertainty about the sentences of the language when valuation pairs provide the underlying truth model. The combination operators on valuation pairs are then extended to belief pairs using a general schema incorporating a probabilistic model of the interaction between agents. The properties of the four operators are then investigated within this extended framework.

We study (i) uniform interpolation for TBoxes that are formulated in the description logic EL and (ii) approximations of TBoxes formulated in more expressive languages. In both cases, we give model-theoretic characterizations based on simulations and cartesian products, and we develop algorithms that decide whether interpolants and approximations exist. We present a uniform approach to both problems, based on a novel amorphous automaton model called EL automata (EA). Using EAs, we also establish a simpler proof of the known result that conservative extensions of EL-TBoxes can be decided in ExpTime.

Belief revision has been extensively studied in the framework of propositional logic, but just recently revision within fragments of propositional logic has gained attention. Hereby it is not only the belief set and the revision formula which are given within a certain language fragment, but also the result of the revision has to be located in the same fragment. So far, research in this direction has been mainly devoted to the Horn fragment of classical logic. In this work, we present a general approach to define new revision operators derived from known operators (as for instance, Satoh's and Dalal's revision operators), such that the result of the revision remains in the fragment under consideration. Our approach is not limited to the Horn case but applicable to any fragment of propositional logic where the models of the formulas are closed under a Boolean function. Thus we are able to uniformly treat cases as dual-Horn, Krom and affine formulas, as well.