Author name cluster

Anicet Bart

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

2 author rows

TCS Journal 2018 Journal Article

Reachability in parametric Interval Markov Chains using constraints

Anicet Bart
Benoît Delahaye
Paulin Fournier
Didier Lime
Éric Monfroy
Charlotte Truchet

Parametric Interval Markov Chains (pIMCs) are a specification formalism that extend Markov Chains (MCs) and Interval Markov Chains (IMCs) by taking into account imprecision in the transition probability values: transitions in pIMCs are labelled with parametric intervals of probabilities. In this work, we study the difference between pIMCs and other Markov Chain abstractions models and investigate three semantics for IMCs: once-and-for-all, interval-Markov-decision-process, and at-every-step. In particular, we prove that all three semantics agree on the maximal/minimal reachability probabilities of a given IMC. We then investigate solutions to several parameter synthesis problems in the context of pIMCs – consistency, qualitative reachability and quantitative reachability – that rely on constraint encodings. Finally, we propose a prototype implementation of our constraint encodings with promising results.

Details DOI

ECAI Conference 2016 Conference Paper

An Improved CNF Encoding Scheme for Probabilistic Inference

Anicet Bart
Frédéric Koriche
Jean-Marie Lagniez
Pierre Marquis

We present and evaluate a new CNF encoding scheme for reducing probabilistic inference from a graphical model to weighted model counting. This new encoding scheme elaborates on the CNF encoding scheme ENC4 introduced by Chavira and Darwiche, and improves it by taking advantage of log encodings of the elementary variable/value assignments and of the implicit encoding of the most frequent probability value per conditional probability table. From the theory side, we show that our encoding scheme is faithful, and that for each input network, the CNF formula it leads to contains less variables and less clauses than the CNF formula obtained using ENC4. From the practical side, we show that the C2D compiler empowered by our encoding scheme performs in many cases significantly better than when ENC4 is used, or when the state-of-the-art ACE compiler is considered instead.

Details

ECAI Conference 2014 Conference Paper

Symmetry-Driven Decision Diagrams for Knowledge Compilation

Anicet Bart
Frédéric Koriche
Jean-Marie Lagniez
Pierre Marquis

In this paper, symmetries are exploited for achieving significant space savings in a knowledge compilation perspective. More precisely, the languages FBDD and DDG of decision diagrams are extended to the languages Sym-FBDDX, Yand Sym-DDGX, Yof symmetry-driven decision diagrams, where X is a set of "symmetry-free" variables and Y is a set of "top" variables. Both the time efficiency and the space efficiency of Sym-FBDDX, Yand Sym-DDGX, Yare analyzed, in order to put those languages in the knowledge compilation map for propositional representations. It turns out that each of Sym-FBDDX, Yand Sym-DDGX, Ysatisfies CT (the model counting query). We prove that no propositional language over a set X∪ Y of variables, satisfying both CO (the consistency query) and CD (the conditioning transformation), is at least as succinct as any of Sym-FBDDX, Yand Sym-DDGX, Yunless the polynomial hierarchy collapses. The price to be paid is that only a restricted form of conditioning and a restricted form of forgetting are offered by Sym-FBDDX, Yand Sym-DDGX, Y. Nevertheless, this proves sufficient for a number of applications, including configuration and planning. We describe a compiler targeting Sym-FBDDX, Yand Sym-DDGX, Yand give some experimental results on planning domains, highlighting the practical significance of these languages.

Details