1,721,607 research outputs found
A sound and complete tableau calculus for reasoning about only knowing and knowing at most
No full textDirettore Scuola di Specializzazione in Chirurgia Generale, Università Vita Salute, Ospedale San Raffaele, Milano
No full textOn the complexity of dealing with inconsistency in description logic ontologies
No full textWe study the problem of dealing with inconsistency in Description Logic (DL) ontologies. We consider inconsistency-tolerant semantics recently proposed in the literature, called AR-semantics and CAR-semantics, which are based on repairing (i.e., modifying) in a minimal way the extensional knowledge (ABox) while keeping the intensional knowledge (TBox) untouched. We study instance checking and conjunctive query entailment under the above inconsistency-tolerant semantics for a wide spectrum of DLs, ranging from tractable ones (EL) to very expressive ones (SHIQ), showing that reasoning under the above semantics is inherently intractable, even for very simple DLs. To the aim of overcoming such a high computational complexity of reasoning, we study sound approximations of the above semantics. Surprisingly, our computational analysis shows that reasoning under the approximated semantics is intractable even for tractable DLs. Finally, we identify suitable language restrictions of such DLs allowing for tractable reasoning under inconsistency-tolerant semantics
Minimal belief and negation as failure in multi-agent systems
No full textWe propose an epistemic, nonmonotonic approach to the formalization of knowledge in a multi-agent setting. From the technical viewpoint, a family of nonmonotonic logics, based on Lifschitz's modal logic of minimal belief and negation as failure, is proposed, which allows for formalizing an agent which is able to reason about both its own knowledge and other agents' knowledge and ignorance. We define a reasoning method for such a logic and characterize the computational complexity of the major reasoning tasks in this formalism. From the practical perspective, we argue that our logical framework is well-suited for representing situations in which an agent cooperates in a team, and each agent is able to communicate his knowledge to other agents in the team. In such a case, in many situations the agent needs nonmonotonic abilities, in order to reason about such a situation based on his own knowledge and the other agents' knowledge and ignorance. Finally, we show the effectiveness of our framework in the robotic soccer application domain
Reasoning about minimal knowledge in nonmonotonic modal logics
No full textWe study the problem of embedding Halpern and Moses's modal logic of minimal knowledge states into two families of modal formalism for nonmonotonic reasoning, McDermott and Doyle's nonmonotonic modal logics and ground nonmonotonic modal logics. First, we prove that Halpern and Moses's logic can be embedded into all ground logics; moreover, the translation employed allows for establishing a lower bound (Π3p) for the problem of skeptical reasoning in all ground logics. Then, we show a translation of Halpern and Moses's logic into a significant subset of McDermott and Doyle's formalisms. Such a translation both indicates the ability of Halpern and Moses's logic of expressing minimal knowledge states in a more compact way than McDermott and Doyle's logics, and allows for a comparison of the epistemological properties of such nonmonotonic modal formalisms. © 1999 Kluwer Academic Publishers
Embedding negation as failure into minimal knowledge
No full textRecent studies in nonmonotonic reasoning have shown that many of the best known nonmonotonic logics are based on the same two fundamental principles, i.e. minimal knowledge and negation as failure (or negation by default). In this paper we prove that it is possible to express negation as failure in terms of minimal knowledge. Specifically, we present a polynomial, non-faithful, modular embedding of Lifschitz's logic of minimal knowledge and negation as failure MKNF into Halpern and Moses' logic of minimal knowledge S5(G). From the theoretical viewpoint, this result implies that minimal knowledge has the same expressive power of negation as failure, hence it is possible to embed all the best known propositional nonmonotonic formalisms, in particular default logic, autoepistemic logic, and circumscription, into S5(G). From the perspective of knowledge-based systems, the proposed embedding allows in principle for realizing negation as failure in systems without a negation as failure construct, as e.g. positive disjunctive deductive databases
On the decidability and complexity of integrating ontologies and rules
No full textWe define the formal framework of r-hybrid knowledge bases (KBs) integrating ontologies and rules. A r-hybrid KB has a structural component (ontology) and a rule component. Such a framework is very general, in the sense that: (i) the construction is parametric with respect to the logic used to specify the structural component; (ii) the rule component is very expressive, since it consists of a Datalog\neg\vee program, i.e., a Datalog program with negation as failure and disjunction, (iii) the rule component is constrained in its interaction with the structural component according to a safeness condition: such a safe interaction between rules and structural KB captures (and is a generalization of) several previous proposals. As a consequence, we are able to show that such a framework of r-hybrid KBs comprises many systems proposed for combining rules and Description Logics. Then, we study reasoning in r-hybrid KBs. We provide a general algorithm for reasoning in r-hybrid KBs, and prove that, under very general conditions, decidability of reasoning is preserved when we add safe Datalog\neg\vee rules to a KB: in other words, if reasoning in the logic L used to specify the structural component T is decidable, then reasoning in the extension of T with safe Datalog\neg\vee rules is still decidable. We also show that an analogous property holds for the complexity of reasoning in r-hybrid KBs. Our decidability and complexity results generalize in a broad sense previous results obtained in recent research on this topic. In particular, we prove that reasoning in r-hybrid KBs whose structural component is specified in the Web Ontology Language OWL-DL is decidable
- …
