Philippe Besnard

AIJ Journal 2020 Journal Article

Relative inconsistency measures

• Philippe Besnard
• John Grant

The literature on inconsistency measures has ignored a distinction, that is, differentiating absolute measures and relative measures. An absolute measure gives the total amount of inconsistency in the knowledge base but a relative measure computes, by some criteria, the proportion of the base that is inconsistent. To compare the inconsistency measures, researchers have proposed postulates for such measures. We split these postulates into three groups: ones (including two new postulates) that relative measures should satisfy, ones inappropriate for relative measures, and ones that relative measures may satisfy. We obtain some new results upon the relationships between these groups of postulates. On these grounds, we introduce a formal definition for relative inconsistency measures. We consider some relative measures previously proposed and define several new ones that serve as examples. We show that all of these measures satisfy the new formal definition.

ECAI Conference 2020 Conference Paper

Semantics of Negative Sequential Patterns

• Philippe Besnard
• Thomas Guyet

In the field of pattern mining, a negative sequential pattern is specified by means of a sequence consisting of events to occur and of other events, called negative events, to be absent. For instance, containment of the pattern ⟨a ¬b c⟩ arises with an occurrence of a and a subsequent occurrence of c but no occurrence of b in between. This article is to shed light on the ambiguity of such a seemingly intuitive notation and we identify eight possible semantics for the containment relation between a pattern and a sequence. These semantics are illustrated and formally studied, in particular we propose dominance and equivalence relations between them. Also we prove that support is anti-monotonic for some of these semantics. Some of the results are discussed with the aim of developing algorithms to extract efficiently frequent negative patterns.

AAAI Conference 2015 Conference Paper

On Computing Maximal Subsets of Clauses that Must Be Satisfiable with Possibly Mutually-Contradictory Assumptive Contexts

• Philippe Besnard
• Eric Grégoire
• Jean-Marie Lagniez

An original method for the extraction of one maximal subset of a set of Boolean clauses that must be satisfiable with possibly mutually contradictory assumptive contexts is motivated and experimented. Noticeably, it performs a direct computation and avoids the enumeration of all subsets that are satisfiable with at least one of the contexts. The method applies for subsets that are maximal with respect to inclusion or cardinality.

FLAP Journal 2014 Journal Article

A Note on Directions for Cumulativity.

• Philippe Besnard

Logical systems are often characterized as closure systems, by means of unary operators satisfying Reflexivity, Idempotence and Monotony. In order to capture non-monotone systems, Monotony can be replaced by Cumulativity, namely Restricted Cut and Cautious Monotony. This short note shows that in such a context, Restricted Cut is redundant.

JELIA Conference 2014 Conference Paper

Revisiting Postulates for Inconsistency Measures

• Philippe Besnard

Abstract Postulates for inconsistency measures are examined, the set of postulates due to Hunter and Konieczny being the starting point. Objections are raised against a few individual postulates. More general shortcomings are discussed and a new series of postulates is introduced.

ECAI Conference 2012 Conference Paper

Preemption Operators

• Philippe Besnard
• Éric Grégoire
• Sébastien Ramon

We introduce a family of operators for belief change that aim at making a new piece of information to be preemptive so that any former belief subsuming it is given up. That is, the current belief base is to be altered even in the case that it is logically consistent with the new piece of information. Existing operators for belief revision are inadequate for this purpose because they amount to set-theoretic union in a contradiction-free case. We propose a series of postulates for such preemption operators. We show that a preemption operator can be defined as a multiple contraction followed by an expansion, drawing on operators from belief revision.

AIJ Journal 2009 Journal Article

Encoding deductive argumentation in quantified Boolean formulae

• Philippe Besnard
• Anthony Hunter
• Stefan Woltran

There are a number of frameworks for modelling argumentation in logic. They incorporate a formal representation of individual arguments and techniques for comparing conflicting arguments. A common assumption for logic-based argumentation is that an argument is a pair 〈 Φ, α 〉 where Φ is minimal subset of the knowledge-base such that Φ is consistent and Φ entails the claim α. Different logics provide different definitions for consistency and entailment and hence give us different options for argumentation. Classical propositional logic is an appealing option for argumentation but the computational viability of generating an argument is an issue. To better explore this issue, we use quantified Boolean formulae to characterise an approach to argumentation based on classical logic.

ECAI Conference 2008 Conference Paper

Deriving explanations from causal information

• Philippe Besnard
• Marie-Odile Cordier
• Yves Moinard

We define an inference system to capture explanations based on causal statements, using an ontology in the form of an IS-A hierarchy. We introduce a simple logical language which makes it possible to express that a fact causes another fact and that a fact explains another fact. We present a set of formal inference patterns from causal statements to explanation statements. We introduce an elementary ontology which gives greater expressiveness to the system while staying close to propositional reasoning. We provide an inference system that captures the patterns discussed, in a datalog (limited predicate) framework.

KR Conference 2006 Conference Paper

Knowledgebase compilation for efficient logical argumentation

• Philippe Besnard
• Anthony Hunter

There are a number of frameworks for modelling argumentation in logic. They incorporate a formal representation of individual arguments and techniques for comparing conflicting arguments. A common assumption for logic-based argumentation is that an argument is a pair (X, p) where X is minimal subset of the knowledgebase such that X is consistent and X entails the claim p. Different logics are based on different definitions for entailment and consistency, and give us different options for argumentation. For a variety of logics, in particular for classical logic, the computational viability of generating arguments is an issue. Here, we present a solution that involves compiling a knowledgebase K based on the set of minimal inconsistent subsets of K, and then generating arguments from the compilation. Whilst generating a compilation is expensive, generating arguments from a compilation is relatively inexpensive.

ECAI Conference 2006 Conference Paper

Variable Forgetting in Preference Relations over Propositional Domains

• Philippe Besnard
• Jérôme Lang
• Pierre Marquis

Representing (and reasoning about) preference relations over combinatorial domains is computationally expensive. For many problems involving such preferences, it is relevant to simplify them by projecting them on a subset of variables. We investigate several possible definitions, focusing without loss of generality on propositional (binary) variables.

AAAI Conference 2005 Conference Paper

Practical First-Order Argumentation

• Philippe Besnard

There are many frameworks for modelling argumentation in logic. They include a formal representation of individual arguments and techniques for comparing conflicting arguments. A problem with these proposals is that they do not consider arguments for and against first-order formulae. We present a framework for first-order logic argumentation based on argument trees that provide a way of exhaustively collating arguments and counter-arguments. A difficulty with first-order argumentation is that there may be many arguments and counterarguments even with a relatively small knowledgebase. We propose rationalizing the arguments under consideration with the aim of reducing redundancy and highlighting key points.

KR Conference 2004 Conference Paper

Characterization of semantics for argument systems

• Philippe Besnard
• Sylvie Doutre

We consider Dung’s argumentation framework, in which an argument system consists of a set of arguments and a binary relation between arguments representing the notion of a conflict. The semantics given by Dung define (with respect to each argument system) acceptable sets of arguments called extensions. For his so-called stable semantics, Dung also gives an alternative definition in terms of an equation that a set satisfies if and only if that set is a stable extension. However, neither the original definition nor the equation reflect the fact that the stable semantics (similarly to all of Dung’s semantics) rely upon the notion of an admissible set. Moreover, none of Dung’s other semantics have been characterized by such an equation. Our first goal is to provide such characterizations for the other semantics: We capture Dung’s semantics by means of equations that a set satisfies if and only if it is an extension under the semantics at hand. Not only do we give such equations, but we also take care of providing them as a unified characterization expressing the common grounds of Dung’s semantics. Beyond Dung’s semantics, we are interested in semantics (within Dung’s argumentation framework) relying upon the notion of an admissible set. Our second goal is to show that many of those semantics are captured like Dung’s, using the same unified characterization.

NMR Workshop 2004 Conference Paper

Checking the acceptability of a set of arguments

• Philippe Besnard
• Sylvie Doutre

Considering Dung’s argumentation framework and semantics, we are interested in the problem which consists in deciding whether a set of arguments is acceptable under a given semantics. We look at three approaches. The first one consists in testing whether the set satisfies an equation; In particular, we look at the equations presented in (Dung 1995; Besnard & Doutre 2004). The second approach consists in testing whether the set is a model of a propositional formula and the third one consists in testing the satisfiability of a propositional formula.

NMR Workshop 2002 Conference Paper

Optimality theory through default logic

• Philippe Besnard
• Robert E. Mercer
• Torsten Schaub

Optimality Theory is an approach to linguistic problems which is based on rules with exceptions, resorting to a ranking among rules to resolve conflicts arising from competing rules. In such a way, dealing with linguistic problems amounts to applying rules with exceptions: That is reasoning. A related issue is then about a formalization of the logic at work. An immediate candidate is Default Logic which is dedicated to reasoning from rules with exceptions. Moreover, there are versions of default logic with priorities. We show that Default Logic is well-suited as a specification language capturing Optimality Theory and suggests that implementations of default logic can be applied to run experiments with grammatical interaction in the sense of Optimality Theory and beyond.

JELIA Conference 2002 Conference Paper

Paraconsistent Reasoning via Quantified Boolean Formulas, I: Axiomatising Signed Systems

• Philippe Besnard
• Torsten Schaub
• Hans Tompits
• Stefan Woltran

Signed systems were introduced as a general, syntax-independent framework for paraconsistent reasoning, that is, non-trivialised reasoning from inconsistent information. In this paper, we show how the family of corresponding paraconsistent consequence relations can be axiomatised by means of quantified Boolean formulas. This approach has several benefits. First, it furnishes an axiomatic specification of paraconsistent reasoning within the framework of signed systems. Second, this axiomatisation allows us to identify upper bounds for the complexity of the different signed consequence relations. We strengthen these upper bounds by providing strict complexity results for the considered reasoning tasks. Finally, we obtain an implementation of different forms of paraconsistent reasoning by appeal to the existing system QUIP.

AAAI Conference 2000 Conference Paper

Towards a Logic-Based Theory of Argumentation

• Philippe Besnard

There are a number of frameworks for modelling argumentation in logic. They incorporate formal representation of individual arguments and techniques for comparing conflicting arguments. In these frameworks, if there are a number of arguments for and against a particular conclusion, an aggregation function determines whether the conclusion is taken to hold. We propose a generalization of these frameworks. In particular, this new framework makes it possible to define aggregation functions that are sensitive to the number of arguments for or against(in most other frameworks, aggregation functions just consider the existence of arguments for and against). In this paper, we explore this framework (based on classicallogic) in which an argument is a pair where the first item in the pair is a minimal consistent set of formulae that proves the second item (which is a formula).

IJCAI Conference 1997 Conference Paper

Circumscribing Inconsistency

• Philippe Besnard
• lorsten H. Schaub

We present a new logical approach to reasoning from inconsistent information. The idea is to restore modelhood of inconsistent formulas by providing a third truth-value tolerating inconsistency. The novelty of our approach stems first from the restriction of entailment to three-valued models as similar as possible to two-valued models and second from an implication connective providing a notion of restricted monotonicity. After developing the semantics, we present a corresponding proof system that relies on a circumscription schema furnishing the syntactic counterpart of model minimization.

ECAI Conference 1996 Conference Paper

A Modal Logic with Context-Dependent Inference for Non-Monotonic Reasoning

• Philippe Besnard
• Yao-Hua Tan

UAI Conference 1994 Conference Paper

Possibility and Necessity Functions over Non-Classical Logics

• Philippe Besnard
• Jérôme Lang

We propose an integration of possibility theory into non-classical logics. We obtain many formal results that generalize the case where possibility and necessity functions are based on classical logic. We show how useful such an approach is by applying it to reasoning under uncertain and inconsistent information.

AAAI Conference 1993 Conference Paper

A Context-based Framework for Default Logics

• Philippe Besnard

We present a new context-based approach to default logic, called contextual default logic. The approach”extends the notion of a default rule and supplies each extension with a context. Contextual default logic allows for embedding all existing variants of default logic along with more traditional approaches like the closed world assumption. A key advantage of contextual default logic is that it provides a syntactical instrument for comparing existing default logics in a unified setting. In particular, it reveals that existing default logics mainly differ in the way they deal with an explicit or implicit underlying context. Thus, the primary purpose of this work is to integrate the different variants of default logic in a more general but uniform system, which combines the expressiveness of the various default logics. The basic idea is twofold. First, we supply each default extension (ie. a set of default conclusions) with an underlying context. Second, we extend the notion of a default rule in order to allow for a variety of different application conditions which arise naturally from the distinction between the initial set of facts, the default extension at hand, and its context.

ECAI Conference 1992 Conference Paper

Explanatory Diagnoses and their Computation by Circumscription

• Philippe Besnard
• Marie-Odile Cordier

AIJ Journal 1989 Journal Article

The importance of open and recursive circumscription

• Philippe Besnard
• Yves Moinard
• Robert E. Mercer

Circumscription is known to result in an inconsistency when applied to certain consistent theories. To counter this problem, closed nonrecursive circumscription, a restricted form of circumscription that has been proved not to affect the consistency of the theory over which circumscription is applied, has been proposed. We show that closed nonrecursive circumscription involves an excessive weakening of standard circumscription by establishing that closed nonrecursive circumscription is incomplete for some crucial theories over which standard circumscription is consistent and complete. First, we prove that closed circumscription cannot yield the desired uniqueness formula for the simplest of existential theories. Second, we prove that nonrecursive circumscription fails to be as strong as predicate completion for Horn clause theories. Third, we prove that the natural way to strengthen circumscription, that is, adding more variable predicates, may weaken nonrecursive circumscription.

ECAI Conference 1988 Conference Paper

A Formula Circumscriptively both Valid and Unprovable

• Philippe Besnard
• Jean Houdebine
• Raymond Rolland

AAAI Conference 1983 Conference Paper

A Theorem-Prover for a Decidable Subset of Default Logic

• Philippe Besnard

Non-monotonic logic is an attempt to take into account such notions as incomplete knowledge and theory evolution. However the decidable theorem-prover issue has been so far unexplored. We propose such a theorem-prover for default logic with a restriction on the first-order formulae it deals with. This theorem-prover is based on the generalisation of a resolution technique named saturation, which was initially designed to test the consistency of a set of first-order formulae. We have proved that our algorithm is complete and that it always terminates for the selected subset of first-order formulae.