Une classe spéciale de langues: les langues «circulaires». Est-il connu?

Définissez la classe suivante de langues "circulaires" sur un alphabet fini Sigma. En fait, le nom existe déjà pour désigner une chose différente, semble-t-il, utilisée dans le domaine de l'informatique ADN. AFAICT, c'est une classe de langues différente.

Un langage L est circulaire ssi pour tous les mots dans , on a:$w$$\Sigma^*$

$w$ appartient à L si et seulement si pour tous les entiers , appartient à L.k > 0 w $k > 0$$w^k$

Cette classe de langues est-elle connue? Je m'intéresse aux langues circulaires qui sont également régulières et notamment:

• un nom pour eux, s'ils sont déjà connus

• décidabilité du problème, étant donné un automate (en particulier: un DFA), si le langage accepté obéit à la définition ci-dessus

Dans la première partie, nous montrons un algorithme exponentiel pour décider de la circularité. Dans la deuxième partie, nous montrons que ce problème est coNP-dur. Dans la troisième partie, nous montrons que tout langage circulaire est une union de langages de la forme r + (ici r pourrait être l'expression rationnelle vide); l'union n'est pas nécessairement disjointe. Dans la quatrième partie, nous présentons un langage circulaire qui ne peut pas s'écrire comme une somme disjointe ∑ r + i .$r^+$$r$$\sum r_i^+$

Edit: Incorporé quelques corrections suite aux commentaires de Mark. En particulier, mes affirmations antérieures selon lesquelles la circularité est coNP-complète ou NP-dure sont corrigées.

Edit: forme normale corrigée de ∑ r ∗ i à ∑ r + i . Présentait un langage "intrinsèquement ambigu".$\sum r_i^*$$\sum r_i^+$

Poursuivant le commentaire de Peter Taylor, voici comment décider (de manière extrêmement inefficace) si une langue est circulaire compte tenu de son DFA. Construisez un nouveau DFA dont les états sont n -tuples des anciens états. Ce nouveau DFA exécute n copies de l'ancien DFA en parallèle.$n$$n$

Si le langage n'est pas circulaire, alors il y a un mot w tel que si nous le parcourons le DFA à plusieurs reprises, en commençant par l'état initial s 0 , alors nous obtenons les états s 1 , … , s n tels que s 1 accepte mais un des autres n'accepte pas (si tous acceptent alors alors la séquence s 0 , … , s n doit faire un cycle pour que w ∗ soit toujours dans le langage). En d'autres termes, nous avons un chemin de s 0 , … , s $w$$s_0$$s_1,\ldots,s_n$$s_1$$s_0,\ldots,s_n$$w^*$- 1 à s 1 ,…, s n où s 1 accepte mais que l'un des autres n'accepte pas. Inversement, si la langue est circulaire, cela ne peut pas se produire.$s_0,\ldots,s_{n-1}$$s_1,\ldots,s_n$$s_1$

Nous avons donc réduit le problème à un simple test d'accessibilité dirigée (il suffit de vérifier tous les "mauvais" n -tuples possibles).$n$

Le problème de la circularité est difficile à résoudre. Supposons qu'on nous donne une instance 3SAT avec n variables → x et m clauses C 1 , … , C m . Nous pouvons supposer que n = m (ajouter des variables fictives) et que n est premier (sinon trouver un nombre premier entre n et 2 n en utilisant le test de primalité AKS et ajouter des variables et des clauses fictives).$n$$\vec{x}$$m$$C_1,\ldots,C_m$$n = m$$n$$n$$2n$

Considérons le langage suivant: "l'entrée n'est pas de la forme → x 1 ⋯ → x n où → x i est une affectation satisfaisante pour C i ". Il est facile de construire un DFA O ( n 2 ) pour ce langage. Si la langue n'est pas circulaire, alors il y a un mot w dans la langue, dont une puissance n'est pas dans la langue. Puisque les seuls mots qui ne sont pas dans la langue ont une longueur n 2 , w doit être de longueur 1 ou n . S'il est de longueur$\vec{x}_1 \cdots \vec{x}_n$$\vec{x}_i$$C_i$$O(n^2)$$w$$n^2$$w$$1$$n$1 , considéronsplutôt w n (il est toujours dans la langue), de sorte que w soit dans la langue et w n ne soit pas dans la langue. Le fait que w n ne soit pas dans la langue signifie que w est une affectation satisfaisante.$1$$w^n$$w$$w^n$$w^n$$w$

Inversement, toute affectation satisfaisante se traduit par un mot prouvant la non-circularité de la langue: l'affectation satisfaisante w appartient à la langue mais pas w n . Ainsi, le langage est circulaire si l'instance 3SAT n'est pas satisfaisante.$w$$w^n$

Dans cette partie, nous discutons d'une forme normale pour les langues circulaires. Songez à certaines DFA pour une langue circulaire L . Une séquence C = C 0 , … est réelle si C 0 = s (l'état initial), tous les autres états acceptent, et C i = C j implique C i + 1 = C j + 1 . Ainsi, chaque séquence réelle est finalement périodique, et il n'y a qu'un nombre fini de séquences réelles (puisque le DFA a un nombre fini d'états).$L$$C = C_0,\ldots$$C_0 = s$$C_i = C_j$$C_{i+1} = C_{j+1}$

On dit qu'un mot se comporte selon $C$ si le mot prend le DFA de l'état c i à l'état c i + 1 , pour tout i . L'ensemble de tous ces mots E ( C ) est régulier (l'argument est similaire à la première partie de cette réponse). On notera que E ( C ) est un sous - ensemble de L .$c_i$$c_{i+1}$$i$$E(C)$$E(C)$$L$

Étant donné une séquence C réelle , définissez C k comme étant la séquence C k ( t ) = C ( k t ) . La séquence C k est également réelle. Puisqu'il n'y a qu'un nombre fini de séquences différentes C k , le langage D ( C ) qui est l'union de tous E ( C k ) est également régulier.$C$$C^k$$C^k(t) = C(kt)$$C^k$$C^k$$D(C)$$E(C^k)$

Nous affirmons que D ( C ) a la propriété que si x , y ∈ D ( C ) alors x y ∈ D ( C ) . En effet, supposons que x ∈ C k et y ∈ C l . Alors x y ∈ C k + l . Ainsi D ( C ) = D ( C ) + peut s'écrire sous la forme $D(C)$$x,y \in D(C)$$xy \in D(C)$$x \in C^k$$y \in C^l$$xy \in C^{k+l}$$D(C) = D(C)^+$+ pour une expression régulière r .$r^+$$r$

Chaque mot w dans les correspond linguistiques dans une certaine séquence réelle C , autrement dit , il existe une véritable séquence C que w se comporte selon l' une . Ainsi L est l'union de D ( C ) sur toute la séquence réelle C . Par conséquent, chaque langage circulaire a une représentation de la forme ∑ r + i . Inversement, chacune de ces langues est circulaire (trivialement).$w$$C$$C$$w$$L$$D(C)$$C$$\sum r_i^+$

Considérez le langage circulaire L de tous les mots sur a , b qui contiennent soit un nombre pair, soit un ou un nombre pair de b (ou les deux). Nous montrons qu'elle ne peut pas s'écrire comme une somme disjointe ∑ r + i ; par "disjoint", nous voulons dire que r + i ∩ r + j = ∅ .$L$$a,b$$a$$b$$\sum r_i^+$$r_i^+ \cap r_j^+ = \varnothing$

Soit N i la taille de certains DFA pour r + i , et N > max N i un entier impair . Considérons x = a N b N ! . Puisque x ∈ L , x ∈ r + i pour certains i . Par le lemme de pompage, on peut pomper un préfixe de x de longueur au plus N . Ainsi r + i génère z = a N $N_i$$r_i^+$$N > \max N_i$$x = a^N b^{N!}$$x \in L$$x \in r_i^+$$i$$x$$N$$r_i^+$b N ! . De même, y = a N ! b N est généré par certains r + j , ce qui génère également z . Notez que i ≠ j depuis x y ∉ L . La représentation ne peut donc pas être disjointe.$z = a^{N!} b^{N!}$$y = a^{N!} b^N$$r_j^+$$z$$i \neq j$$xy \notin L$

Voici quelques articles qui traitent de ces langues:

Thierry Cachat, Le pouvoir des langages rationnels à une lettre, DLT 2001, Springer LNCS # 2295 (2002), 145-154.

S. Hovath, P. Leupold et G. Lischke, Roots and powers of regular languages, DLT 2002, Springer LNCS # 2450 (2003), 220-230.

H. Bordihn, Context-freeness of the power of context-free languages ​​is indecidable, TCS 314 (2004), 445-449.

@Dave Clarke, L = a * | b * serait circulaire, mais L * serait (a | b) *.

En termes de décidabilité, un langage L est circulaire s'il existe un L ' tel que L est la fermeture sous + de L ' ou s'il s'agit d'une union finie de langages circulaires.$L$$L'$$L$$L'$

(Je meurs d'envie de redéfinir "circulaire" en remplaçant votre > par ≥ . Cela simplifie beaucoup les choses. On peut alors caractériser les langues circulaires comme celles pour lesquelles il existe un NDFA dont l'état de départ n'a que des transitions epsilon pour accepter des états et a une transition epsilon vers chaque état acceptant).$>$$\ge$

Modifier: Une preuve complète (simplifiée) d'exhaustivité de PSPACE apparaît ci-dessous.

Deux mises à jour. Premièrement, la forme normale décrite dans mon autre réponse apparaît déjà dans un article de Calbrix et Nivat intitulé Prefix and period languages ​​of rational ω -langauges$\omega$ , malheureusement non disponible en ligne.

Deuxièmement, décider si une langue est circulaire étant donné que son DFA est PSPACE-complete.

Circularité dans PSPACE. Puisque NPSPACE = PSPACE par le théorème de Savitch, il suffit de donner un algorithme NPSPACE pour la non-circularité. Soit A = ( Q , Σ , δ , q 0 , F ) un DFA avec | Q | = n états. Le fait que le monoïde syntaxique de L ( A ) ait une taille au plus n n implique que si L ( A ) n'est pas circulaire alors il y a un mot w de longueur au plus n $A = (Q,\Sigma,\delta,q_0,F)$$|Q|=n$$L(A)$$n^n$$L(A)$$w$$n^n$ such that $w \in L(A)$ but $w^k \notin L(A)$ for some $k \leq n$. The algorithm guesses $w$ and computes $\delta_w(q) = \delta(q,w)$ for all $q \in Q$, using $O(n\log n)$ space (used to count up to $n^n$). It then verifies that $\delta_w(q_0) \in F$ but $\delta_w^{(k)} \notin F$ for some $k \leq n$.

Circularity is PSPACE-hard. Kozen showed in his classic 1977 paper Lower bounds for natural proof systems that it is PSPACE-hard to decide, given a list of DFAs, whether the intersection of the languages accepted by them is empty. We reduce this problem to circularity. Given binary DFAs $A_1,\ldots,A_n$, we find a prime $p \in [n,2n]$ and construct a ternary DFA $A$ accepting the language

Every $s \in L$ of length $p>0$ can be written as $xy^{i}z$ where $x = z = \epsilon$ , $y = w \neq \epsilon$ . It's obvious that $|xy| \leq p$ and $|y| = |w| > 0$. It follows that the language is regular for non-empty inputs, by the pumping lemma.

For $w= \epsilon$ , the definition holds, since a NDFA that accepts the empty string will also accept any number of empty strings.

The union of the above languages is the language L and since regular languages are closed under union, it follows that every circular language is regular.

By Rice's theorem, $CIRCULARITY/TM$ is undecidable. The proof is similar to regularity.