432 citations
Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.
- Centre National de la Recherche ScientifiqueFR17 papers
- Université d'ArtoisFR11 papers
- Centre de Recherche en InformatiqueFR4 papers
- Centre de Recherche en Informatique, Signal et Automatique de LilleFR4 papers
- Institut national de recherche en sciences et technologies du numériqueFR3 papers
- Laboratoire Traitement et Communication de l’InformationFR3 papers
- LamsadeFR3 papers
- Laboratoire d'Automatique, de Mécanique et d'Informatique Industrielles et HumainesFR2 papers
- Télécom ParisFR2 papers
- Université de LilleFR2 papers
- Université Paris Dauphine-PSLFR2 papers
- University of BayreuthDE2 papers
29 papers
ASTERYX : A model-Agnostic SaT-basEd appRoach for sYmbolic and score-based eXplanations
Ryma Boumazouza, Fahima Cheikh-Alili, Bertrand Mazure +1
The ever increasing complexity of machine learning techniques used more and more in practice, gives rise to the need to explain the predictions and decisions of these models, often…
A Symbolic Approach for Counterfactual Explanations
Ryma Boumazouza, Fahima Cheikh-Alili, Bertrand Mazure +1
In this paper titled A Symbolic Approach for Counterfactual Explanations we propose a novel symbolic approach to provide counterfactual explanations for a classifier predictions. C…
Rectifying Mono-Label Boolean Classifiers
Sylvie Coste-Marquis, Pierre Marquis
We elaborate on the notion of rectification of a Boolean classifier . Given and some background knowledge , postulates characterizing the way must be changed into a n…
Generalized binary utility functions and fair allocations
Franklin Camacho, Rigoberto Fonseca-Delgado, Ramón Pino Pérez +1
The problem of finding envy-free allocations of indivisible goods can not always be solved; therefore, it is common to study some relaxations such as envy-free up to one good (EF1)…
Constant-Delay Enumeration for Nondeterministic Document Spanners
Antoine Amarilli, Pierre Bourhis, Stefan Mengel +1
We consider the information extraction framework known as document spanners, and study the problem of efficiently computing the results of the extraction from an input document, wh…
Graph Width Measures for CNF-Encodings with Auxiliary Variables
Stefan Mengel, Romain Wallon
We consider bounded width CNF-formulas where the width is measured by popular graph width measures on graphs associated to CNF-formulas. Such restricted graph classes, in particula…
Enumeration on Trees with Tractable Combined Complexity and Efficient Updates
Antoine Amarilli, Pierre Bourhis, Stefan Mengel +1
We give an algorithm to enumerate the results on trees of monadic second-order (MSO) queries represented by nondeterministic tree automata. After linear time preprocessing (in the…
Nopol: Automatic Repair of Conditional Statement Bugs in Java Programs
Jifeng Xuan, Matias Martinez, Favio Demarco +5
We propose NOPOL, an approach to automatic repair of buggy conditional statements (i.e., if-then-else statements). This approach takes a buggy program as well as a test suite as in…
On Rational Entailment for Propositional Typicality Logic
Richard Booth, Giovanni Casini, Thomas Meyer +1
Propositional Typicality Logic (PTL) is a recently proposed logic, obtained by enriching classical propositional logic with a typicality operator capturing the most typical (alias…
Knowledge Compilation, Width and Quantification
Florent Capelli, Stefan Mengel
We generalize many results concerning the tractability of SAT and #SAT on bounded treewidth CNF-formula in the context of Quantified Boolean Formulas (QBF). To this end, we start b…
QBF as an Alternative to Courcelle's Theorem
Michael Lampis, Stefan Mengel, Valia Mitsou
We propose reductions to quantified Boolean formulas (QBF) as a new approach to showing fixed-parameter linear algorithms for problems parameterized by treewidth. We demonstrate th…
Enumeration on Trees under Relabelings
Antoine Amarilli, Pierre Bourhis, Stefan Mengel
We study how to evaluate MSO queries with free variables on trees, within the framework of enumeration algorithms. Previous work has shown how to enumerate answers with linear-time…
A Circuit-Based Approach to Efficient Enumeration
Antoine Amarilli, Pierre Bourhis, Louis Jachiet +1
We study the problem of enumerating the satisfying valuations of a circuit while bounding the delay, i.e., the time needed to compute each successive valuation. We focus on the cla…
XCSP3: An Integrated Format for Benchmarking Combinatorial Constrained Problems
Frederic Boussemart, Christophe Lecoutre, Gilles Audemard +1
We propose a major revision of the format XCSP 2.1, called XCSP3, to build integrated representations of combinatorial constrained problems. This new format is able to deal with mo…
Parameterized Compilation Lower Bounds for Restricted CNF-formulas
Stefan Mengel
We show unconditional parameterized lower bounds in the area of knowledge compilation, more specifically on the size of circuits in decomposable negation normal form (DNNF) that en…
Compact-Table: Efficiently Filtering Table Constraints with Reversible Sparse Bit-Sets
Jordan Demeulenaere, Renaud Hartert, Christophe Lecoutre +4
In this paper, we describe Compact-Table (CT), a bitwise algorithm to enforce Generalized Arc Consistency (GAC) on table con- straints. Although this algorithm is the default propa…
Agenda Separability in Judgment Aggregation
Jérôme Lang, Marija Slavkovik, Srdjan Vesic
One of the better studied properties for operators in judgment aggregation is independence, which essentially dictates that the collective judgment on one issue should not depend o…
A Comparative Study of Ranking-based Semantics for Abstract Argumentation
Elise Bonzon, Jérôme Delobelle, Sébastien Konieczny +1
Argumentation is a process of evaluating and comparing a set of arguments. A way to compare them consists in using a ranking-based semantics which rank-order arguments from the mos…
Counting Answers to Existential Positive Queries: A Complexity Classification
Hubie Chen, Stefan Mengel
Existential positive formulas form a fragment of first-order logic that includes and is semantically equivalent to unions of conjunctive queries, one of the most important and well…
Minimal Distance of Propositional Models
Mike Behrisch, Miki Hermann, Stefan Mengel +1
We investigate the complexity of three optimization problems in Boolean propositional logic related to information theory: Given a conjunctive formula over a set of relations, find…
A partial taxonomy of judgment aggregation rules, and their properties
Jerôme Lang, Gabriella Pigozzi, Marija Slavkovik +2
The literature on judgment aggregation is moving from studying impossibility results regarding aggregation rules towards studying specific judgment aggregation rules. Here we give…
The Logic of Counting Query Answers
Hubie Chen, Stefan Mengel
We consider the problem of counting the number of answers to a first-order formula on a finite structure. We present and study an extension of first-order logic in which algorithms…
Identifying the Class of Maxi-Consistent Operators in Argumentation
Srdjan Vesic
Dung's abstract argumentation theory can be seen as a general framework for non-monotonic reasoning. An important question is then: what is the class of logics that can be subsumed…
Second-Order Consistencies
Christophe Lecoutre, Stephane Cardon, Julien Vion
In this paper, we propose a comprehensive study of second-order consistencies (i.e., consistencies identifying inconsistent pairs of values) for constraint satisfaction. We build a…