Semantic forgetting in answer set programming

The notion of forgetting, also known as variable elimination, has been investigated extensively in the context of classical logic, but less so in (nonmonotonic) logic programming and nonmonotonic reasoning. The few approaches that exist are based on syntactic modifications of a program at hand. In this paper, we establish a declarative theory of forgetting for disjunctive logic programs under answer set semantics that is fully based on semantic grounds. The suitability of this theory is justified by a number of desirable properties. In particular, one of our results shows that our notion of forgetting can be entirely captured by classical forgetting. We present several algorithms for computing a representation of the result of forgetting, and provide a characterization of the computational complexity of reasoning from a logic program under forgetting. As applications of our approach, we present a fairly general framework for resolving conflicts in inconsistent knowledge bases that are represented by disjunctive logic programs, and we show how the semantics of inheritance logic programs and update logic programs from the literature can be characterized through forgetting. The basic idea of the conflict resolution framework is to weaken the preferences of each agent by forgetting certain knowledge that causes inconsistency. In particular, we show how to use the notion of forgetting to provide an elegant solution for preference elicitation in disjunctive logic programming.     

Realistic model for temporal reasoning in real-time patient monitoring

Time is a central factor in patient monitoring. Introduction of domain-dependent knowledge is essential to ensure efficiency of time managers, especially when embedded into systems that interact with the real world. We present a realistic temporal reasoning model based on two basic cognitive mechanisms: aggregation of similar observed situations and forgetting of non-relevant information. We describe in detail how we represented the proposed model and how, by refinement of domain-independent temporal entities and inferences, we added domain specific knowledge to manage a clinical therapy. The model allows clinical observations to be incrementally interpreted as they are acquired by an intelligent system, mainly reactive in its reasoning, for the management of patients receiving respiratory support.     

Probabilistic Default Reasoning with Conditional Constraints

We present an approach to reasoning from statistical and subjective knowledge, which is based on a combination of probabilistic reasoning from conditional constraints with approaches to default reasoning from conditional knowledge bases. More precisely, we introduce the notions of z-, lexicographic, and conditional entailment for conditional constraints, which are probabilistic generalizations of Pearl's entailment in system Z, Lehmann's lexicographic entailment, and Geffner's conditional entailment, respectively. We show that the new formalisms have nice properties. In particular, they show a similar behavior as reference-class reasoning in a number of uncontroversial examples. The new formalisms, however, also avoid many drawbacks of reference-class reasoning. More precisely, they can handle complex scenarios and even purely probabilistic subjective knowledge as input. Moreover, conclusions are drawn in a global way from all the available knowledge as a whole. We then show that the new formalisms also have nice general nonmonotonic properties. In detail, the new notions of z-, lexicographic, and conditional entailment have similar properties as their classical counterparts. In particular, they all satisfy the rationality postulates proposed by Kraus, Lehmann, and Magidor, and they have some general irrelevance and direct inference properties. Moreover, the new notions of z- and lexicographic entailment satisfy the property of rational monotonicity. Furthermore, the new notions of z-, lexicographic, and conditional entailment are proper generalizations of both their classical counterparts and the classical notion of logical entailment for conditional constraints. Finally, we provide algorithms for reasoning under the new formalisms, and we analyze its computational complexity.     

On the soundness,completeness and applicability of the logic of knowledge and communicative commitments in multi-agent systems

Benthem’s correspondence theory is one of the most important tools of the theory of modal logics developed in the last three decades. Correspondence theory, a subfield of the model theory, reflects a systematic study of relations between classes of frames and modal language. In this paper, we use correspondence theory for modal logics to solve a problem not addressed yet in the literature, namely the soundness and completeness of a logic combining two different, yet related modalities: agents’ knowledge and commitments. The paper proves the soundness and completeness of this logic called CTLKC⁺. This work is highly significant as it proves that combining the two agents’ modalities resulted in a consistent logic that can be used to design reliable systems. The methodology is as follows: we develop a set of reasoning postulates (axioms) that reflect the interaction between agents’ knowledge and social commitments in multi-agent system (MAS) using the CTLKC⁺ logic and correspond them to certain classes of frames. In particular, we first give a name, formalization and meaning for each postulate. Then, we correspond the postulates to certain classes of frames and provide the required proofs. Thereafter, we present a discussion that illustrates the importance of the proposed postulates in MASs using a concrete application example called the NetBill protocol taken from the business domain. Finally, we show how the postulates were addressed in the literature. The existence of such a correspondence allows us to prove that the logic generated by any subset of these postulates is sound and complete with respect to models that are based on the corresponding frames. The ultimate goal of this paper is to further assess the logic of knowledge and commitments (CTLKC⁺) from a new perspective (i.e., the soundness and completeness). Consequently, this work advances the literature of logics in MASs and closes a gap that has not been explored before.     

Adaptive case-based reasoning using retention and forgetting strategies

Case-based reasoning systems need to maintain their case base in order to avoid performance degradation. Degradation mainly results from memory swamping or exposure to harmful experiences and so, it becomes vital to keep a compact, competent case base. This paper proposes an adaptive case-based reasoning model that develops the case base during the reasoning cycle by adding and removing cases. The rationale behind this approach is that a case base should develop over time in the same way that a human being evolves her overall knowledge: by incorporating new useful experiences and forgetting invaluable ones. Accordingly, our adaptive case-based reasoning model evolves the case base by using a measure of “case goodness” in different retention and forgetting strategies. This paper presents empirical studies of how the combination of this new goodness measure and our adaptive model improves three different performance measures: classification accuracy, efficiency and case base size.     

Reasoning about reasoning in a meta-level architecture

In this paper we discuss reasoning about reasoning in a multiple agent scenario. We consider agents that are perfect reasoners, loyal, and that can take advantage of both the knowledge and ignorance of other agents. The knowledge representation formalism we use is (full) first order predicate calculus, where different agents are represented by different theories, and reasoning about reasoning is realized via a meta-level representation of knowledge and reasoning. The framework we provide is pretty general: we illustrate it by showing a machine checked solution to the three wisemen puzzle. The agents' knowledge is organized into units: the agent's own knowledge about the world and its knowledge about other agents are units containing object-level knowledge; a unit containing meta-level knowledge embodies the reasoning about reasoning and realizes the link among units. In the paper we illustrate the meta-level architecture we propose for problem solving in a multi-agent scenario; we discuss our approach in relation to the modal one and we compare it with other meta-level architectures based on logic. Finally, we look at a class of applications that can be effectively modeled by exploiting the meta-level approach to reasoning about knowledge and reasoning.     

Agent信念的遗忘修正方法

为了使信念修正能够满足最小改变原则,首先基于遗忘理论定义遗忘收缩算子,并且证明该算子满足必要AGM收缩假定;然后通过Levi Identity构建遗忘修正算子;最后给出遗忘修正方法和多次遗忘修正算法。实例分析表明,算法具有可行性和有效性,能够得到较满意的修正结果。     

Reasoning in inconsistent knowledge bases

Databases and knowledge bases could be inconsistent in many ways. For example, during the construction of an expert system, we may consult many different experts. Each expert may provide us with a group of rules and facts which are self-consistent. However, when we coalesce the facts and rules provided by these different experts, inconsistency may arise. Alternatively, knowledge bases may be inconsistent due to the presence of some erroneous information. Thus, a framework for reasoning about knowledge bases that contain inconsistent information is necessary. However, existing frameworks for reasoning with inconsistency do not support reasoning by cases and reasoning with the law of excluded middle (“everything is either true or false”). In this paper, we show how reasoning with cases, and reasoning with the law of excluded middle may be captured. We develop a declarative and operational semantics for knowledge bases that are possibly inconsistent. We compare and contrast our work with work on explicit and non-monotonic modes of negation in logic programs and suggest under what circumstances one framework may be preferred over another     

On the interaction between knowledge and social commitments in multi-agent systems

Both knowledge and social commitments have received considerable attention in Multi-Agent Systems (MASs), specially for multi-agent communication. Plenty of work has been carried out to define their semantics. However, the relationship between social commitments and knowledge has not been investigated yet. In this paper, we aim to explore such a relationship from the semantics and model checking perspectives with respect to CTLK logic (an extension of CTL logic with modality for reasoning about knowledge) and CTLC logic (an extension of CTL with modalities for reasoning about commitments and their fulfillments). To analyze this logical relationship, we simply combine the two logics in one new logic named CTLKC. The purpose of such a combination is not to advocate a new logic, but only to express and figure out some reasoning postulates merging both knowledge and commitments as they are currently defined in the literature. By so doing, we identify some paradoxes in the new logic showing that simply combining current versions of commitment and knowledge logics results in a logical language that violates some fundamental intuitions. Consequently, we propose CTLKC⁺, a new logic that fixes the identified paradoxes and allows us to reason about social commitments and knowledge simultaneously in a consistent manner. Furthermore, we address the problem of model checking CTLKC⁺ by reducing it to the problem of model checking GCTL^?, a generalized version of CTL^? with action formulae. By doing so, we directly benefit from CWB-NC, the model checker of GCTL^?. Using this reduction, we also prove that the computational complexity of model checking CTLKC⁺ is still PSPACE-complete for concurrent programs as the complexity of model checking CTLK and CTLC separately.     

THE SCOPE OF DIMENSIONAL ANALYSIS IN QUALITATIVE REASONING

Dimensional analysis, traditionally used in physics and engineering to identify quantitative relationships, has recently been applied to qualitative reasoning of physical systems. We illustrate some problems of this approach. In the light of this, we reexamine the fundamentals of dimensional analysis in order to more precisely characterize its scope and limitations as a tool in qualitative reasoning. We also explore its relationship to state equation representations of physical systems. In particular, we describe its value in providing a set of constraints to reduce the ambiguity that bedevils qualitative reasoning schemes. We argue that dimensional analysis should not be seen as a substitute for knowledge about the physics but rather a supplement to other sources of knowledge.     

Case-Base Maintenance in a Multimodal Reasoning System

The definition of suitable case-base maintenance policies is widely recognized as a major key to success for case-based systems; underestimating this issue may lead to systems that either do not fulfill their role of knowledge management and preservation or that do not perform adequately under performance dimensions, namely, computation time and competence and quality of solutions. The goal of this article is to analyze some automatic case-base management strategies in the context of a multimodal architecture combining case-based reasoning and model-based reasoning. We propose and compare two different methodologies, the first one, called replace , is a competence-based strategy aimed at replacing a set of stored cases with the current one, if the latter exhibits an estimated competence comparable with the estimated competence of the considered set of stored cases. The second one, called learning by failure with forgetting (LFF), is based on incremental learning of cases interleaved with off-line processes of forgetting (deleting) cases whose usage does not fulfill specific utility conditions. Results from an extensive experimental analysis in an industrial plant diagnosis domain are reported, showing the usefulness of both strategies with respect to the maintenance of suitable performance levels for the target system.     

Belief revision in structured probabilistic argumentation

In real-world applications, knowledge bases consisting of all the available information for a specific domain, along with the current state of affairs, will typically contain contradictory data, coming from different sources, as well as data with varying degrees of uncertainty attached. An important aspect of the effort associated with maintaining such knowledge bases is deciding what information is no longer useful; pieces of information may be outdated; may come from sources that have recently been discovered to be of low quality; or abundant evidence may be available that contradicts them. In this paper, we propose a probabilistic structured argumentation framework that arises from the extension of Presumptive Defeasible Logic Programming (PreDeLP) with probabilistic models, and argue that this formalism is capable of addressing these basic issues. The formalism is capable of handling contradictory and uncertain data, and we study non-prioritized belief revision over probabilistic PreDeLP programs that can help with knowledge-base maintenance. For belief revision, we propose a set of rationality postulates — based on well-known ones developed for classical knowledge bases — that characterize how these belief revision operations should behave, and study classes of operators along with theoretical relationships with the proposed postulates, including representation theorems stating the equivalence between classes of operators and their associated postulates. We then demonstrate how our framework can be used to address the attribution problem in cyber security/cyber warfare.     

A rule based knowledge transaction model for mobile environments

In this paper, we propose and formalize a rule based knowledge transaction model for mobile environments. Our model integrates the features of both mobile environments and intelligent agents. We use logic programming as a mathematic tool and formal specification method to study knowledge transaction in mobile environments. Our knowledge transaction model has the following major advantages: (1) It can be used for knowledge transaction representation, formalization and knowledge reasoning in mobile environments. (2) It is knowledge oriented and has a declarative semantics inherited from logic programming. (3) It is a formalization that can be applied to general problem domains. We show that our model can be used for knowledge transaction representation, formalization and knowledge reasoning in mobile environments.     

Distributed reasoning with ontologies and rules in order-sorted logic programming

Integrating ontologies and rules on the Semantic Web enables software agents to interoperate between them; however, this leads to two problems. First, reasoning services in SWRL (a combination of OWL and RuleML) are not decidable. Second, no studies have focused on distributed reasoning services for integrating ontologies and rules in multiple knowledge bases. In order to address these problems, we consider distributed reasoning services for ontologies and rules with decidable and effective computation. In this paper, we describe multiple order-sorted logic programming that transfers rigid properties from knowledge bases. Our order-sorted logic contains types (rigid sorts), non-rigid sorts, and unary predicates that distinctly express essential sorts, non-essential sorts, and non-sortal properties. We formalize the order-sorted Horn-clause calculus for such properties in a single knowledge base. This calculus is extended by embedding rigid-property derivation for multiple knowledge bases, each of which can transfer rigid-property information from other knowledge bases. In order to enable the reasoning to be effective and decidable, we design a query-answering system that combines order-sorted linear resolution and rigid-property resolution as top-down algorithms.     

Instantiating abstract argumentation with classical logic arguments: Postulates and properties

In this paper we investigate the use of classical logic as a basis for instantiating abstract argumentation frameworks. In the first part, we propose desirable properties of attack relations in the form of postulates and classify several well-known attack relations from the literature with regards to the satisfaction of these postulates. Furthermore, we provide additional postulates that help us prove characterisation results for these attack relations. In the second part of the paper, we present postulates regarding the logical content of extensions of argument graphs that may be constructed with classical logic. We then conduct a comprehensive study of the status of these postulates in the context of the various combinations of attack relations and extension semantics.     

On the evaluation of argumentation formalisms

Argumentation theory has become an important topic in the field of AI. The basic idea is to construct arguments in favor and against a statement, to select the “acceptable” ones and, finally, to determine whether the original statement can be accepted or not. Several argumentation systems have been proposed in the literature. Some of them, the so-called rule-based systems, use a particular logical language with strict and defeasible rules. While these systems are useful in different domains (e.g. legal reasoning), they unfortunately lead to very unintuitive results, as is discussed in this paper. In order to avoid such anomalies, in this paper we are interested in defining principles, called rationality postulates, that can be used to judge the quality of a rule-based argumentation system. In particular, we define two important rationality postulates that should be satisfied: the consistency and the closure of the results returned by that system. We then provide a relatively easy way in which these rationality postulates can be warranted for a particular rule-based argumentation system developed within a European project on argumentation.     

Spatial reasoning in a fuzzy region connection calculus

Although the region connection calculus (RCC) offers an appealing framework for modelling topological relations, its application in real-world scenarios is hampered when spatial phenomena are affected by vagueness. To cope with this, we present a generalization of the RCC based on fuzzy set theory, and discuss how reasoning tasks such as satisfiability and entailment checking can be cast into linear programming problems. We furthermore reveal that reasoning in our fuzzy RCC is NP-complete, thus preserving the computational complexity of reasoning in the RCC, and we identify an important tractable subfragment. Moreover, we show how reasoning tasks in our fuzzy RCC can also be reduced to reasoning tasks in the original RCC. While this link with the RCC could be exploited in practical reasoning algorithms, we mainly focus on the theoretical consequences. In particular, using this link we establish a close relationship with the Egg-Yolk calculus, and we demonstrate that satisfiable knowledge bases can be realized by fuzzy regions in any dimension.