Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Sampling Markov Models under Constraints: Complexity Results for Binary
  Equalities and Grammar Membership   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.

15
The categories of this paper are: nucl-ex
12
The categories of this paper are: nucl-th
35
The categories of this paper are: mtrl-th
30
The categories of this paper are: q-alg
31
The categories of this paper are: ao-sci
28
The categories of this paper are: alg-geom
22
The categories of this paper are: chao-dyn
7
The categories of this paper are: hep-th
17
The categories of this paper are: q-fin
11
The categories of this paper are: hep-lat
6
The categories of this paper are: astro-ph
29
The categories of this paper are: funct-an
9
The categories of this paper are: nlin
8
The categories of this paper are: hep-ex
36
The categories of this paper are: cmp-lg
33
The categories of this paper are: plasm-ph