2017/11/28 by Stéphane Rivaud, Rivaud, Stephane, François Pachet +1 · 1 citation
Computer Science · #Algorithms and Data Compression #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Natural Language Processing Techniques #Topic Modeling
paper · pdf · doi:10.48550/arxiv.1711.10436
openalex publication_date 2017/11/28 · openalex created_date 2017/12/04 · openalex updated_date 2026/07/28
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.