Éric Grégoire

IJCAI Conference 2018 Conference Paper

Boosting MCSes Enumeration

• Éric Grégoire
• Yacine Izza
• Jean-Marie Lagniez

The enumeration of all Maximal Satisfiable Subsets (MSSes) or all Minimal Correction Subsets (MCSes) of an unsatisfiable CNF Boolean formula is a useful and sometimes necessary step for solving a variety of important A. I. issues. Although the number of different MCSes of a CNF Boolean formula is exponential in the worst case, it remains low in many practical situations; this makes the tentative enumeration possibly successful in these latter cases. In the paper, a technique is introduced that boosts the currently most efficient practical approaches to enumerate MCSes. It implements a model rotation paradigm that allows the set of MCSes to be computed in an heuristically efficient way.

ECAI Conference 2016 Conference Paper

A Computational Approach to Consensus-Finding

• Éric Grégoire
• Jean-Marie Lagniez

Consensus-finding plays a ubiquitous role in A. I. In this paper, a consensus among agents is defined as a non-contradictory fragment of all the information conveyed by the agents such that this fragment does not logically conflict with any of the agents. This concept is investigated in modal logic S5 in order to meet representation needs that are put in light by this concept of consensus itself. Interestingly, an optimization-based approach to compute maximal consensuses is developed and shown experimentally efficient very often for both the standard Boolean and S5 frameworks.

AAAI Conference 2016 Conference Paper

On the Extraction of One Maximal Information Subset That Does Not Conflict with Multiple Contexts

• Éric Grégoire
• Yacine Izza
• Jean-Marie Lagniez

The efficient extraction of one maximal information subset that does not conflict with multiple contexts or additional information sources is a key basic issue in many A. I. domains, especially when these contexts or sources can be mutually conflicting. In this paper, this question is addressed from a computational point of view in clausal Boolean logic. A new approach is introduced that experimentally outperforms the currently most efficient technique.

LPAR Conference 2015 Conference Paper

On Anti-subsumptive Knowledge Enforcement

• Éric Grégoire
• Jean-Marie Lagniez

Abstract The anti-subsumptive enforcement of a clause \(\delta \) in a set of clauses \(\varDelta \) consists in extracting one cardinality-maximal satisfiable subset \(\varDelta '\) of \(\varDelta \cup \{\delta \}\) that contains \(\delta \) but that does not strictly subsume \(\delta \). In this paper, the computational issues of this problem are investigated in the Boolean framework. Especially, the minimal change policy that requires a minimal number of clauses to be dropped from \(\varDelta \) can lead to an exponential computational blow-up. Indeed, a direct and natural approach to anti-subsumptive enforcement requires the computation of all inclusion-maximal subsets of \(\varDelta \cup \{\delta \}\) that, at the same time, contain \(\delta \) and are satisfiable with \(\lnot \delta _j\) where \(\delta _j\) is some strict sub-clause of \(\delta \). On the contrary, we propose a method that avoids the computation of this possibly exponential number of subsets of clauses. Interestingly, it requires only one single call to a Partial-Max-SAT procedure and appears tractable in many realistic situations, even for very large \(\varDelta \). Moreover, the approach is easily extended to take into account a preference pre-ordering between formulas and lay the foundations for the practical enumeration of all optimal solutions to the problem of making \(\delta \) subsumption-free in \(\varDelta \) under a minimal change policy.

ECAI Conference 2014 Conference Paper

Enforcing Solutions in Constraint Networks

• Éric Grégoire
• Jean-Marie Lagniez
• Bertrand Mazure

A method is proposed to enforce specific solutions in constraint networks. Contrary to previous approaches, it yields a set of constraints to be dropped whose cardinality is minimal.

IJCAI Conference 2013 Conference Paper

Preserving Partial Solutions while Relaxing Constraint Networks

• Éric Grégoire
• Jean-Marie Lagniez
• Bertrand Mazure

An extension of the CSP optimization framework tailored to identify fair solutions to instances involving multiple optimization functions is studied. Two settings are considered, based on the maximization of the minimum value over all the given functions (MAX-MIN approach) and on its lexicographical refinement where, over all solutions maximizing the minimum value, those maximizing the second minimum value are preferred, and so on, until all functions are considered (LEXMAX-MIN approach). For both settings, the complexity of computing an optimal solution is analyzed and the tractability frontier is charted for acyclic instances, w. r. t. the number and the domains of the functions to be optimized. Larger islands of tractability are then identified via a novel structural approach, based on a notion of guard that is designed to deal with the interactions among constraint scopes and optimization functions.

IJCAI Conference 2013 Conference Paper

Preserving Partial Solutions while Relaxing Constraint Networks

• Éric Grégoire
• Jean-Marie Lagniez
• Bertrand Mazure

This paper is about transforming constraint networks to accommodate additional constraints in specific ways. The focus is on two intertwined issues. First, we investigate how partial solutions to an initial network can be preserved from the potential impact of additional constraints. Second, we study how more permissive constraints, which are intended to enlarge the set of solutions, can be accommodated in a constraint network. These two problems are studied in the general case and the light is shed on their relationship. A case study is then investigated where a more permissive additional constraint is taken into account through a form of network relaxation, while some previous partial solutions are preserved at the same time.

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.

ECAI Conference 2006 Conference Paper

Extracting MUSes

• Éric Grégoire
• Bertrand Mazure
• Cédric Piette

Minimally unsatisfiable subformulas (in short, MUSes) represent the smallest explanations for the inconsistency of SAT instances in terms of the number of involved clauses. Extracting MUSes can thus prove valuable because it circumscribes the sources of contradiction in an instance. In this paper, a new heuristic-based approach to approximate or compute MUSes is presented. It is shown that it often outperforms current competing ones.

SAT Conference 2004 Conference Paper

Automatic Extraction of Functional Dependencies

• Éric Grégoire
• Richard Ostrowski
• Bertrand Mazure
• Lakhdar Saïs

In this paper, a new polynomial time technique for extracting functional dependencies in Boolean formulas is proposed. It makes an original use of the well-known Boolean constraint propagation technique (BCP) in a new preprocessing approach that extracts more hidden Boolean functions and dependent variables than previously published approaches on many classes of instances.

ECAI Conference 1990 Conference Paper

Skeptical Inheritance Can Be More Expressive

• Éric Grégoire