Komplexität der Überprüfung, ob zwei Wörter in einer Sprache verschachtelt sind

Betrachten wir für eine feste Sprache in einem Alphabet A das folgende Problem, das ich L- INTERLEAVING nenne :$L$$A$$L$

• Eingabe: zwei Wörter $u, v \in A^*$
• Output: ob eine existiert Verschachtelung von und v , die in ist L .$u$$v$$L$

Hier ist eine Verschachtelung von zwei Wörtern und v ein Wort w , das intuitiv erhalten werden kann, indem die Buchstaben von u und v genommen werden, während ihre relative Reihenfolge beibehalten wird. Formal ist w eine Verschachtelung von u und v, wenn wir es in zwei disjunkte Teilsequenzen aufteilen können, eine, die gleich u ist, und eine, die gleich v ist . Zum Beispiel ist "bheleloll" eine Verschachtelung von "Hallo" und "Glocke".$u$$v$$w$$u$$v$$w$$u$$v$$u$$v$

Was ist die Komplexität des INTERLEAVING-Problems in Abhängigkeit von der Sprache L ? $L$$L$Speziell:

• Wenn regulär ist, können wir das Problem mit einem dynamischen Algorithmus für die beiden Zeichenfolgen lösen, der zeigt, dass es in der Klasse NL liegt. Ist es für einige reguläre Sprachen NL-schwer? Bei einigen regulären Sprachen liegt das Problem jedoch eindeutig in L (deterministischer Logspace). Gibt es eine Charakterisierung der Sprachen, für die das Problem in L liegt?$L$
• Wenn nicht regulär ist, liegt das Problem immer noch in NL, wenn L eine polynomielle online deterministische Raumkomplexität aufweist (siehe hier für diesen Begriff oder meine frühere Frage ). Dies gilt jedoch nicht für alle kontextfreien Sprachen; Es kann jedoch auch gezeigt werden, dass einige andere (z. B. Palindrome) NL sind (z. B. indem gleichzeitig von Anfang bis Ende ein dynamischer Algorithmus ausgeführt wird). Gibt es eine kontextfreie Sprache, deren L- Interleaving-Problem NP-schwer ist?$L$$L$$L$

Für ein Wort und für zwei ganze Zahlen i , j mit 1 ≤ i ≤ j ≤ ℓ bezeichnen wir mit w ( i , j ) das Unterwort w i w i + 1 … w j von w . Weiterhin lassen wir w ( 0 , 0 ) das leere Wort bezeichnen.$w=w_1\ldots w_{\ell}$$i,j$$1\le i\le j\le \ell$$w(i,j)$$w_iw_{i+1}\ldots w_j$$w$$w(0,0)$

• Sei und v = v 1 … v n die beiden betrachteten Wörter.$u=u_1\ldots u_m$$v=v_1\ldots v_n$
• Angenommen, die kontextfreie Sprache wird durch eine kontextfreie Grammatik in Chomsky-Normalform angegeben.$L$

Erstellen Sie ein dynamisches Programm, in dem ein Zustand angegeben ist$[i,j,r,s,A]$

• zwei ganze Zahlen mit 1 ≤ i ≤ j ≤ m oder i = j = $i,j$$1\le i\le j\le m$$i=j=0$
• zwei ganze Zahlen mit 1 ≤ r ≤ s ≤ n oder r = s = $r,s$$1\le r\le s\le n$$r=s=0$
• ein nicht-terminales Symbol in der kontextfreien Grammatik$A$

Entscheiden Sie für jeden Zustand, ob es in der kontextfreien Grammatik eine Ableitung gibt, die mit dem nicht-terminalen beginnt und mit einer Verschachtelung der beiden Wörter u ( i , j ) und w ( r , s ) endet . Diese Entscheidung kann leicht getroffen werden, wenn die Zustände in der richtigen Reihenfolge behandelt werden (kurze Unterwörter vor längeren Unterwörtern).$A$$u(i,j)$$w(r,s)$

Alles in allem ergibt dies eine Polynomialzeitalgorithmus für die -interleaving Problem jeder kontextfreien Sprache L .$L$$L$