Złożoność sprawdzania, czy dwa słowa mają przeplatanie w języku

Dla ustalonego języka $L$ na jakiś alfabet $A$, rozważmy następujący problem, który nazywam $L$-WŁOKA WEWNĘTRZNA :

• Wejście: dwa słowa $u, v \in A^*$
• Wyjście: czy istnieje takie przeplatanie od$u$ i $v$ która jest w $L$.

Tutaj przeplatają się dwa słowa$u$ i $v$ to słowo $w$ które można uzyskać intuicyjnie, biorąc litery $u$ i $v$zachowując ich względną kolejność. Formalnie,$w$ jest przeplotem $u$ i $v$ jeśli możemy podzielić go na dwa rozłączne podsekwencje, jeden równy $u$ a drugi, który jest równy $v$. Na przykład „bheleloll” to przeplatanie „hello” i „bell”.

Jaka jest złożoność $L$-WYMIAR WEWNĘTRZNY, w zależności od języka $L$? W szczególności:

• Gdyby $L$jest regularny, wtedy możemy rozwiązać problem za pomocą algorytmu dynamicznego na dwóch ciągach, który pokazuje, że jest w klasie NL. Czy w niektórych zwykłych językach jest to trudne? Jednak w przypadku niektórych zwykłych języków problemem jest wyraźnie L (deterministyczny obszar logów). Czy istnieje jakaś charakterystyka języków, dla których problem występuje w L?
• Gdyby $L$ nie jest regularny, problem nadal występuje w Holandii, kiedy $L$ma wielomianową deterministyczną złożoność przestrzeni online (zobacz tutaj to pojęcie lub moje wcześniejsze pytanie ). Nie obejmuje to jednak np. Wszystkich języków bezkontekstowych; jednak niektóre inne (np. palindromy) można również wykazać jako NL (np. wykonując algorytm dynamiczny jednocześnie od początku i od końca). Czy istnieje język bezkontekstowy, którego$L$-problem przeplatania jest trudny NP?

Za słowo $w=w_1\ldots w_{\ell}$ i dla dwóch liczb całkowitych $i,j$ z $1\le i\le j\le \ell$ oznaczamy przez $w(i,j)$ podmowa $w_iw_{i+1}\ldots w_j$ z $w$. Ponadto pozwalamy$w(0,0)$ oznacz puste słowo.

• Pozwolić $u=u_1\ldots u_m$ i $v=v_1\ldots v_n$ dwa rozważane słowa.
• Załóżmy, że język bezkontekstowy $L$ jest określony przez bezkontekstową gramatykę w normalnej formie Chomsky'ego.

Zbuduj program dynamiczny, w którym stan $[i,j,r,s,A]$ jest określone przez

• dwie liczby całkowite $i,j$ z $1\le i\le j\le m$ lub $i=j=0$
• dwie liczby całkowite $r,s$ z $1\le r\le s\le n$ lub $r=s=0$
• nieterminalny symbol $A$ w gramatyce bezkontekstowej

Dla każdego stanu zdecyduj, czy w gramatyce bezkontekstowej istnieje pewna pochodna, która zaczyna się od nieterminalnej $A$ i to kończy się przeplataniem dwóch słów $u(i,j)$ i $w(r,s)$. Decyzję tę można łatwo podjąć, jeśli stany są obsługiwane we właściwej kolejności (krótkie słowa przed dłuższymi słowami).

Podsumowując, daje to algorytm wielomianu czasu dla $L$-interleaving problem dowolnego języka bezkontekstowego $L$.