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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.