Such a goal can represent either the behaviour model checking systems (e.g., MOCHA (Alur et al. 1998) of the computer system one wants to synthesize and Prism (Kwiatkowska, Norman, and Parker 2011)). Reactive (an automated design problem (Pnueli and Rosner 1989)) Modules supports succinct and high-level modelling or a particular system property which one wants to check of concurrent and multi-agent systems. In the games we (an automated verification problem (Clarke, Grumberg, and study, the preferences of system components are specified Peled 2000)). In this framework, it is assumed that the system by associating with each player in the game a temporal logic plays against an adversarial environment, that is, that (LTL) formula that the player desires to be satisfied. Reactive the goal of the environment is to prevent the system from Modules Games with perfect information (where each player achieving its goal. In game-theoretic terms, this means that can see the entire system state) have been extensively studied the problem is modelled as a zero-sum game, and hence that (Gutierrez, Harrenstein, and Wooldridge 2015a), but in its solution is given by the computation of a winning strategy this paper we focus on imperfect information cases. We study for either the system or the environment.

Generalized plans, such as plans with loops, are widely used in AI. Among other things, they are straightforward to execute, they allow action repetition, and they solve multiple problem instances. However, the correctness of such plans is non-trivial to define, making it difficult to provide a clear specification of what we should be looking for. Proposals in the literature, such as strong planning, are universally adopted by the community, but were initially formulated for finite state systems. There is yet to emerge a study on the sensitivity of such correctness notions to the structural assumptions of the underlying plan framework. In this paper, we are interested in the applicability and correctness of generalized plans in domains that are possibly unbounded, and/or stochastic, and/or continuous. To that end, we introduce a generic controller framework to capture different types of planning domains. Using this framework, we then study a number of termination and goal satisfaction criteria from first principles, relate them to existing proposals, and show plans that meet these criteria in the different types of domains.

SPARQL, a query language for RDF graphs, is one of the key technologies for the Semantic Web. The expressivity and complexity of various fragments of SPARQL have been studied extensively. It is usually assumed that the optional matching operator OPTIONAL has only two graph patterns as arguments. The specification of SPARQL, however, defines it as a ternary operator, with an additional filter condition. We address the problem of expressibility of the full ternary OPTIONAL via the simplified binary version and show that it is possible, but only with an exponential blowup in the size of the query (under common complexity-theoretic assumptions). We also study expressibility of other non-monotone SPARQL operators via optional matching and each other.

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.

Large-scale probabilistic knowledge bases are becoming increasingly important in academia and industry alike. They are constantly extended with new data, powered by modern information extraction tools that associate probabilities with database tuples. In this paper, we revisit the semantics underlying such systems. In particular, the closed-world assumption of probabilistic databases, that facts not in the database have probability zero, clearly conflicts with their everyday use. To address this discrepancy, we propose an open-world probabilistic database semantics, which relaxes the probabilities of open facts to intervals. While still assuming a finite domain, this semantics can provide meaningful answers when some probabilities are not precisely known. For this open world setting, we propose an efficient evaluation algorithm for unions of conjunctive queries. Our open-world algorithm incurs no overhead compared to closed-world reasoning and runs in time linear in the size of the database for tractable queries. All other queries are #P-hard, implying a data complexity dichotomy between linear time and #P. For queries involving negation, however, open-world reasoning can become NP-, or even NP^PP-hard. Finally, we discuss additional knowledge representation layers that can further strengthen open-world reasoning about big uncertain data.

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.

A referring expression in linguistics is any noun phrase identifying an object in a way that will be useful to interlocutors. In the context of a query over a first order knowledge base K, constant symbols occurring in K are the artifacts usually used as referring expressions in certain answers to the query. In this paper, we begin to explore how this can be usefully extended by allowing a class of more general formulas, called Singular Referring Expressions, to replace constants in this role. In particular, we lay a foundation for admitting Singular Referring Expressions in certain answer computation for queries over K. An integral part of this foundation are characterization theorems for identification properties of Singular Referring Expressions for queries annotated with a domain specific language for referring concept types. Finally, we apply this framework in the context of tractable description logic dialects, showing how identification properties can be determined at compile-time for conjunctive queries, and how off-the-shelf conjunctive query evaluation for these dialects can be used in query evaluations, preserving, in all cases, underlying tractability.

Bisimulation provides structural conditions to characterize indistinguishability between nodes on graph-like structures from an external observer. It is a fundamental notion used in many areas. However, many applications use graphs where nodes have data, and where observers can test for equality or inequality of data values (e.g., asking the attribute "name" of a node to be different from that of all its neighbors). The present work constitutes a first investigation of "data aware"' bisimulations on data graphs. We study the problem of computing such bisimulations, based on the observational indistinguishability for XPath — a language that extends modal logic with tests for data equality. We show that in general the problem is pspace-complete, but identify several restrictions that yield better complexity bounds (coNP, ptime) by controlling suitable parameters of the problem; namely, the amount of em non-locality allowed, and the class of models considered (graph, DAG, tree). In particular, this analysis yields a hierarchy of tractable fragments.

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*.

A principled way to study limited forms of reasoning for expressive knowledge bases is to specify the reasoning problem within a suitable logic of limited belief. Ideally such a logic comes equipped with a perspicuous semantics, which provides insights into the nature of the belief model and facilitates the study of the reasoning problem. While a number of such logics were proposed in the past, none of them is able to deal with function symbols except perhaps for the special case of logical constants. In this paper we propose a logic of limited belief with arbitrary function symbols. Among other things, we demonstrate that this form of limited belief has desirable properties such as eventual completeness for a large class of formulas and that it serves as a specification of a form of decidable reasoning for very expressive knowledge bases.