The ability to predict, or at least recognize, the state of the world that an action brings about, is a central feature of autonomous agents. We propose, herein, a formal framework within which we investigate whether this ability can be autonomously learned. The framework makes explicit certain premises that we contend are central in such a learning task: (i) slow sensors may prevent the sensing of an action's direct effects during learning; (ii) predictions need to be made reliably in future and novel situations. We initiate in this work a thorough investigation of the conditions under which learning is or is not feasible. Despite the very strong negative learnability results that we obtain, we also identify interesting special cases where learning is feasible and useful.

Let us explain our motivations for studying the logic of fuzzy belief and common belief. It is not so unusual that one We formalize reasoning about fuzzy belief and believes something to some degree, or the degree of one's fuzzy common belief, especially incomparable beliefs, belief may be neither 0 nor 1. The notion of fuzzy belief is in multi-agent systems by using a logical system appropriate in such a case. Moreover, the notion of fuzzy based on Fitting's many-valued modal logic, common belief can be appropriate even in a case where any where incomparable beliefs mean beliefs whose degrees agent of a group does not have a fuzzy belief. To see this, are not totally ordered. Completeness and consider the following question. Is there anything that all the decidability results for the logic of fuzzy belief people in the world believe? Strictly speaking, there may be and common belief are established while implicitly no such thing as a common belief among all the people in the exploiting the duality-theoretic perspective on Fitting's world. Even if so, there may be something that most of the logic that builds upon the author's previous people in the world believe.

Despite the importance of propositional logic in artificial intelligence, the notion of language independence in the propositional setting (not to be confound with syntax independence) has not received much attention so far. In this paper, we define language independence for a propositional operator as robustness w.r.t.symbol translation. We provide a number of characterizations results for such translations. We motivate the need to focus on symbol translations of restricted types, and identify several families of interest. We identify the computational complexity of recognizing symbol translations from those families. Finally, as a case study, we investigate the robustness of belief revision/merging operators w.r.t. translations of different types. It turns out that rational belief revision/merging operators are not guaranteed to offer the most basic (yet non-trivial) form of language independence; operators based on the Hamming distance do not suffer from this drawback but are less robust than operators based on the drastic distance.

We study the existential closures of several propositional languages L considered recently as target languages for knowledge compilation (KC), namely the incomplete fragments KROM-C, HORN-C, K/H-C, renH-C, AFF, and the corresponding disjunction closures KROM-C[V], HORN-C[V], K/H-C[V], renH-C[V], and AFF[V]. We analyze the queries, transformations, expressiveness and succinctness of the resulting languages L[E] in order to locate them in the KC map. As a by-product, we also address several issues concerning disjunction closures that were left open so far. From our investigation, the language HORN-C[V, E] (where disjunctions and existential quantifications can be applied to Horn CNF formulae) appears as an interesting target language for the KC purpose, challenging the influential DNNF languages.

We study uniform interpolation and forgetting in the description logic ALC. Our main results are model-theoretic characterizations of uniform interpolants and their existence in terms of bisimulations, tight complexity bounds for deciding the existence of uniform interpolants, an approach to computing interpolants when they exist, and tight bounds on their size. We use a mix of model-theoretic and automata-theoretic methods that, as a by-product, also provides charachterizations of, and decision procedures for, conservative extensions.

In a seminal paper, Lin and Reiter introduced the notion of progression for basic action theories in the situation calculus. Earlier works by Moore, Scherl and Levesque extended the situation calculus to account for knowledge. In this paper, we study progression of knowledge in the situation calculus. We first adapt the concept of bisimulation from modal logic and extend Lin and Reiter's notion of progression to accommodate knowledge. We show that for physical actions, progression of knowledge reduces to forgetting predicates in first-order modal logic. We identify a class of first-order modal formulas for which forgetting an atom is definable in first-order modal logic. This class of formulas goes beyond formulas without quantifying-in. We also identify a simple case where forgetting a predicate reduces to forgetting a finite number of atoms. Thus we are able to show that for local-effect physical actions, when the initial KB is a formula in this class, progression of knowledge is definable in first-order modal logic. Finally, we extend our results to the multi-agent case.

Since the seminal work of Sampath et al. in 1996, despite the subsequent flourishing of techniques on diagnosis of discrete-event systems (DESs), the basic notions of fault and diagnosis have been remaining conceptually unchanged. Faults are defined at component level and diagnoses incorporate the occurrences of component faults within system evolutions: diagnosis is context-free. As this approach may be unsatisfactory for a complex DES, whose topology is organized in a hierarchy of abstractions, we propose to define different diagnosis rules for different subsystems in the hierarchy. Relevant fault patterns are specified as regular expressions on patterns of lower-level subsystems. Separation of concerns is achieved and the expressive power of diagnosis is enhanced: each subsystem has its proper set of diagnosis rules, which may or may not depend on the rules of other subsystems. Diagnosis is no longer anchored to components: it becomes context-sensitive. The approach yields seemingly contradictory but nonetheless possible scenarios: a subsystem can be normal despite the faulty behavior of a number of its components (positive paradox); also, it can be faulty despite the normal behavior of all its components (negative paradox).

Existential rules, i.e. Datalog extended with existential quantifiers in rule heads, are currently studied under a variety of names such as Datalog +/-, ∀∃-rules, and tuple-generating dependencies. The renewed interest in this formalism is fuelled by a wealth of recently discovered language fragments for which query answering is decidable. This paper extends and consolidates two of the main approaches in this field — acyclicity and guardedness — by providing (1) complexity-preserving generalisations of weakly acyclic and weakly (frontier-)guarded rules, and (2) a novel formalism of glut-(frontier-)guarded rules that subsumes both. This builds on an insight that acyclicity can be used to extend any existential rule language while retaining decidability. Besides decidability, combined query complexities are established in all cases.

We investigate (quantifier-free) spatial constraint languages with equality, contact and connectedness predicates as well as Boolean operations on regions, interpreted over low-dimensional Euclidean spaces. We show that the complexity of reasoning varies dramatically depending on the dimension of the space and on the type of regions considered. For example, the logic with the interior-connectedness predicate (and without contact) is undecidable over polygons or regular closed sets in the Euclidean plane, NP-complete over regular closed sets in three-dimensional Euclidean space, and ExpTime-complete over polyhedra in three-dimensional Euclidean space.

Existing belief merging operators take advantage of all the models from the bases, including those contradicting the integrity constraints. In this paper, we show that this is not suited to every merging scenario. We study the case when the bases are "rationalized" with respect to the integrity constraints during the merging process. We define in formal terms several independence conditions for merging operators and show how they interact with the standard IC postulates for belief merging. Especially, we give an independence-based axiomatic characterization of a distance-based operator.