An Interpretation of Default Logic in Minimal Temporal Epistemic Logic

When reasoning about complex domains, where information available is usually only partial, nonmonotonic reasoning can be an important tool. One of the formalisms introduced in this area is Reiter's Default Logic (1980). A characteristic of this formalism is that the applicability of default (inference) rules can only be verified in the future of the reasoning process. We describe an interpretation of default logic in temporal epistemic logic which makes this characteristic explicit. It is shown that this interpretation yields a semantics for default logic based on temporal epistemic models. A comparison between the various semantics for default logic will show the differences and similarities of these approaches and ours.     

Reasoning with Sets of Defaults in Default Logic

We present a general approach for representing and reasoning with sets of defaults in default logic, focusing on reasoning about preferences among sets of defaults. First, we consider how to control the application of a set of defaults so that either all apply (if possible) or none do (if not). From this, an approach to dealing with preferences among sets of default rules is developed. We begin with an ordered default theory , consisting of a standard default theory, but with possible preferences on sets of rules. This theory is transformed into a second, standard default theory wherein the preferences are respected. The approach differs from other work, in that we obtain standard default theories and do not rely on prioritized versions of default logic. In practical terms this means we can immediately use existing default logic theorem provers for an implementation. Also, we directly generate just those extensions containing the most preferred applied rules; in contrast, most previous approaches generate all extensions, then select the most preferred. In a major application of the approach, we show how semimonotonic default theories can be encoded so that reasoning can be carried out at the object level. With this, we can reason about default extensions from within the framework of a standard default logic. Hence one can encode notions such as skeptical and credulous conclusions, and can reason about such conclusions within a single extension.     

Logic Programs with Ordered Disjunction

Logic programs with ordered disjunction (LPODs) contain a new connective which allows representing alternative, ranked options for problem solutions in the heads of rules: A × B intuitively means that if possible A , but if A is not possible, then at least B . The semantics of logic programs with ordered disjunction is based on a preference relation on answer sets. We show how LPODs can be implemented using answer set solvers for normal programs. The implementation is based on a generator, which produces candidate answer sets and a tester which checks whether a given candidate is maximally preferred and produces a better candidate if it is not. We also discuss the complexity of reasoning tasks based on LPODs and possible applications.     

Modeling uncertainty reasoning with possibilistic Petri nets

Manipulation of perceptions is a remarkable human capability in a wide variety of physical and mental tasks under fuzzy or uncertain surroundings. Possibilistic reasoning can be treated as a mechanism that mimics human inference mechanisms with uncertain information. Petri nets are a graphical and mathematical modeling tool with powerful modeling and analytical ability. The focus of this paper is on the integration of Petri nets with possibilistic reasoning to reap the benefits of both formalisms. This integration leads to a possibilistic Petri nets model (PPN) with the following features. A possibilistic token carries information to describe an object and its corresponding possibility and necessity measures. Possibilistic transitions are classified into four types: inference transitions, duplication transitions, aggregation transitions, and aggregation-duplication transitions. A reasoning algorithm, based on possibilistic Petri nets, is also presented to improve the efficiency of possibilistic reasoning and an example related to diagnosis of cracks in reinforced concrete structures is used to illustrate the proposed approach.     

Binary naive possibilistic classifiers: Handling uncertain inputs

Possibilistic networks are graphical models particularly suitable for representing and reasoning with uncertain and incomplete information. According to the underlying interpretation of possibilistic scales, possibilistic networks are either quantitative (using product‐based conditioning) or qualitative (using min‐based conditioning). Among the multiple tasks, possibilitic models can be used for, classification is a very important one. In this paper, we address the problem of handling uncertain inputs in binary possibilistic‐based classification. More precisely, we propose an efficient algorithm for revising possibility distributions encoded by a naive possibilistic network. This algorithm is suitable for binary classification with uncertain inputs since it allows classification in polynomial time using several efficient transformations of initial naive possibilistic networks. © 2009 Wiley Periodicals, Inc.     

Paraconsistent Declarative Semantics for Extended Logic Programs

We introduce a fixpoint semantics for logic programs with two kinds of negation: an explicit negation and a negation-by-failure. The programs may also be prioritized, that is, their clauses may be arranged in a partial order that reflects preferences among the corresponding rules. This yields a robust framework for representing knowledge in logic programs with a considerable expressive power. The declarative semantics for such programs is particularly suitable for reasoning with uncertainty, in the sense that it pinpoints the incomplete and inconsistent parts of the data, and regards the remaining information as classically consistent. As such, this semantics allows to draw conclusions in a non-trivial way, even in cases that the logic programs under consideration are not consistent. Finally, we show that this formalism may be regarded as a simple and flexible process for belief revision.     

可能性理论与不相容知识处理

Ｄ．Ｄｕｂｏｉｓ和Ｈ．Ｐｒａｄｅ提出的可能性逻辑是一种基于可能性理论的非经典逻辑，主要和于不确定证据推理。可能性逻辑不同于模糊逻辑，因为模糊逻辑处理非布尔公式，其命题中包模糊谓词，而可能性逻辑处理布尔公式，其中只包含经典命题的和谓词。本文尝试在可能性理论的框架下进行不相容知识库的维护和问题求解。这里的知识表示是基于可能性逻辑的。为此，我们提出了两种不同的方法：第一种方法在计算命题可信度时，要考虑所     

PRL: A probabilistic relational language

In this paper, we describe the syntax and semantics for a probabilistic relational language (PRL). PRL is a recasting of recent work in Probabilistic Relational Models (PRMs) into a logic programming framework. We show how to represent varying degrees of complexity in the semantics including attribute uncertainty, structural uncertainty and identity uncertainty. Our approach is similar in spirit to the work in Bayesian Logic Programs (BLPs), and Logical Bayesian Networks (LBNs). However, surprisingly, there are still some important differences in the resulting formalism; for example, we introduce a general notion of aggregates based on the PRM approaches. One of our contributions is that we show how to support richer forms of structural uncertainty in a probabilistic logical language than have been previously described. Our goal in this work is to present a unifying framework that supports all of the types of relational uncertainty yet is based on logic programming formalisms. We also believe that it facilitates understanding the relationship between the frame-based approaches and alternate logic programming approaches, and allows greater transfer of ideas between them. Editors: Hendrik Blockeel, David Jensen and Stefan Kramer An erratum to this article is available at .     

A Formalism for Representing and Reasoning with Temporal Information,Event and Change

In this paper we present a general formalism for representing and reasoning with temporal information, event and change. The temporal framework is a theory of time that takes both points and interval as temporal primitives and where the base logic is that of Kleene’s three-valued logic. Thus, we can avoid the Divided Instant Problem (DIP). We present a three-valued based Temporal First-Order Nonmonotonic Logic (TFONL) that employs an explicit representation of time and events. We may embody default logic into TFONL, which takes into consideration the frame, qualification and ramification problems.     

Possibilistic uncertainty handling for answer set programming

In this work, we introduce a new framework able to deal with a reasoning that is at the same time non monotonic and uncertain. In order to take into account a certainty level associated to each piece of knowledge, we use possibility theory to extend the non monotonic semantics of stable models for logic programs with default negation. By means of a possibility distribution we define a clear semantics of such programs by introducing what is a possibilistic stable model. We also propose a syntactic process based on a fix-point operator to compute these particular models representing the deductions of the program and their certainty. Then, we show how this introduction of a certainty level on each rule of a program can be used in order to restore its consistency in case of the program has no model at all. Furthermore, we explain how we can compute possibilistic stable models by using available softwares for Answer Set Programming and we describe the main lines of the system that we have developed to achieve this goal.     

Defeasible logic versus Logic Programming without Negation as Failure

Recently there has been increased interest in logic programming-based default reasoning approaches which are not using negation-as-failure in their object language. Instead, default reasoning is modelled by rules and a priority relation among them. In this paper we compare the expressive power of two approaches in this family of logics: Defeasible Logic, and sceptical Logic Programming without Negation as Failure (LPwNF). Our results show that the former has a strictly stronger expressive power. The difference is caused by the latter logic's failure to capture the idea of teams of rules supporting a specific conclusion.     

Introducing possibilistic logic in ILP for dealing with exceptions

In this paper we propose a new formalization of the inductive logic programming (ILP) problem for a better handling of exceptions. It is now encoded in first-order possibilistic logic. This allows us to handle exceptions by means of prioritized rules, thus taking lessons from non-monotonic reasoning. Indeed, in classical first-order logic, the exceptions of the rules that constitute a hypothesis accumulate and classifying an example in two different classes, even if one is the right one, is not correct. The possibilistic formalization provides a sound encoding of non-monotonic reasoning that copes with rules with exceptions and prevents an example to be classified in more than one class. The benefits of our approach with respect to the use of first-order decision lists are pointed out. The possibilistic logic view of ILP problem leads to an optimization problem at the algorithmic level. An algorithm based on simulated annealing that in one turn computes the set of rules together with their priority levels is proposed. The reported experiments show that the algorithm is competitive to standard ILP approaches on benchmark examples.     

A new approach to hybrid probabilistic logic programs

This paper presents a novel revision of the framework of Hybrid Probabilistic Logic Programming, along with a complete semantics characterization, to enable the encoding of and reasoning about real-world applications. The language of Hybrid Probabilistic Logic Programs framework is extended to allow the use of non-monotonic negation, and two alternative semantical characterizations are defined: stable probabilistic model semantics and probabilistic well-founded semantics. These semantics generalize the stable model semantics and well-founded semantics of traditional normal logic programs, and they reduce to the semantics of Hybrid Probabilistic Logic programs for programs without negation. It is the first time that two different semantics for Hybrid Probabilistic Programs with non-monotonic negation as well as their relationships are described. This proposal provides the foundational grounds for developing computational methods for implementing the proposed semantics. Furthermore, it makes it clearer how to characterize non-monotonic negation in probabilistic logic programming frameworks for commonsense reasoning. An erratum to this article can be found at     

SNePSwD: A newcomer to the SNePS family

Abstract

SNePS 2.1 is a knowledge representation and reasoning system that records the dependencies among propositions that are needed to perform a revision of beliefs when a contradiction is detected. The reasoning of SNePS 2.1 is based on a monotonic logic and the system has no provisos for performing an automatic revision of beliefs. In this paper we present SNePSwD that extends the capabilities of SNePS 2.1 along two dimensions: (1) it is able to represent default rules and to perform default reasoning, i.e. the logic underlying SNePSwD is non-monotonic; (2) it accepts the specification of preferences between hypotheses and uses them to decide which hypotheses to discard to resolve a contradiction. This latter possibility allows a semi-automatic contradiction resolution (in some cases, even completely automatic). We discuss the motivations for the creation of SNePSwD, present the form of default rules it uses, discuss the meaning of each of the three kinds of consequence, and describe how preferences can be specified among propositions and how these preferences are used in the process of belief revision. Finally we present examples that illustrate the aspects discussed in the paper.     

Automated reasoning using possibilistic logic: semantics, beliefrevision, and variable certainty weights

An approach to automated deduction under uncertainty, based on possibilistic logic, is described; for that purpose we deal with clauses weighted by a degree that is a lower bound of a necessity or a possibility measure, according to the nature of the uncertainty. Two resolution rules are used for coping with the different situations, and the classical refutation method can be generalized with these rules. Also, the lower bounds are allowed to be functions of variables involved in the clauses, which results in hypothetical reasoning capabilities. In cases where only lower bounds of necessity measures are involved, a semantics is proposed in which the completeness of the extended resolution principle is proved. The relation between our approach and the idea of minimizing abnormality is briefly discussed. Moreover, deduction from a partially inconsistent knowledge base can be managed in this approach and captures a form of nonmonotonicity     

Complexity results and algorithms for possibilistic influence diagrams

In this article we present the framework of Possibilistic Influence Diagrams (PID), which allows to model in a compact form problems of sequential decision making under uncertainty, when only ordinal data on transitions likelihood or preferences are available. The graphical part of a PID is exactly the same as that of usual influence diagrams, however the semantics differ. Transition likelihoods are expressed as possibility distributions and rewards are here considered as satisfaction degrees. Expected utility is then replaced by anyone of the two possibilistic qualitative utility criteria (optimistic and pessimistic) for evaluating strategies in a PID. We then describe decision tree-based methods for evaluating PID and computing optimal strategies and we study the computational complexity of PID optimisation problems for both cases. Finally, we propose a dedicated variable elimination algorithm that can be applied to both optimistic and pessimistic cases for solving PID.     

Nonmonotonic reasoning as prioritized argumentation

This paper proposes a formalism for nonmonotonic reasoning based on prioritized argumentation. We argue that nonmonotonic reasoning in general can be viewed as selecting monotonic inferences by a simple notion of priority among inference rules. More importantly, these types of constrained inferences can be specified in a knowledge representation language where a theory consists of a collection of rules of first order formulas and a priority among these rules. We recast default reasoning as a form of prioritized argumentation and illustrate how the parameterized formulation of priority may be used to allow various extensions and modifications to default reasoning. We also show that it is possible, but more difficult, to express prioritized argumentation by default logic: Even some particular forms of prioritized argumentation cannot be represented modularly by defaults under the same language     

Inference in possibilistic network classifiers under uncertain observations

Possibilistic networks, which are compact representations of possibility distributions, are powerful tools for representing and reasoning with uncertain and incomplete information in the framework of possibility theory. They are like Bayesian networks but lie on possibility theory to deal with uncertainty, imprecision and incompleteness. While classification is a very useful task in many real world applications, possibilistic network-based classification issues are not well investigated in general and possibilistic-based classification inference with uncertain observations in particular. In this paper, we address on one hand the theoretical foundations of inference in possibilistic classifiers under uncertain inputs and propose on the other hand a novel efficient algorithm for the inference in possibilistic network-based classification under uncertain observations. We start by studying and analyzing the counterpart of Jeffrey’s rule in the framework of possibility theory. After that, we address the validity of Markov-blanket criterion in the context of possibilistic networks used for classification with uncertain inputs purposes. Finally, we propose a novel algorithm suitable for possibilistic classifiers with uncertain observations without assuming any independence relations between observations. This algorithm guarantees the same results as if classification were performed using the possibilistic counterpart of Jeffrey’s rule. Classification is achieved in polynomial time if the target variable is binary. The basic idea of our algorithm is to only search for totally plausible class instances through a series of equivalent and polynomial transformations applied on the possibilistic classifier taking into account the uncertain observations.