The Experts below are selected from a list of 318 Experts worldwide ranked by ideXlab platform
Marc Denecker - One of the best experts on this subject based on the ideXlab platform.
-
Safe inductions and their applications in knowledge representation
Artificial Intelligence, 2018Co-Authors: Bart Bogaerts, Joost Vennekens, Marc DeneckerAbstract:Abstract In many knowledge representation formalisms, a constructive semantics is defined based on sequential applications of rules or of a semantic operator. These constructions often share the property that rule applications must be delayed until it is safe to do so: until it is known that the condition that triggers the rule will continue to hold. This intuition occurs for instance in the well-founded semantics of Logic programs and in Autoepistemic Logic. In this paper, we formally define the safety criterion algebraically. We study properties of so-called safe inductions and apply our theory to Logic programming and Autoepistemic Logic. For the latter, we show that safe inductions manage to capture the intended meaning of a class of theories on which all classical constructive semantics fail.
-
IJCAI - Safe inductions: An algebraic study
Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, 2017Co-Authors: Bart Bogaerts, Joost Vennekens, Marc DeneckerAbstract:In many knowledge representation formalisms, a constructive semantics is defined based on sequential applications of rules or of a semantic operator. These constructions often share the property that rule applications must be delayed until it is safe to do so: until it is known that the condition that triggers the rule will remain to hold. This intuition occurs for instance in the well-founded semantics of Logic programs and in Autoepistemic Logic. In this paper, we formally define the safety criterion algebraically. We study properties of so-called safe inductions and apply our theory to Logic programming and Autoepistemic Logic. For the latter, we show that safe inductions manage to capture the intended meaning of a class of theories on which all classical constructive semantics fail.
-
distributed Autoepistemic Logic and its application to access control
International Joint Conference on Artificial Intelligence, 2016Co-Authors: Pieter Van Hertum, Marcos Cramer, Bart Bogaerts, Marc DeneckerAbstract:In this paper we define and study an extension of Autoepistemic Logic (AEL) called distributed Autoepistemic Logic (dAEL) with multiple agents that have full introspection in their own knowledge as well as in that of others. This mutual full introspection between agents is motivated by an application of dAEL in access control. We define 2- and 3-valued semantic operators for dAEL. Using these operators, approximation fixpoint theory, an abstract algebraic framework that unifies different knowledge representation formalisms, immediately yields us a family of semantics for dAEL, each based on different intuitions that are well-studied in the context of AEL. The application in access control also motivates an extension of dAEL with inductive definitions (dAEL(ID)). We explain a use-case from access control to demonstrate how dAEL(ID) can be fruitfully applied to this domain and discuss how well-suited the different semantics are for the application in access control.
-
KR - Ordered epistemic Logic: semantics, complexity and applications
2012Co-Authors: Hanne Vlaeminck, Joost Vennekens, Maurice Bruynooghe, Marc DeneckerAbstract:Many examples of epistemic reasoning in the literature exhibit a stratified structure: defaults are formulated on top of an incomplete knowledge base. These defaults derive extra information in case information is missing in the knowledge base. In Autoepistemic Logic, default Logic and ASP this inherent stratification is not preserved as they may refer to their own knowledge or Logical consequences. Defining the semantics of such Logics requires a complex mathematical construction. As an alternative, this paper further develops ordered epistemic Logic. This Logic extends first order Logic with a modal operator and stratification is maintained. This allows us to define an easy to understand semantics. Moreover, inference tasks have a lower complexity than in Autoepistemic Logic and the Logic integrates seamlessly into classical Logic and its extensions. In this paper we also propose a generalization of ordered epistemic Logic, which we call distributed ordered epistemic Logic. We argue that it can provide a semantic foundation for a number of distributed knowledge representation formalisms found in the literature.
-
Predicate Introduction for Logics with Fixpoint Semantics. Part II: Autoepistemic Logic
Fundamenta Informaticae, 2008Co-Authors: Joost Vennekens, Johan Wittocx, Maarten Mariën, Marc DeneckerAbstract:We study the transformation of "predicate introduction" in non-monotonic Logics. By this, we mean the act of replacing a complex formula by a newly defined predicate. From a knowledge representation perspective, such transformations can be used to eliminate redundancy or to simplify a theory. From a more practical point of view, they can also be used to transform a theory into a normal form imposed by certain inference programs or theorems. In a companion paper, we developed an algebraic theory that considers predicate introduction within the framework of "approximation theory", a fixpoint theory for non-monotone operators that generalizes all main semantics of various non-monotonic Logics, including Logic programming, default Logic and Autoepistemic Logic. We then used these results to show that certain Logic programming transformations are equivalence preserving under, among others, both the stable and well-founded semantics. In this paper, we now apply the same algebraic results to Autoepistemic Logic and prove that a transformation to reduce the nesting depth of modal operators is equivalence preserving under a family of semantics for this Logic. This not only provides useful theorems for Autoepistemic Logic, but also demonstrates that our algebraic theory does indeed capture the essence of predicate introduction in a generally applicable way.
Yuejun Jiang - One of the best experts on this subject based on the ideXlab platform.
-
on the relationship between assumption based framework and Autoepistemic Logic
International Syposium on Methodologies for Intelligent Systems, 1994Co-Authors: Yuejun Jiang, Yongyuth AramkulchaiAbstract:Assumption-based (AB) framework [BTK93] is a generalisation of abduction. It augments a theory with a set of admissible assumptions that it can defend against any attacks. Autoepistemic Logic is a nonmonotonic Logic about an ideal agent who reasons about her beliefs and ignorance introspectively. On the surface, these two formalisms look very different. A closer examination reveals many similarities. Indeed, BTK93 has shown that stable extensions in the AB framework of an Autoepistemic theory correspond to the Moore's AE extensions of the theory. In this paper, we shall continue to establish some more relationships between the two formalisms. We first reformulate BTK's AB framework for AE Logic with a modal approach. We then provide an AB framework for a revised preferred extension that neither subsumes nor being subsumed by Przymusinski's 3-valued AE Logic. We then show that the AB framework for a revised complete extension of any consistent AE theory strictly subsumes Przymusinski's 3-valued AE Logic. By exploiting the clear structure of the modally reformulated AB framework, we further define an AB framework for a reflexive preferred (cf. stable, complete) extension that integrates Schwarz 's reflexive AE Logic with Przymusinski's 3-valued AE Logic.
-
on multiagent Autoepistemic Logic an extrospective view
Principles of Knowledge Representation and Reasoning, 1994Co-Authors: Yuejun JiangAbstract:Abstract Moore's Autoepistemic Logic was only introduced for a single agent. Reiter considered the task much harder to extend the Logic to multiagents. Morgenstern argued that multiagent Autoepistemic reasoning is not at all symmetric with the single agent Autoepistemic reasoning. In this paper however, we shall argue for an extrospective view of multiagent Autoepistemic reasoning that is symmetric between the single agent setting and the multiagent setting. In particular, we will present a multiagent generalization of McDermott and Doyle's general Autoepistemic Logical framework. Unlike Morgenstern's introspective view which extends Moore's belief operator L to a multiagent setting by indexing the operator with an agent, eg. LJohnP, the proposed extrospective view combines Moore's L operator with a multiagent monotonic epistemic Logic, eg. L Bel(John,p). We shall present two approaches based on the extrospective view of multiagent Autoepistemic reasoning. The first approach simply replaces the “base” Logic of Moore's Autoepistemic Logic by an epistemic Logic. The second approach allows Autoepistemic reasoning within the scope of any nested monotonic epistemic modal operators. On the surface, the two approaches seem to be very different. A closer examination reveals surprizingly that they are essentially equivalent. This suggests that single-agent Autoepistemic reasoning and its proof mechanization are in fact readily extendible to multiagents. In particular, we shall show that the extrospective approaches subsume Morgenstern's formulation including its various principles of arrogance. Keywords: Knowledge Representation, Autoepistemic Logic, Epistemic Logic and Multiagent Nonmonotonic Reasoning
-
ISMIS - On the Relationship between Assumption-based Framework and Autoepistemic Logic
Lecture Notes in Computer Science, 1994Co-Authors: Yuejun Jiang, Yongyuth AramkulchaiAbstract:Assumption-based (AB) framework [BTK93] is a generalisation of abduction. It augments a theory with a set of admissible assumptions that it can defend against any attacks. Autoepistemic Logic is a nonmonotonic Logic about an ideal agent who reasons about her beliefs and ignorance introspectively. On the surface, these two formalisms look very different. A closer examination reveals many similarities. Indeed, BTK93 has shown that stable extensions in the AB framework of an Autoepistemic theory correspond to the Moore's AE extensions of the theory. In this paper, we shall continue to establish some more relationships between the two formalisms. We first reformulate BTK's AB framework for AE Logic with a modal approach. We then provide an AB framework for a revised preferred extension that neither subsumes nor being subsumed by Przymusinski's 3-valued AE Logic. We then show that the AB framework for a revised complete extension of any consistent AE theory strictly subsumes Przymusinski's 3-valued AE Logic. By exploiting the clear structure of the modally reformulated AB framework, we further define an AB framework for a reflexive preferred (cf. stable, complete) extension that integrates Schwarz 's reflexive AE Logic with Przymusinski's 3-valued AE Logic.
-
another view of Autoepistemic Logic and truth maintenance system
International Syposium on Methodologies for Intelligent Systems, 1991Co-Authors: Yuejun JiangAbstract:In this paper, we present a novel Autoepistemic Logic (NAE) that subsumes both Moore's original Autoepsteimc Logic (AE) and Konolige's stronger extensions. The semantics of the Logic is characterized by a combination of AE extensions and minimum stable theories. Although the Logic is still based on fixpoints, it always has a NAE extension for any AE theory. Unlike Konolige's strongly-grounded AE extension, strongly-grounded NAE extension is syntax-independent and always exists. In particular, it is shown that strongly-grounded NAE can provide a complete semantics to Truth Maintenance System (TMS) because NAE can additionally account for backtracking routines in TMS. In contrast, strongly-grounded AE can only capture the semantical aspect of TMS that is free of backtracking.
-
ISMIS - Another View of Autoepistemic Logic and Truth Maintenance System
Lecture Notes in Computer Science, 1991Co-Authors: Yuejun JiangAbstract:In this paper, we present a novel Autoepistemic Logic (NAE) that subsumes both Moore's original Autoepsteimc Logic (AE) and Konolige's stronger extensions. The semantics of the Logic is characterized by a combination of AE extensions and minimum stable theories. Although the Logic is still based on fixpoints, it always has a NAE extension for any AE theory. Unlike Konolige's strongly-grounded AE extension, strongly-grounded NAE extension is syntax-independent and always exists. In particular, it is shown that strongly-grounded NAE can provide a complete semantics to Truth Maintenance System (TMS) because NAE can additionally account for backtracking routines in TMS. In contrast, strongly-grounded AE can only capture the semantical aspect of TMS that is free of backtracking.
Miroslaw Truszczynski - One of the best experts on this subject based on the ideXlab platform.
-
Uniform semantic treatment of default and Autoepistemic Logics
arXiv: Artificial Intelligence, 2000Co-Authors: Marc Denecker, Victor W. Marek, Miroslaw TruszczynskiAbstract:We revisit the issue of connections between two leading formalisms in nonmonotonic reasoning: Autoepistemic Logic and default Logic. For each Logic we develop a comprehensive semantic framework based on the notion of a belief pair. The set of all belief pairs together with the so called knowledge ordering forms a complete lattice. For each Logic, we introduce several semantics by means of fixpoints of operators on the lattice of belief pairs. Our results elucidate an underlying isomorphism of the respective semantic constructions. In particular, we show that the interpretation of defaults as modal formulas proposed by Konolige allows us to represent all semantics for default Logic in terms of the corresponding semantics for Autoepistemic Logic. Thus, our results conclusively establish that default Logic can indeed be viewed as a fragment of Autoepistemic Logic. However, as we also demonstrate, the semantics of Moore and Reiter are given by different operators and occupy different locations in their corresponding families of semantics. This result explains the source of the longstanding difficulty to formally relate these two semantics. In the paper, we also discuss approximating skeptical reasoning with Autoepistemic and default Logics and establish constructive principles behind such approximations.
-
Fixpoint 3-valued semantics for Autoepistemic Logic
arXiv: Logic in Computer Science, 1999Co-Authors: Marc Denecker, Victor W. Marek, Miroslaw TruszczynskiAbstract:The paper presents a constructive fixpoint semantics for Autoepistemic Logic (AEL). This fixpoint characterizes a unique but possibly three-valued belief set of an Autoepistemic theory. It may be three-valued in the sense that for a subclass of formulas F, the fixpoint may not specify whether F is believed or not. The paper presents a constructive 3-valued semantics for Autoepistemic Logic (AEL). We introduce a derivation operator and define the semantics as its least fixpoint. The semantics is 3-valued in the sense that, for some formulas, the least fixpoint does not specify whether they are believed or not. We show that complete fixpoints of the derivation operator correspond to Moore's stable expansions. In the case of modal representations of Logic programs our least fixpoint semantics expresses well-founded semantics or 3-valued Fitting-Kunen semantics (depending on the embedding used). We show that, computationally, our semantics is simpler than the semantics proposed by Moore (assuming that the polynomial hierarchy does not collapse).
-
fixpoint 3 valued semantics for Autoepistemic Logic
National Conference on Artificial Intelligence, 1998Co-Authors: Marc Denecker, Victor W. Marek, Miroslaw TruszczynskiAbstract:The paper presents a constructive 3-valued semantics for Autoepistemic Logic (AEL). We introduce a derivation operator and define the semantics as its least fixpoint. The semantics is 3-valued in the sense that, for some formulas, the least fixpoint does not specify whether they are believed or not. We show that complete fixpoints of the derivation operator correspond to Moore's stable expansions. In the case of modal representations of Logic programs our least fixpoint semantics expresses well-founded semantics or 3-valued Fitting-Kunen semantics (depending on the embedding used). We show that, computationally, our semantics is simpler than the semantics proposed by Moore (assuming that the polynomial hierarchy does not collapse).
-
AAAI/IAAI - Fixpoint 3-valued semantics for Autoepistemic Logic
1998Co-Authors: Marc Denecker, Victor W. Marek, Miroslaw TruszczynskiAbstract:The paper presents a constructive 3-valued semantics for Autoepistemic Logic (AEL). We introduce a derivation operator and define the semantics as its least fixpoint. The semantics is 3-valued in the sense that, for some formulas, the least fixpoint does not specify whether they are believed or not. We show that complete fixpoints of the derivation operator correspond to Moore's stable expansions. In the case of modal representations of Logic programs our least fixpoint semantics expresses well-founded semantics or 3-valued Fitting-Kunen semantics (depending on the embedding used). We show that, computationally, our semantics is simpler than the semantics proposed by Moore (assuming that the polynomial hierarchy does not collapse).
-
reflexive Autoepistemic Logic and Logic programming
Logic Programming and Non-Monotonic Reasoning, 1993Co-Authors: Wiktor V Marek, Miroslaw TruszczynskiAbstract:In this paper we show that reflexive Autoepistemic Logic of Schwarz is a particularly convenient modal formalism for studying properties of answer sets for Logic programs with classical negation and disjunctive Logic programs. Syntactical properties of Logic programs imply that a natural interpretation of default Logic in the Logic of minimal knowledge (nonmonotonic S4F) provides also a modal representation of Logic programs. Moreover, in the case of Logic programs one can use reflexive Autoepistemic Logic which is stronger and possesses simpler semantical characterizations than the Logic of minimal knowledge. Reflexive Autoepistemic Logic and Autoepistemic Logic are bi-interpretable. Consequently, our results provide embeddings of Logic programs with classical negation and disjunctive programs in Autoepistemic Logic.
Heribert Vollmer - One of the best experts on this subject based on the ideXlab platform.
-
The Complexity of Reasoning for Fragments of Autoepistemic Logic
ACM Transactions on Computational Logic, 2012Co-Authors: Nadia Creignou, Arne Meier, Heribert Vollmer, Michael ThomasAbstract:Autoepistemic Logic extends propositional Logic by the modal operator L . A formula φ that is preceded by an L is said to be “believed.” The Logic was introduced by Moore in 1985 for modeling an ideally rational agent’s behavior and reasoning about his own beliefs. In this article we analyze all Boolean fragments of Autoepistemic Logic with respect to the computational complexity of the three most common decision problems expansion existence, brave reasoning and cautious reasoning. As a second contribution we classify the computational complexity of checking that a given set of formulae characterizes a stable expansion and that of counting the number of stable expansions of a given knowledge base. We improve the best known Δ 2 p -upper bound on the former problem to completeness for the second level of the Boolean hierarchy. To the best of our knowledge, this is the first paper analyzing counting problem for Autoepistemic Logic.
-
LATA - On the parameterized complexity of default Logic and Autoepistemic Logic
Language and Automata Theory and Applications, 2012Co-Authors: Arne Meier, Michael Thomas, Johannes Schmidt, Heribert VollmerAbstract:We investigate the application of Courcelle's Theorem and the logspace version of Elberfeld et al. in the context of the implication problem for propositional sets of formulae, the extension existence problem for default Logic, as well as the expansion existence problem for Autoepistemic Logic and obtain fixed-parameter time and space efficient algorithms for these problems. On the other hand, we exhibit, for each of the above problems, families of instances of a very simple structure that, for a wide range of different parameterizations, do not have efficient fixed-parameter algorithms (even in the sense of the large class XPnu), unless P=NP.
-
On the Parameterized Complexity of Default Logic and Autoepistemic Logic
arXiv: Computational Complexity, 2011Co-Authors: Arne Meier, Michael Thomas, Johannes Schmidt, Heribert VollmerAbstract:We investigate the application of Courcelle's Theorem and the logspace version of Elberfeld etal. in the context of the implication problem for propositional sets of formulae, the extension existence problem for default Logic, as well as the expansion existence problem for Autoepistemic Logic and obtain fixed-parameter time and space efficient algorithms for these problems. On the other hand, we exhibit, for each of the above problems, families of instances of a very simple structure that, for a wide range of different parameterizations, do not have efficient fixed-parameter algorithms (even in the sense of the large class XPnu), unless P=NP.
-
The Complexity of Reasoning for Fragments of Autoepistemic Logic
arXiv: Logic in Computer Science, 2010Co-Authors: Nadia Creignou, Arne Meier, Michael Thomas, Heribert VollmerAbstract:Autoepistemic Logic extends propositional Logic by the modal operator L. A formula that is preceded by an L is said to be "believed". The Logic was introduced by Moore 1985 for modeling an ideally rational agent's behavior and reasoning about his own beliefs. In this paper we analyze all Boolean fragments of Autoepistemic Logic with respect to the computational complexity of the three most common decision problems expansion existence, brave reasoning and cautious reasoning. As a second contribution we classify the computational complexity of counting the number of stable expansions of a given knowledge base. To the best of our knowledge this is the first paper analyzing the counting problem for Autoepistemic Logic.
Grigori Schwarz - One of the best experts on this subject based on the ideXlab platform.
-
On embedding default Logic into Moore's Autoepistemic Logic
Artificial Intelligence, 1996Co-Authors: Grigori SchwarzAbstract:Abstract Recently Gottlob proved [2] that there does not exist a faithful modular translation of default Logic into Autoepistemic Logic, and presented a non-modular translation. Gottlob's translation, however, is indirect (it uses “nonmonotonic Logic N” as an intermediate point), quite complex and exploits sophisticated encoding of proof theory in Autoepistemic formulas. We provide a simpler and more intuitive (non-modular) direct translation. In addition, our argument is purely model-theoretic.
-
Autoepistemic Logic and introspective circumscription
Theoretical Aspects of Rationality and Knowledge, 1994Co-Authors: Michael Gelfond, Vladimir Lifschitz, Halina Przymusinska, Grigori SchwarzAbstract:We investigate the relationship between two epistemic nonmonotonic formalisms: Autoepistemic Logic and introspective circumscription. Finitely axiomatized Autoepistemic theories are shown to be equivalent to the propositional case of introspective circumscription. This theorem is applied to the problem of relating the usual "minimizing" circumscription to Autoepistemic Logic.
-
Modal nonmonotonic Logics: ranges, characterization, computation
Journal of the ACM, 1993Co-Authors: V. Wiktor Marek, Grigori Schwarz, Miroslaw TruszczynskiAbstract:Many nonmonotonic formalism, including default Logic, Logic programming with stable models, and Autoepistemic Logic, can be represented faithfully by means of modal nonmonotonic Logics in the family proposed by McDermott and Doyle. In this paper properties of Logics in this family are thoroughly investigated. We present several results on characterization of expansions. These results are applicable to a wide class of nonmonotonic modal Logics. Using these characterization results, algorithms for computing expansions for finite theories are developed. Perhaps the most important finding of this paper is that the structure of the family of modal nonmonotonic Logics is much simpler than that of the family of underlying modal (monotonic) Logics. Namely, it is often the case that different monotonic modal Logics collapse to the same nonmonotonic system. We exhibit four families of Logics whose nonmonotonic variants coincide: 5-KD45, TW5-SW5, N-WK , and W5-D4WB . These nonmonotonic Logics naturally represent Logics related to commonsense reasoning and knowledge representation such as Autoepistemic Logic, reflexive Autoepistemic Logic, default Logic, and truth maintenance with negation.
