On the Complexity of Language Membership for Probabilistic Words

We give preliminaries and formally introduce the problem in Section 2. We then give some first results in Section 3, which are essentially generalizations of the unweighted counting results of [13]. Namely, we show that probabilistic membership is tractable for uCFLs (even in combined complexity), because we can count the total probability of derivation trees with a variant of the Cocke-Younger-Kasami (CYK) algorithm. However, we show that the task can be intractable (namely, #P-hard) for some inherently ambiguous CFLs: we give a simple example of such a CFL, and generalize and extend techniques from [13] to show hardness even in the case of the union of two unambiguous linear CFLs, i.e., the right-hand-side of each production rule contains at most one nonterminal.

The next section (Section 4) shows that there are CFLs that are inherently ambiguous but for which probabilistic membership is nevertheless tractable. These include, for instance, all bounded CFLs [38]: these are known to coincide with the class of polyslender CFLs [50], i.e., those CFLs containing only polynomially many words of length $n$. Thus, we can tractably solve probabilistic membership for bounded CFLs $L$ (even in combined complexity) by simply listing all words of length $n$ of $L$ explicitly and summing their probabilities. Bounded CFLs are incomparable to uCFLs, as there are non-bounded uCFLs (e.g., palindromes) and also inherently ambiguous bounded CFLs (e.g., $\{a^n{b}^m{c}^m\mid n,m\in \mathbb{N}\}\cup \{a^n{b}^n{c}^m\mid n,m\in \mathbb{N}\}$). We give a unifying explanation to the tractability of uCFLs and bounded CFLs by introducing the class of languages $L$ that are poly-slicewise-unambiguous in the sense that, given a length $n\in \mathbb{N}$, we can compute in polynomial time in $n$ a uCFG $G$ recognizing the words of length $n$ of $L$, i.e., recognizing a language $L^{\prime }$ with $L\cap {\mathrm{\Sigma }}^n=L^{\prime }\cap {\mathrm{\Sigma }}^n$. For such languages, probabilistic membership is tractable simply by reducing to uCFGs. We last introduce a formalism of unambiguous polynomial-time counter automata which are poly-slicewise-unambiguous: these recognize in particular some CFLs that are neither bounded nor unambiguous. We show that probabilistic membership is tractable for such automata, but that it can be #P-hard for some CFLs accepted by very restricted nondeterministic counter automata.

The natural question is then whether poly-slicewise-unambiguity is the unifying explanation for the tractability of probabilistic membership for CFLs. We answer in the negative in Section 5 by introducing a framework of tractable circuits from the field of knowledge compilation [29], inspired by database theory [4]. Intuitively, tractable circuits are circuits that give a factorized representation of a set of partial functions (intuitively corresponding to outcomes of a probabilistic word) using some tractable operators: Cartesian product (called decomposable AND in the setting of Boolean knowledge compilation circuit classes), and disjoint union (called deterministic OR in the Boolean setting). These circuits are a multivalued analogue to so-called sd-DNNF circuits [29]. The choice of operators ensures that we can compute in linear time (up to the cost of arithmetic operations) the total probability of the assignments captured by a tractable circuit. We show that these circuits can be used to recapture the tractability of all poly-slicewise-unambiguous languages. What is more, we show that there are CFLs that are not poly-slicewise-unambiguous but admit tractable circuits: we use for this the language very recently studied in [57] whose length-$n$ slices were recently shown [68] not to admit uCFLs of polynomial size in $n$.

We then continue our study of tractable circuits in Section 6 and extend them by adding a complementation operator (corresponding to negation in the Boolean sense). This follows the observation from probabilistic databases [69] that counting the satisfying valuations of d-DNNF circuits can be tractably achieved even in the presence of negation. Further, negation is very useful to encode some inclusion-exclusion-based counting arguments (through the full extent to which this is true is not yet understood [7]). Tractable circuits with negation imply the obvious fact that probabilistic membership is tractable for the complements of all tractable languages studied so far (which are generally not CFLs). We use those circuits to further show tractability for some other languages: we introduce the technique with the language of primitive words (whose context-freeness is a long-standing open problem [51]), and further apply it to the language of the concatenation of palindromes, a non-linear CFL of unbounded degree of ambiguity [26]. Our tractability result for probabilistic membership for this language generalizes an earlier result on unweighted counting [56].

We then conclude the paper in Section 7 and survey directions for future work; we also mention there the undecidability of finding out, given a CFG, whether it admits PTIME probabilistic membership. For reasons of space, most proofs are deferred to the full version of the article [6].

We fix a nonempty finite set of symbols $\mathrm{\Sigma }$ called an alphabet and whose elements are called letters. We let ${\mathrm{\Sigma }}^{\ast }$ be the set of all words over $\mathrm{\Sigma }$, which are finite sequences of letters of $\mathrm{\Sigma }$. We write $ϵ$ for the empty word. The mirror image of $w=a_1\mathrm{\cdots }{a}_n\in {\mathrm{\Sigma }}^{\ast }$ is $w^R≔a_n\mathrm{\cdots }{a}_1$; we call $w$ a palindrome if $w=w^R$. A language over $\mathrm{\Sigma }$ is a subset of ${\mathrm{\Sigma }}^{\ast }$. We omit the definition of standard language operations, e.g., concatenation, Kleene star, etc.

A context-free grammar (CFG) over $\mathrm{\Sigma }$ is a tuple $\mathrm{\Gamma }=(N,S,P)$ where $N$ is a nonempty finite set of symbols called nonterminals, $S\in N$ is the axiom, and $P\subseteq N\times {(\mathrm{\Sigma }\cup N)}^{\ast }$ is a set of production rules, with each production $(U,\alpha )\in P$ written as $U\to \alpha$. We call the letters of $\mathrm{\Sigma }$ terminals, and write them in lowercase. We say that $\mathrm{\Gamma }$ is a linear CFG if the right-hand-side of every production contains at most one nonterminal. The size of $\mathrm{\Gamma }$, written $|\mathrm{\Gamma }|$, is simply $|N|$ plus the total size of the production rules.

We omit the standard formal definitions of derivations and parse trees for CFGs. A CFG $\mathrm{\Gamma }$ recognizes the language $\text{L}(\mathrm{\Gamma })$ formed of the words $w\in {\mathrm{\Sigma }}^{\ast }$ on which $\mathrm{\Gamma }$ admits a parse tree. We say that $\mathrm{\Gamma }$ is unambiguous (or a uCFG) if on every word it admits at most one parse tree; otherwise $\mathrm{\Gamma }$ is ambiguous. We call $\mathrm{\Gamma }$ $k$-ambiguous for $k\in \mathbb{N}$ if on every word it admits at most $k$ parse trees. A language $L$ is a context-free language (CFL) if there is a CFG $\mathrm{\Gamma }$ with $\text{L}(\mathrm{\Gamma })=L$. It is an unambiguous CFL (uCFL) if $\mathrm{\Gamma }$ can be taken to be a uCFG (but note that there may also be ambiguous CFGs recognizing $L$). We define unambiguous linear CFLs and $k$-ambiguous linear CFLs in the expected way. A CFL $L$ is called inherently ambiguous if it is not a uCFL, meaning that every CFG recognizing $L$ is ambiguous.

We now define the notion of probabilistic words on an alphabet $\mathrm{\Sigma }$:

Concatenating probabilistic words means concatenating the tuples: this is associative and the neutral element is the empty probabilistic word (the empty tuple). Note that probabilistic words indeed define probability distributions on ${\mathrm{\Sigma }}^{\ast }$, i.e., the probabilities sum to 1.

We now define the problem that we study, called probabilistic membership. Given a language $L$ on an alphabet $\mathrm{\Sigma }$, and a probabilistic word $p$, we abuse notation and write $p(L)$ to mean the probability that a random word of ${\mathrm{\Sigma }}^{\ast }$ drawn according to $p$ will belong to the language $L$. Formally, we have: $p(L)≔{\sum }_{w\in L}p(w)$. The probabilistic membership problem then asks: given a language $L$ and a probabilistic word $p$, compute $p(L)$. Here, probabilities of the input word are given as rational numbers $\frac{r}{q}$ for $(r,q)\in \mathbb{N}\times (\mathbb{N}\setminus \{0\})$, with $r$ and $q$ encoded in binary. We focus on the data complexity perspective, where the target $L$ is fixed: this defines a problem $\text{\#pM}(L)$, with complexity measured as a function of $p$. However, some of our tractability results hold in combined complexity, where the input is $p$ along with a CFG $\mathrm{\Gamma }$ with $\text{L}(\mathrm{\Gamma })=L$. We illustrate special cases of probabilistic membership below:

• $\mathrm{■}$

  For each $u\in {\mathrm{\Sigma }}^{\ast }$, the Dirac probabilistic word $u^{\prime }=(p_1,\mathrm{\dots },p_{|u|})$ is the one that ensures that $u^{\prime }(u)=1$, namely, $p_i$ is the Dirac distribution on $u_i$ for each $1\le i\le |u|$. We may abuse notation and identify $u^{\prime }$ with $u$. Probabilistic membership to a language $L$ thus generalizes the standard (non-probabilistic) membership problem to $L$.

• $\mathrm{■}$

  For each $n\in \mathbb{N}$ the uniform probabilistic word of length $n$ is $p_n=(p_1,\mathrm{\dots },p_n)$ where each $p_i$ is the uniform distribution on $\mathrm{\Sigma }$. Its outcomes are precisely the words of ${\mathrm{\Sigma }}^n$, each with probability $1/{|\mathrm{\Sigma }|}^n$. Probabilistic membership to $L$ thus generalizes (up to renormalization by an easily-computable factor of ${|\mathrm{\Sigma }|}^n$) the unweighted counting problem studied in [13]: given an integer $n\in \mathbb{N}$, compute the cardinality $|L\cap {\mathrm{\Sigma }}^n|$.

• $\mathrm{■}$

  Probabilistic words are also a weighted generalization of partial words [11]. A partial word is a word $p$ over the alphabet $\mathrm{\Sigma }\cup \{\mathrm{?}\}$, for $\mathrm{?}$ a fresh wildcard. The semantics of $p$ is that it represents a set of possible words over ${\mathrm{\Sigma }}^{\ast }$ obtained by considering all possible completions of $p$, i.e., all possible ways to replace each occurrence of $\mathrm{?}$ in $p$ by a letter of $\mathrm{\Sigma }$. Note that all completions have length $|p|$. A partial word $p$ can be translated to a probabilistic word $q=(q_1,\mathrm{\dots },q_{|p|})$ where for each $1\le i\le |p|$ we set $q_i$ as the Dirac on $p_i$ if $p_i\in \mathrm{\Sigma }$ or as the uniform distribution if $p_i=\mathrm{?}$. Probabilistic membership to $L$ thus generalizes the problem of counting the number of completions of $p$ that are in $L$. In fact, all our hardness results already hold for a variant of this problem (see [6, Appendix A]).

Recall that FP is the class of function problems that can be solved by a deterministic polynomial-time Turing machine, and that #P is the class of counting problems that can be expressed as the number of accepting runs of a nondeterministic polynomial-time Turing machine. When seeing the output of FP problems as an integer, we have $FP\subseteq \mathrm{\#}$P. Further, ${\text{FP}}^{\mathrm{\#}\text{P}}$ is the class of function problems that can be solved in deterministic polynomial time with access to a #P oracle: we use this class simply because the answer to our problems are formally probabilities rather than integers. In the data complexity perspective, it is easy to see that the probabilistic membership problem $\text{\#pM}(L)$ is in ${\text{FP}}^{\mathrm{\#}\text{P}}$ for any language $L$ which is in the class PTIME, i.e., where there is a deterministic polynomial-time algorithm testing membership of an input (non-probabilistic) word to the language $L$: see, e.g., [40, Theorem 4.2] or [70, p19]. All languages studied in the sequel will be PTIME languages in this sense (as is the case of all CFLs).

We will be interested in languages $L$ for which $\text{\#pM}(L)$ is in FP (we will often abuse terminology and say in that case that $\text{\#pM}(L)$ is in PTIME), and languages $L$ for which $\text{\#pM}(L)$ is #P-hard, i.e., any problem in #P can be reduced by Turing reductions to $\text{\#pM}(L)$: note that we always use Turing reductions (and not many-one reductions). When giving complexity bounds with an explicit polynomial degree, to avoid specifying the details of the computational model we will state them up to the cost of arithmetic operations, i.e., assuming that all arithmetic operations take unit time.

Our goal in this paper is to determine for which languages $L$ the problem $\text{\#pM}(L)$ can be solved in polynomial time data complexity, and for which it is #P-hard.

We focus on the case of unambiguous CFLs and show:

We do not claim that the cubic dependency in the probabilistic word is optimal, and leave to future work the investigation of whether the complexity can be lowered, e.g., to match the complexity of Valiant’s parser [87], or the quadratic upper bound given by the Earley parser for unambiguous CFGs [33].

This result implies that #pM is tractable for many CFGs, e.g., the language of palindromes, the language $\{a^n{b}^n\mid n\in \mathbb{N}\}$, or the language of Dyck words. It also implies the tractability in data complexity of subclasses of uCFGs, for instance deterministic CFGs [37], or indeed all regular languages. Our result generalizes the tractability in combined complexity of (weighted or unweighted) counting for regular languages given as unambiguous automata, see, e.g., [24]. We note that, by contrast, hardness holds in combined complexity with nondeterministic automata as input: the problem is then #P-complete [2] but admits an FPRAS [8].

We convert the input uCFG $\mathrm{\Gamma }$ in linear time into arity-2 normal form (2NF) [63], which preserves unambiguity [5, Appendix A.2]. We then generalize the textbook CYK parsing algorithm that computes inductively, for each nonterminal $X$ and each interval $1\le i\le j\le n$, whether the factor of the input word with endpoints $[i,j]$ can be derived from $X$. Instead, we compute the total probability of the words that can be derived from $X$ in the distribution represented by the factor $(p_i,\mathrm{\dots }{p}_j)$. As $\mathrm{\Gamma }$ is unambiguous, every word admits at most one derivation tree, so there are no double counts. $◀$

However, for arbitrary CFGs, we cannot solve #pM simply by counting the probability of derivation trees in this fashion – because the probability of words with multiple derivation trees is counted as many times as there are trees¹¹1However, the algorithm as presented could apply to those CFGs in which all accepted words have precisely the same number of derivation trees. We do not know if this strictly generalizes uCFLs: see [3]..

The previous result shows that #pM is tractable for uCFLs, leaving open the complexity of inherently ambiguous CFLs. We will now show intractability in this case by first giving a simple explicit CFL for which #pM is hard, before extending the result to a 2-ambiguous CFL in the sequel.

Our #P-hardness result is by reducing from the problem of counting satisfying assignments to a certain class of Boolean formulas, called PP2DNFs, and defined below:

Satisfiability for PP2DNFs is trivial as there are no negations; by contrast:

We will now define our hard CFL $L_0$ on alphabet $\mathrm{\Sigma }≔\{0,1,\mathrm{\#}\}$:

where we abuse notation and write ${\mathrm{\Sigma }}^{\ast }$ to denote arbitrary factors in ${\mathrm{\Sigma }}^{\ast }$, and where we denote by $\le$ the order relation defined on $\{0,1\}$ by $0\le 1$ and extended in a pointwise manner on binary words of the same length, i.e., we have $v\le u$ if $|u|=|v|$ and for each $1\le i\le |u|$ we have $v_i\le u_i$. Equivalently, for each $1\le i\le |u|$ such that $v_i=1$ we also have $u_i=1$.

It is not hard to see that $L_0$ is a linear CFL, e.g., it can be recognized by ${\mathrm{\Gamma }}_0=(\{S,S_1,S_2\},S,P)$ with productions:

Our first hardness result is then:

We code a PP2DNF $\mathrm{\Phi }$ into a probabilistic word $p$ defined as follows. It starts with $2n$ times the uniform distribution on $\{0,1\}$ (representing all possible Boolean valuations on $\{0,1\}$), followed by #, then followed by #-separated codings of each clause $C_i$ as a non-probabilistic (mirrored) word $u_i^R$ of length $2n$. The word $u_i$ carries a $1$ at the position of the variables occurring in $C_i$. One then sees that the outcomes of $p$ satisfying $L_0$ are precisely those for which there is a clause $C_i$ such that the outcome of $u$ contains a $1$ at all positions where $u_i$ contains as $1$, i.e., precisely those where the corresponding Boolean valuation satisfies $\mathrm{\Phi }$. $◀$

We remark that the hardness proof easily adapts to a more symmetric language:

We now move to our second hardness result:

This result above implies in particular²²2We do not know whether this is a generalization, because it is not known whether all 2-ambiguous CFLs can be written as the union of two uCFLs, cf [92, Section 9.3, point (iv)]. that #pM is hard already for 2-ambiguous linear CFLs.

We show instead hardness of $\text{\#pM}(L_{\text{L}}\cap L_{\text{R}})$, which is PTIME-equivalent by inclusion-exclusion, using the fact that $\text{\#pM}(L_{\text{L}})$ and $\text{\#pM}(L_{\text{R}})$ are in PTIME by Proposition 3.1. We fix a nondeterministic polynomial-time Turing machine for which it is #P-hard to count the accepting runs, and encode its runs as in [9], intuitively as a probabilistic word of the form $p=w_1\mathrm{\#}{w}_3\mathrm{\#}\mathrm{\cdots }\mathrm{\#}{w}_4^R\mathrm{\#}{w}_2^R$, with all $w_i$ having the same length and each of them being uniform probabilistic words that will encode the configuration of the machine at time step $i$. (Note that the word $p$ hardcodes a polynomial-sized initial tape and a polynomial duration for the computation.) The language $L_{\text{L}}$ checks the correctness of even transitions (i.e., it reads $w_{2k+1}$ and $w_{2k+2}$ in lockstep for each $k$ and check that the transition of the machine is correct), and $L_{\text{R}}$ does the same for odd transitions (it skips until the first # and then proceeds accordingly). This ensures that $L_{\text{L}}\cap L_{\text{R}}$ precisely accepts those outcomes of $p$ where each pair of configuration is a valid transition, i.e., $\text{\#pM}(L_{\text{L}}\cap L_{\text{R}})$ counts the accepting runs of the machine. $◀$

We introduce our more general class of tractable languages:

Poly-slicewise-unambiguous languages include languages that are not CFLs, hence tractability will also hold for such languages. Note that the complexity of ${𝒜}_L$ is measured as a function of $n$ only (as $L$ is fixed). Further note that a similar notion has been studied in [79, 93] under the name “1U”. These are families of sequences of languages ${(L_i)}_{i\in \mathbb{N}}$ where each $L_i$ has a unambiguous NFA of size $p(i)$ for some fixed polynomial $p$. However, unlike us, the definition of 1U does not require the NFAs to be computable in PTIME, i.e., these works use a non-uniform setting.

Of course, any uCFL $L$ is immediately poly-slicewise-unambiguous (taking ${𝒜}_L$ that always returns an unambiguous grammar $\mathrm{\Gamma }$ for $L$), but we will later show that some inherently ambiguous CFLs are poly-slicewise-unambiguous. The following tractability result in data complexity immediately follows from Proposition 3.1:

Indeed, to solve $\text{\#pM}(L)$ on an input probabilistic word $p$ of length $n$, we use ${𝒜}_L$ to compute in polynomial time the uCFG ${\mathrm{\Gamma }}_{L,n}$, and then invoke Proposition 3.1. The overall complexity (up to arithmetics) is in $O(n^{k+3})$ if ${𝒜}_L$ has running time bounded by $O(n^k)$.

We will now show how Proposition 4.2 specializes to so-called bounded CFLs and to counter automata, and remark in particular that it strictly generalizes Proposition 3.1.

In this section we study the class of bounded CFLs, namely, those CFLs $L$ for which there exist words $u_1,\mathrm{\dots },u_k$ such that $L\subseteq u_1^{\ast }\mathrm{\cdots }{u}_k^{\ast }$. This class has been studied for a long time [38] and was equivalently characterized as those CFLs that are polyslender, i.e., there is $k\in \mathbb{N}$ such that for all $n\in \mathbb{N}$, we have $|L\cap {\mathrm{\Sigma }}^n|$ is in $O(n^k)$. It is immediate that bounded CFLs are polyslender, and the reverse inclusion is known to hold [50]. The following result is easy to show by a variant of CYK:

Thus, bounded CFLs are poly-slicewise-unambiguous, even in “combined complexity”:

This implies the following combined tractability result of #pM on bounded CFLs:

Importantly, some polyslender CFLs are inherently ambiguous, such as $\{a^n{b}^m{c}^m\mid n,m\in \mathbb{N}\}\cup \{a^n{b}^n{c}^m\mid n,m\in \mathbb{N}\}$. Hence, this result covers some languages not covered by Proposition 3.1. Also note that the results above adapt to any language which is “constructively polyslender” in the sense of Proposition 4.3 (even beyond CFLs).

We now present another language formalism enjoying tractable #pM via Proposition 4.2, namely, polynomial-time counter automata:

The model described here is very general: it allows arbitrary polynomial-time computations at each step, and it can freely use the value of counters during the run (i.e., it is not blind or partially blind [42]). Thus, it generalizes the model of counter machines from Fischer et al. [35] when those machines are required to be real-time (i.e., they read one input symbol at each transition), or more generally when they operate in polynomial-time (so they can only do a polynomial number of autonomous transitions between input symbols). Further, the model generalizes Vector Addition Systems with States or VASSes [55]; Parikh automata [58] (also called $\mathbb{Z}$-VASSes [27] or integer VASSes [23]); pushdown automata with a unary stack alphabet aka one-counter automata [89]; and extensions such as Parikh one-counter automata [19]. The main restriction is that our counter automata must read the word in a one-way fashion and in particular they only see each input symbol once.

The non-probabilistic membership problem to polynomial-time counter automata $A$ is in PTIME, and for unambiguous such automata #pM is in PTIME for similar reasons:

We use a product construction to construct a nondeterministic finite automaton (NFA) $A_n$ with $\text{L}(A_n)=\text{L}(𝒜)\cap {\mathrm{\Sigma }}^n$, by considering the polynomial number of potentially reachable configurations, and testing the acceptance and transition relations in polynomial time. As $𝒜$ is unambiguous, we know that $A_n$ is also an unambiguous NFA, and $A_n$ can directly be converted in linear time to a uCFG, which concludes. $◀$

By Proposition 4.2, this immediately implies that $\text{\#pM}(L)$ is tractable for any language recognized by an unambiguous polynomial-time counter automata: so the same is true for languages recognized by unambiguous Parikh automata, unambiguous VASSes, etc.

To contrast with our previous results, note that unambiguous polynomial-time counter automata and uCFLs are incomparable. These automata cannot recognize some uCFLs such as the language of palindromes, intuitively because this requires exponentially many configurations: see [71, Theorem 5]. Conversely, these automata can recognize some languages that are not even CFLs (e.g., $\{a^n{b}^n{c}^n\mid n\in \mathbb{N}\}$), and they can also recognize some CFLs such as $\{u\in {\mathrm{\Sigma }}^{\ast }\mid {|u|}_a\ne {|u|}_b\vee {|u|}_a\ne {|u|}_c\}$ that are not polyslender and inherently ambiguous [10, Proposition 1.10], so their tractability for #pM did not follow from our previous results.

Is the unambiguity requirement in Proposition 4.7 necessary? In this section, we show that #pM is intractable on nondeterministic counter automata, even for CFLs accepted by very restricted such automata:

We reduce from #PP2DNF. The left and right parts of the words contain blocks of each possible length (corresponding to the variables $x_i$ and $y_j$ respectively), with a 1/2 chance of being set to true, and the middle part contains a block for each clause. $◀$

Both $L_1$ and $L_2$ are CFLs because they can be recognized by nondeterministic pushdown automata with unary stack alphabet: this is a restriction of our counter automaton formalism, with only one counter and very simple transition and acceptance relations. The language $L_2$ can even be recognized by a (nondeterministic) 1-dimensional Parikh automaton, i.e., a counter automaton with a single blind counter which is only tested at the end of the run. Hence, hardness for #pM can hold even for very restricted ambiguous counter automata.

We will define (smooth) $\times ,\uplus$-circuits following [4], which are a multivalued analogue to the sd-DNNF circuits used in knowledge compilation [29]. A circuit $C$ is a directed acyclic graph with vertices called gates. An input to a gate $g$ is a gate $g^{\prime }$ having a directed edge to $g$, the fan-in of $g$ is the number of inputs that $g$ has, and the fan-out of $g$ is the number of gates of which $g$ is an input. An input gate is a gate with fan-in zero. We assume that $C$ has a distinguished gate with fan-out zero, called the output gate.

Let $\mathrm{\Sigma }$ be the alphabet. A $\times ,\uplus$-circuit on $\mathrm{\Sigma }$ is a circuit whose input gates are labeled by pairs $n:a$ for $n>0$ and $a\in \mathrm{\Sigma }$, and whose internal gates are labeled with $\times$ or $\uplus$ and satisfy the three requirements of decomposability, smoothness, and disjointness that we now present. To state the first two requirements, we need to define inductively the domain of each gate $g$ of $C$: the domain of an input gate $g$ labeled by $n:a$ is $\mathrm{dom}(g)≔\{n\}$, and the domain $\mathrm{dom}(g)$ of an internal gate $g$ is the union of $\mathrm{dom}(g^{\prime })$ for all inputs $g^{\prime }$ of $g$. The domain $\mathrm{dom}(C)$ of $C$ is that of its output gate. We then say that a $\times$-gate $g$ is decomposable if the domains of the input gates of $g$ are pairwise disjoint, and we require that $C$ is decomposable, i.e., every $\times$-gate of $C$ is. We say that a $\uplus$-gate $g$ is smooth if the domains of the input gates of $g$ are all identical, and we require that $C$ is smooth, i.e., every $\uplus$-gate is.

To state disjointness, we need to define inductively the sets of assignments $\mathrm{SS}(g)$ captured by each gate $g$ of $C$, as a set of partial functions $f$ from $\mathbb{N}$ to $\mathrm{\Sigma }$ with $\mathrm{dom}(f)=\mathrm{dom}(g)$:

• $\mathrm{■}$

  For an input gate $g$ of the form $n:a$, we have $\mathrm{SS}(g)≔\{n\mapsto a\}$;

• $\mathrm{■}$

  For an internal $\uplus$-gate $g$, letting $g_1,\mathrm{\dots },g_k$ be its input gates, we have $\mathrm{SS}(g)≔{⨄}_i\mathrm{SS}(g_i)$;

• $\mathrm{■}$

  For an internal $\times$-gate $g$, letting $g_1,\mathrm{\dots },g_k$ be its input gates, we have $\mathrm{SS}(g)≔{\times }_i\mathrm{SS}(g_i)$.

The $\times$ operator denotes the Cartesian product, where we identify a tuple of functions $(f_1,\mathrm{\dots },f_k)\in {\times }_i\mathrm{SS}(g_i)$ with the function $f$ defined like each $f_i$ on $\mathrm{dom}(f_i)=\mathrm{dom}(g_i)$, noting that by decomposability these domains are disjoint. In particular, if $g$ is a $\uplus$-gate with no inputs then $\mathrm{SS}(g)≔\mathrm{\varnothing }$, and if $g$ is a $\times$-gate with no inputs then $\mathrm{SS}(g)≔\{{\mathrm{\varnothing }}_{\mathrm{\Sigma }}\}$ for ${\mathrm{\varnothing }}_{\mathrm{\Sigma }}$ the function to $\mathrm{\Sigma }$ with empty domain. We will write $\mathrm{SS}(C)$ to mean $\mathrm{SS}(g_0)$ for $g_0$ the output gate of $C$. We then say that an $\uplus$-gate $g$ is disjoint if for any two inputs $g^{\prime }$ and $g^{\prime \prime }$ of $g$, the sets $\mathrm{SS}(g^{\prime })$ and $\mathrm{SS}(g^{\prime \prime })$ are disjoint. We require that $C$ is disjoint, i.e., every $\uplus$-gate is.

Given a probabilistic word $p=(p_1,\mathrm{\dots },p_n)$, and a circuit $C$ with domain $\mathrm{dom}(C)=\{1,\mathrm{\dots },n\}$, the probability $p(C)$ of $C$ under $p$ is the sum of the probabilities of the functions of $\mathrm{SS}(C)$ under $p$, where the probability of $f:\mathrm{dom}(C)\to \mathrm{\Sigma }$ under $p$ is simply $p(w_f)$ for the word $w_f=f(1)\mathrm{\cdots }f(n)$. The point of $\times ,\uplus$-circuits $C$ is that we can tractably compute the probability of $C$ under a probabilistic word $p$ without materializing the (potentially exponential) set $\mathrm{SS}(C)$ of assignments that $C$ captures. This is the immediate analogue of the tractability of model counting for sd-DNNFs [28]:

For $n\in \mathbb{N}$, we say that a $\times ,\uplus$-circuit captures the $n$-th slice of a language $L$ if $\mathrm{dom}(C)=\{1,\mathrm{\dots },n\}$ and $\mathrm{SS}(C)$ precisely corresponds to the words of $L\cap {\mathrm{\Sigma }}^n$, i.e., a function $f:\{1,\mathrm{\dots },n\}\to \mathrm{\Sigma }$ is in $\mathrm{SS}(C)$ precisely if the word $f(1)\mathrm{\cdots }f(n)$ is in $L$. We say that a language admits tractable circuits if there is an algorithm $A$ running in polynomial time in its input $n\in \mathbb{N}$ which computes a $\uplus ,\times$-circuit $A(n)$ that captures the $n$-th slice of $L$. (Note that this is stronger than requiring the mere existence of polynomial-sized circuits: we assume that they can also be computed in polynomial time.) The following is then a direct consequence of Proposition 5.1:

Which languages admit tractable circuits? In fact, all poly-slicewise-unambiguous languages do, because we can build tractable circuits for uCFLs:

This implies the following on poly-slicewise-unambiguous languages (in particular uCFLs):

We next show that, even within the class of CFLs, the converse of Corollary 5.4 does not hold. Thus, the tractability of #pM for languages admitting tractable circuits (Proposition 5.2) strictly generalizes the same result for poly-slicewise-unambiguous languages (Proposition 4.2). For this, consider the language on $\mathrm{\Sigma }=\{a,b\}$, which consists of the words of length $2n$ which contain two occurrences of $a$ at distance exactly $n$. This language is a CFL which is inherently ambiguous [57, Proposition 5.8]. It is shown in [68, Theorem 1] that this language is not poly-slicewise-unambiguous: they show a lower bound of $2^{\mathrm{\Omega }(n)}$ on the size of any uCFG accepting $L\cap {\mathrm{\Sigma }}^n$, so in particular there is no algorithm computing such uCFGs in polynomial time in $n$. However:

We first test letters $a_1$ and $a_{n+1}$ and check if they are both equal to $a$. If not, we move to $a_2$ and $a_{n+2}$. We continue until we reach $a_n,a_{2n}$, and otherwise we fail. This describes an ordered binary decision diagram or OBDD [18], which gives a $\times ,\uplus$-circuit. $◀$

This implies that $\text{\#pM}(L_3)$ is tractable. Intuitively, the proof uses the fact that tractable circuits are not constrained to reading the word in left-to-right fashion, or in any predefined order: this is in contrast with uCFGs and with poly-slicewise-unambiguous languages. This also resembles formalisms such as Multiple Context Free Grammars (MCFGs) [81], which generalize CFGs by deriving tuples of strings instead of strings: MCFGs can recognize complex parenthetical structures [53], languages that do not satisfy strong forms of pumping lemmas [54], or images of regular tree languages by MSO tree-to-string transductions [61]. In fact, since MCFGs admit a generalization of the CYK algorithm [81], we could easily generalize Proposition 5.3 to unambiguous MCFGs. This would recapture the tractability of $\text{\#pM}(L_3)$, and also show tractability for other languages definable by unambiguous MCFGs.

The motivation for extending $\times ,\uplus$-circuits with complement gates is that complements of tractable languages for #pM are always tractable:

The answer to $\text{\#pM}(L^{\prime })$ on $p$ is simply $1-A$, for $A$ the answer to $\text{\#pM}(L)$ on $p$. $◀$

Thus, all our tractability results on languages immediately extend to their complements (even though the complement of a CFL, or indeed of a uCFL, is generally not a CFL [45]).

However, beyond the use of negation at the top-level, we could also support negation as an arbitrary intermediate gate. This motivates the definition of $\times ,\uplus ,\mathrm{\complement }$-circuits:

These gates correspond to negation gates for Boolean circuits, and $\times ,\uplus ,\mathrm{\complement }$-circuits can be seen as a multivalued analogue of the (smooth) d-D circuits recently studied in probabilistic databases [69]. We can immediately generalize Proposition 5.1 to show:

Hence, we can use $\times ,\uplus ,\mathrm{\complement }$-circuits to show the tractability of #pM. We say that such a circuit captures the $n$-th slice of a language $L$ by the obvious generalization of the definition of Section 5, and that $L$ admits tractable $\times ,\uplus ,\mathrm{\complement }$-circuits if there is an algorithm which given a length $n$ computes in polynomial time in $n$ a $\times ,\uplus ,\mathrm{\complement }$-circuit that captures the $n$-th slice of $L$. By the immediate generalization of Proposition 5.2, this implies tractability for #pM.

While we will use complement gates in this section, we do not know whether they are necessary, i.e., whether $\times ,\uplus ,\mathrm{\complement }$-circuits capture the tractability of #pM for more languages than $\times ,\uplus$-circuits; we come back to this point in the conclusion. We also note that the support of negation in relation with (u)CFLs seems superficially similar to the notions of conjunctive grammars and Boolean grammars [73], in particular to unambiguous such grammars [72]. However, the semantics of Boolean grammars are different, because they allow in particular conjunctions that range over the entire word (and so are not decomposable). Thus, unambiguous conjunctive grammars include, e.g., the intersections of two uCFGs; but #pM can be intractable for such languages (see the proof of Proposition 3.6). This suggests that the tractability of unambiguous Boolean grammars (e.g., for parsing) does not extend to counting, so there is no obvious connection to our results.

We will now show that the language of primitive words admits tractable $\times ,\uplus ,\mathrm{\complement }$-circuits in the sense above, and will then show the same for the language ${\mathrm{PAL}}^2$.

Let us first define the language $L_{\text{prim}}$ of primitive words. We fix an arbitrary alphabet $\mathrm{\Sigma }$. A word $w\in {\mathrm{\Sigma }}^{\ast }$ is composite if there exist $u\in {\mathrm{\Sigma }}^{\ast }$ and $k\ge 2$ such that $w=u^k$. If $w$ is not composite, then we say that $w$ is primitive, i.e., a word is primitive if it is not a proper power of another word. In particular, the empty word is not primitive. The language $L_{\text{prim}}$ consists of all primitive words over the alphabet $\mathrm{\Sigma }$.

We note that, over non-unary alphabets, it is not currently known whether $L_{\text{prim}}$ is a CFL or not [51]. However, it is known that $L_{\text{prim}}$ is not a uCFL [74, 60], and also that $L_{\text{prim}}$ is not a linear CFL [47]. We do not know whether $L_{\text{prim}}$ is poly-slicewise-unambiguous, or whether it admits tractable circuits without complementation. Our goal is to show the tractability of #pM for primitive words (and hence for composite words, by ˜6.1). Namely:

We prove this result before turning to the language ${\mathrm{PAL}}^2$, which will use a similar technique. Our proofs rely on the standard notion of the (primitive) root and of the order of a word. For the uniqueness and well-definedness of these notions, see [83, Theorem 2.3.4]:

Our algorithm to solve $\text{\#pM}(L_{\text{prim}})$ will proceed by distinguishing words according to their order. For this, we introduce two families of languages:

To solve $\text{\#pM}(L_{\text{prim}})$, we first show that $M_k$ admits tractable $\times ,\uplus$-circuits for all $k\in \mathbb{N}$:

The only non-trivial case is when $k$ divides $n$. Then, letting $d≔n/k$, a word belongs to $M_k$ precisely when, for each $1\le j\le d$ all positions on $\{j+pd\mid 0\le p\le k-1\}$ contain the same letter. So we do a decomposable product across the values of $j$, and for each value we do a deterministic union across the choice of letter, and then do a decomposable product asserting that this letter occurs at the requisite positions. $◀$

Now, we can construct circuits capturing $L_{\text{prim}}=L_1$, and in fact $L_k$ for each $k$, from the circuits capturing the $M_k$. Namely, we show the following, which allows us to conclude the proof of Proposition 6.4:

We do a downwards induction, where we compute a circuit for each $L_k^{\prime }$ from the circuit for $M_k^{\prime }$ and the disjoint union of the circuits for $L_{dk}^{\prime }$ for $d>1$. This requires us to do a subset-complement operation, which can be achieved with complementation. $◀$

We now move on to the study of the CFL ${\mathrm{PAL}}^2$, where $\mathrm{PAL}$ is the language of palindromes on our alphabet $\mathrm{\Sigma }$. Our main result is:

It is known that ${\mathrm{PAL}}^2$ is an inherently ambiguous CFL with infinite ambiguity degree [26], so the tractability of $\text{\#pM}({\mathrm{PAL}}^2)$ does not follow from Proposition 3.1. It is incidentally easy to show that ${\mathrm{PAL}}^2$ is not a linear CFL (see [6, Appendix E.3]). The language ${\mathrm{PAL}}^2$ has been abundantly studied, e.g., in [43, Section 3]; its words have been called palindrome pairs [16], or symmetric words [17, 34]. The efficient recognition of ${\mathrm{PAL}}^k$ for arbitrary $k$ (e.g., in linear time) was studied in [62]; see also [78]. More relevant to our purposes, the problem of counting the number of words of ${\mathrm{PAL}}^2$ was studied in [56], but they study unweighted counting, depending only on the word length and on the alphabet size. Our proof of Theorem 6.9 reuses the following word combinatorics result from [56] (using [26], with similar results in [30, Proposition 9] or [31, Lemma 1]):

Using this lemma, the proof of Theorem 6.9 deviates from [56] (which uses generating functions). Namely, we follow an inclusion-exclusion-based reasoning which is similar to that of primitive words but more complicated (we partition words based on their order and on also the offset of their decomposition into two palindromes).