AI RESEARCH
Exact Regular-Constrained Variable-Order Markov Generation via Sparse Context-State Belief Propagation
arXiv CS.AI
•
ArXi:2605.07839v1 Announce Type: new Variable-order Marko models generate sequences over a finite alphabet by conditioning each symbol on the longest available suffix of the generated history. Regular constraints, by contrast, describe finite-horizon control requirements by an automaton: fixed positions, forced endings, metrical patterns, and forbidden copied fragments are all special cases. Existing exact methods already handle regular constraints with belief propagation for first-order Marko chains.