Seminar Collective Singleton-based Consistency for Qualitative Constraint Networks: Theory and Practice
Michael Sioutis (Örebro University)
Partial singleton weak path-consistency is essential for tackling challenging fundamental reasoning problems
associated with qualitative constraints networks. Briefly put, partial singleton weak path-consistency
ensures that each base relation of each of the constraints of a qualitative constraint network can define a
singleton relation in its corresponding partially weakly path-consistent subnetwork. In this talk, we propose
a stronger local consistency that couples partial singleton weak path-consistency with the idea of collectively
deleting certain unfeasible base relations by exploiting singleton checks. We then propose an algorithm for
enforcing this new consistency and a lazy variant of that algorithm for approximating the new consistency, both of which outperform the respective algorithm for enforcing partial singleton weak path-consistency in a given qualitative constraint network . With respect to the lazy algorithmic variant in particular, we show that it runs up to 5 times faster than our original exhaustive algorithm whilst exhibiting very similar pruning capability.
We formally prove certain properties of our new local consistency and our algorithms, and motivate their usefulness through demonstrative examples and a thorough experimental evaluation with random qualitative constraint networks of the Interval Algebra and the Region Connection Calculus from the phase transition region of two different generation models. Finally, we provide evidence of the crucial role of the new consistency in tackling the minimal labeling problem of a qualitative constraint network, which is the problem of finding the strongest implied constraints of that network.
PhD defense of Valentin Montmirail - Practical resolution of satisfiability testing for modal logics
September 17th, 2018, 10 AM, salle des thèses de la faculté Jean Perrin
In this thesis, we explored the idea to use modern SAT technology that has seen considerable progress over the last years for solving various kinds of Modal Logics.
We tackled the problem from various directions. For the NP-complete variants of Modal Logics it is a natural choice to encode them to SAT and use a SAT solver to decide them. In order to get an efficient Modal Logic solver, it requires several optimisations because otherwise the formulas will get too huge.
In the next step, we asked the question how to obtain smallest models when the considered formula is satisfiable and we came up with several solutions but we did not stop our work with the NP-complete logics.
For going beyond NP, we suggested a novel approach inspired by the successful CEGAR techniques that we named RECAR for Recursive Explore and Check Abstraction Refinement. We instantiated the framework RECAR within the solver MoSaiC and we demonstrated how, with efficient over- and under- abstractions, a SAT-based approach can solve PSPACE modal logics.
September 13th, 2018, 2 PM, salle des thèses de la faculté Jean Perrin
In this thesis, We adress the well-known clustering and association rules mining problems. Our first
contribution introduces a new clustering framework, where complex objects are described by proposi-
tional formulas. First, we extend the two well-known k-means and hierarchical agglomerative clustering
techniques to deal with these complex objects. Second, we introduce a new divisive algorithm for clus-
tering objects represented explicitly by sets of models. Finally, we propose a propositional satisfiability
based encoding of the problem of clustering propositional formulas without the need for an explicit
representation of their models. In a second contribution, we propose a new propositional satisfiability
based approach to mine association rules in a single step. The task is modeled as a propositional for-
mula whose models correspond to the rules to be mined. To highlight the flexibility of our proposed
framework, we also address other variants, namely the closed, minimal non-redundant, most general and
indirect association rules mining tasks. Experiments on many datasets show that on the majority of the
considered association rules mining tasks, our declarative approach achieves better performance than the
state-of-the-art specialized techniques.
Keywords: Data mining, Clustering, Association rules, Propositional satisfiability.
This year, 4 papers et 3 extended abstracts co-authored by CRIL members will be presented at KR 2018.
Those four papers will be presented at the main conference:
Leila Amgoud, Elise Bonzon, Jérôme Delobelle, Dragan Doder, Sébastien Konieczny and Nicolas Maudet Gradual semantics accounting for similarity between arguments
Elise Bonzon, Jérôme Delobelle, Sébastien Konieczny and Nicolas Maudet Combining Extension-based semantics and Ranking-based semantics for Abstract Argumentation
Nicolas Schwind, Sébastien Konieczny and Pierre Marquis On Belief Promotion
Giovanni Casini, Thomas Meyer, Eduardo Fermé and Ivan Varzinczak A Semantic Perspective on Belief Change in a Preferential Non-Monotonic Framework
The following posters will be present as well:
Sébastien Konieczny, Pierre Marquis and Srdjan Vesic New inference relations from maximal consistent subsets
Jean Marie Lagniez, Daniel Le Berre, Tiago de Lima and Valentin Montmirail Space-Awareness in a SAT-Based Approach For PSPACE Modal Logics
Nicolas Schwind, Tenda Okimoto, Katsumi Inoue, Katsutoshi Hirayama, Jean-Marie Lagniez and Pierre Marquis Probabilistic Coalition Structure Generation
Ivan Varzinczak will receive Louis Couturat’s logic prize during the
next edition of the UNILOG’18 conference, on June 24, for his article
“A note on a description logic of concept and role typicality”.