We will explore the use of disjunctive causal rules for representing indeterminate causation. We provide first a logical formalization of such rules in the form of a disjunctive inference relation, and describe its logical semantics. Then we consider a nonmonotonic semantics for such rules, described in (Turner 1999). It will be shown, however, that, under this semantics, disjunctive causal rules admit a stronger logic in which these rules are reducible to ordinary, singular causal rules. This semantics also tends to give an exclusive interpretation of disjunctive causal effects, and so excludes some reasonable models in particular cases. To overcome these shortcomings, we will introduce an alternative nonmonotonic semantics for disjunctive causal rules, called a covering semantics, that permits an inclusive interpretation of indeterminate causal information. Still, it will be shown that even in this case there exists a systematic procedure, that we will call a normalization, that allows us to capture precisely the covering semantics using only singular causal rules. This normalization procedure can be viewed as a kind of nonmonotonic completion, and it generalizes established ways of representing indeterminate effects in current theories of action.

Previous work has proposed consistent query answering as a way to resolve inconsistencies in ontologies. In these approaches to consistent query answering, however, only inconsistencies due to errors in the underlying database are considered. In this paper, we additionally assume that ontological axioms may be erroneous, and that some database atoms and ontological axioms may not be removed to resolve inconsistencies. This problem is especially well suited in debugging mappings between distributed ontologies. We define two different semantics, one where ontological axioms as a whole are ignored to resolve an inconsistency, and one where only some of their instances are ignored. We then give a precise picture of the complexity of consistent query answering under these two semantics when ontological axioms are encoded as different classes of existential rules. In the course of this, we also close two open complexity problems in standard consistent query answering under existential rules.

Computing certain answers is the preferred way of answering queries in scenarios involving incomplete data. This, however, is computationally expensive, so practical systems use efficient techniques based on a particular three-valued logic, even though this often leads to incorrect results. Our goal is to provide a general many-valued framework for correctly approximating certain answers. We do so by defining the semantics of many-valued answers and queries, following the principle that additional knowledge about the input must translate into additional knowledge about the output. This framework lets us compare query outputs and evaluation procedures in terms of their informativeness. For each many-valued logic with a knowledge ordering on its truth values, one can build a syntactic evaluation procedure for all first-order queries, that correctly approximates certain answers; additional truth values are used to refine information about certain answers. For concrete examples, we show that a recently proposed approach fixing some of the inconsistencies of SQL query evaluation is an immediate consequence of our framework, and we further refine it by adding a fourth truth value. We show that no evaluation procedure based on Boolean logic delivers correctness guarantees. Finally, we study the relative power of evaluation procedures based on the informativeness of the answers they produce.

Open APIs are software intermediaries that make it possible for application programs to interact with data and processes, which can both be viewed as forms of services. In many scenarios, when one wants to obtain or publish a new service, one would like to check whether the new functionality can simply be obtained by suitably composing existing services. In this paper we study this problem by distinguishing between the two forms of services, that we call data-centric and process-centric, respectively. In the former, each API is an abstraction of a query specified on a data source, and composition amounts to building a new query by using the available APIs as views over the data. In the latter, each API abstracts a process made up by sequences of atomic actions, and composition means realizing a new process by suitably using the APIs exposed by the available services. We make the assumption that the semantics of services is specified by means of one of the most basic formalisms used in Computer Science, namely, regular languages. As a result, we get a rich analysis framework, where composition shows similarities to conformant and conditional planning. We describe composition principles and automated synthesis techniques for each of the two settings.

We introduce EHS*, a novel temporal-epistemic logic defined on temporal intervals characterised by regular expressions. We investigate the complexity of verifying multi-agent systems against EHS* specifications for a number of fragments of EHS* with results ranging from PSPACE-completeness to non-elementary time. The findings show that, at least for the fragments under analysis, the increase in expressiveness obtained by using regular expressions rather than end-points as standard, can be achieved without increasing the complexity of the problem. We show that the expressiveness of regular expressions can also be adopted at the level of specifications without severe computational cost. To do so we introduce a further temporal-epistemic logic, called EHSre, in which regular expressions are used within propositions, and give a polynomial time reduction of the model checking problem from EHSre to EHS*.

Some applications of Description Logic (DL) ontologies combine complete information (e.g., stemming from relational databases) with incomplete, open-world knowledge. Several research efforts in the last years have advocated closed predicates, which are predicates whose extension is interpreted as complete, as a suitable way to leverage partial completeness within the standard open-world semantics of DLs. These works have also studied the data complexity of query answering in the presence of closed predicates, which is generally intractable. In this paper we contribute to the understanding the combined complexity of the problem, by establishing tight complexity results for a range of DLs and query answering problems. In summary, our results show that consistency testing and instance query answering in the presence of closed predicates are feasible in NP even for rich dialects of the DL-Lite family; this is the lowest complexity that could be expected. For EL, in contrast, they are EXPTIME-complete, thus as hard as for ALC and some of its extensions. If unions of conjunctive queries (UCQs) are considered, the picture is even bleaker: we can show 2EXPTIME-hardness even for DL-Lite_R and EL. This is in sharp contrast to the NP-upper bound in the standard setting without closed predicates, and coincides with known upper bounds for much richer DLs. We note that our results imply 2EXPTIME-hardness of query answering in ALCO for the standard setting, where all predicates are interpreted under the open-world semantics. This singles out nominals as a previously unidentified source of complexity when answering queries over expressive DLs. Despite these negative results, we can still identify several useful classes of queries for which the increase in hardness is not as drastic, and the combined complexity of query answering remains between NP and coNEXPTIME.

We study anti-unification for the description logic EL and introduce thenotion of least general generalisation, which generalises simultaneously leastcommon subsumer and concept matching. The idea of generalisation of twoconcepts is to detect maximal similarities between them, and to abstract overtheir differences uniformly. We demonstrate that a finite minimal complete setof generalisations for ELconcepts always exists and establish complexitybounds for computing them. Wepresent an anti-unification algorithm that computes generalisations with afixed skeleton, study its properties and report on preliminary experimental evaluation.

We review several different languages for collective decision making problems, in which agents express their judgments, opinions, or beliefs over elements of a logically structured domain. Several such languages have been proposed in the literature to compactly represent the questions on which the agents are asked to give their views. In particular, the framework of judgment aggregation allows agents to vote directly on complex, logically related formulas, whereas the setting of binary aggregation asks agents to vote on propositional variables, over which dependencies are expressed by means of an integrity constraint. We compare these two languages and some of their variants according to their relative succinctness and according to the computational complexity of aggregating several individual views expressed in such languages into a collective judgment. Our main finding is that the formula-based language of judgment aggregation is more succinct than the constraint-based language of binary aggregation. In many (but not all) practically relevant situations, this increase in succinctness does not entail an increase in complexity of the corresponding problem of computing the outcome of an aggregation rule.

Many approaches for forgetting in Answer Set Programming (ASP) have been proposed in recent years, in the form of specific operators, or classes of operators, following different principles and obeying different properties. Whereas each approach was developed to somehow address some particular view on forgetting, thus aimed at obeying a specific set of properties deemed adequate for such view, we are lacking a comprehensive and uniform overview of existing operators and properties. We aim at overcoming this by thoroughly examining existing properties and (classes of) operators for forgetting in ASP, drawing a complete picture, which includes many novel (even surprising) results on relations between properties and operators. Our goal is to provide a guide to help users in choosing the most adequate operator for their application requirements.

We survey a selection of inconsistency measures from the literature and investigate their computational complexity wrt. decision problems related to bounds on the inconsistency value and the functional problem of determining the actual value. Our findings show that those inconsistency measures can be partitioned into three classes related to their complexity. The first class contains measures whose complexity are located on the first level of the polynomial hierarchy, the second class contains measures on the second level of the polynomial hierarchy, and the third class is located beyond the second level of the polynomial hierarchy. We provide membership results for all the investigated problems and completeness results for most of them.