# Complexity of a problem over acyclic context-free grammars

Let $$G$$ be an acyclic, context-free grammar over a fixed alphabet $$\Sigma=\{a_1,\dots,a_k\}$$ with the restriction (without loss of generality) that $$|w|=2$$ for each rule $$A\to w$$ in the grammar. Acyclic means that if $$N$$ is the set of nonterminals, then $$\{(A,B)\in N^2\mid A\to xBy\text{ is a rule in }G\text{; }x,y\in(\Sigma\cup N)^*\}$$ is an acyclic relation. So $$L(G)$$ is finite. Let in this setting the size of a grammar be defined as the number of nonterminals

My question

Let $$\#_w(i,j)$$ be the number of different subsequences of $$a_ia_j$$ in $$w$$. For example $$w=a_1a_1a_2a_2a_1$$ yields $$\#_w(1,2)=4$$, $$\#_w(2,1)=2$$, $$\#_w(1,1)=3$$ and $$\#_w(2,2)=1$$. Now I am looking for the complexity of:

Given: Acyclic, context-free grammar $$G$$ and numbers $$n_{i,j}$$ with $$i,j\in\{1,\cdots,k\}$$

Problem: Is there a word $$w\in L(G)$$ with $$\#_w(i,j)=n_{i,j}$$ for all $$i,j\in\{1,\cdots,k\}$$ ?

Background / Well-studied, related problem

The following problem is one step behind my question. In my question, the number of occurences of all subsequences of length $$2$$ are given. We could first ask, what is the complexity, if the given numbers are the occurences of subsequences of length $$1$$, i.e. the given numbers are the occurences of the alphabet symbols. So, let $$\#_w(i)$$ denote the number of occurences of $$a_i$$ in $$w\in\Sigma^*$$. The following problem is known to be $$\mathsf{NP-complete}$$:

Given: Acyclic, context-free grammar $$G$$ and numbers $$n_1,\dots ,n_k$$
Problem: Is there a word $$w\in L(G)$$ with $$\#_w(i)=n_i$$ for all $$i\in\{1,\cdots,k\}$$ ?

McKenzie and Wagner ("THE COMPLEXITY OF MEMBERSHIP PROBLEMS FOR CIRCUITS OVER SETS OF NATURAL NUMBERS") provide an $$\mathsf{NP}$$ algorithm to solve the membership problem of circuits over the natural numbers with $$\cup$$ and $$+$$. A slightly modified algorithm solves our problem. The algorithm in short: In addition to the given numbers, we guess for each nonterminal how often it occurs in a derivation tree and for each rule how often it is applied in a derivation tree. Afterwards, we check whether there is a derivation tree of $$G$$ satisfying the guessed numbers by checking some relations between those numbers. The problem should also be $$\mathsf{NP-hard}$$, e.g. as a conclusion of Kopczyński and Widjaja To ("Complexity of Problems for Parikh Images of Automata").

Still $$\mathsf{NP}$$ ?

Is the problem for subsequences of length $$2$$ still solvable in $$\mathsf{NP}$$ ? Of course it is at least as hard as the related problem for subsequences of length $$1$$, because $$\#_w(i,i)=\frac {\#_w(i)\cdot(\#_w(i)-1)}{2}.$$ Unfortunately, I am neither able to extend the algorithm of McKenzie and Wagner to get an $$\mathsf{NP}$$ algorithm, nor can I show another hardness result like $$\mathsf{coNP}$$ hardness. Thanks for any help.