  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 under two classes of constraints: Binary
Equalities and Grammar Membership Constraints. First, we give a sketch of proof
of #P-completeness for binary equalities and identify three sub-cases where
sampling is polynomial. We then give a proof of #P-completeness for grammar
membership, and identify two cases where sampling is tractable. The first
polynomial sub-case where sampling is tractable is when the grammar is proven
to be unambiguous. Our main contribution is to identify a new, broader class of
grammars for which sampling is tractable. We provide algorithm along with time
and space complexity for all the polynomial cases we have identified.
