Complexité de vérifier si deux mots ont un entrelacement dans une langue

Pour une langue fixe sur un alphabet A , considérons le problème suivant, que j'appelle L -INTERLEAVING :$L$$A$$L$

• Entrée: deux mots $u, v \in A^*$
• Rendement: s'il existe un entrelacement de et v , qui est en L .$u$$v$$L$

Ici, un entrelacement de deux mots et v est un mot w qui peut être obtenu intuitivement en prenant les lettres de u et v tout en gardant leur ordre relatif. Formellement, w est un entrelacement de u et v si nous pouvons le partitionner en deux sous-séquences disjointes, une qui est égale à u et l'autre qui est égale à v . Par exemple, "bheleloll" est un entrelacement de "bonjour" et de "cloche".$u$$v$$w$$u$$v$$w$$u$$v$$u$$v$

Quelle est la complexité du problème -INTERLEAVING, selon la langue L ? $L$$L$En particulier:

• Si est régulier, alors nous pouvons résoudre le problème avec un algorithme dynamique sur les deux chaînes qui montre qu'il est dans la classe NL. Est-ce difficile en NL pour certaines langues régulières? Cependant, pour certaines langues régulières, le problème est clairement dans L (espace de log déterministe). Existe-t-il une caractérisation des langues pour lesquelles le problème se situe en L?$L$
• Si n'est pas régulier, le problème est toujours en NL lorsque L a une complexité d'espace déterministe en ligne polynomiale (voir ici pour cette notion, ou ma question précédente ). Cependant, cela ne couvre pas, par exemple, toutes les langues sans contexte; pourtant, certains autres (par exemple, les palindromes) peuvent également être présentés comme NL (par exemple, en faisant un algorithme dynamique simultanément depuis le début et la fin). Existe-t-il un langage sans contexte dont le problème d'entrelacement en L est difficile à NP?$L$$L$$L$

$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)$

• $u=u_1\ldots u_m$$v=v_1\ldots v_n$
• $L$

$[i,j,r,s,A]$

• $i,j$$1\le i\le j\le m$$i=j=0$
• $r,s$$1\le r\le s\le n$$r=s=0$
• $A$

$A$$u(i,j)$$w(r,s)$

$L$$L$