9
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.