Sampling Markov Models under Constraints: Complexity Results for Binary Equalities and Grammar Membership

Stephane Rivaud, François Pachet

We aim at enforcing hard constraints to impose a global structure on sequences generated from Markov models. In this report, we study the complexity of sampling Markov sequences un…