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

20

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:wwΣΣ

ww appartient à L si et seulement si pour tous les entiers , appartient à L.k > 0 w kk>0wk

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

vincenzoml
la source
1
C'est une question très intéressante. Deux questions liées: 1) si nous avons un langage régulier L et un DFA associé, pouvons-nous le rendre circulaire? 2) Étant donné un langage L, est-ce que circ (L) est régulier ou possède de belles propriétés?
Suresh Venkat
ps c'est peut-être évident, mais pourquoi pensez-vous que les langues circulaires sont une sous-classe des langues régulières?
Suresh Venkat
3
@Suresh, je pense qu'il définit un langage comme circulaire s'il est a) régulier; b) satisfait à une propriété de fermeture j L , n N : w nLwL,nN:wnL .
Peter Taylor
Crosspost au MO .
Hsien-Chih Chang 張顯 之
1
Peut-être que les remerciements ne devraient pas être affichés, mais c'était ma première question et j'ai beaucoup apprécié la qualité des commentaires, des réponses et des discussions. Merci.
vincenzoml

Réponses:

19

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+rr+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".rir+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.nn

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 nws0s1,,sns1s0,,snw- 1 à s 1 ,, s n s 1 accepte mais que l'un des autres n'accepte pas. Inversement, si la langue est circulaire, cela ne peut pas se produire.s0,,sn1s1,,sns1

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).nx⃗ mC1,,Cmn=mnn2n

Considérons le langage suivant: "l'entrée n'est pas de la forme x 1x nx 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 longueurx⃗ 1x⃗ nx⃗ iCiO(n2)wn2w1n1 , 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.1wnwwnwnw

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.wwn


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).LC=C0,C0=sCi=CjCi+1=Cj+1

On dit qu'un mot se comporte selon CC 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 .cici+1iE( 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.CCkCk( t ) = C( k t )CkCkD ( C)E( Ck)

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 rD ( C)x , yD ( C)x yD ( C)x CkyClx yCk+lD(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).wCCwLD(C)Cr+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 + ir + j = .La,babr+ir+ir+j=

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 !Nir+iN>maxNix=aNbN!xLxr+iixNr+ib 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=aN!bN!y=aN!bNr+jzijxyL

Yuval Filmus
la source
Il semble y avoir un certain nombre d'erreurs ici. Vous réduisez UNSAT, pas SAT, donc vous montrez que c'est coNP-dur. Quel est votre témoin polynomial pour (non) -adhésion?
Mark Reitblatt
"Puisque les seuls mots qui ne sont pas dans la langue ont une longueur n 2 " Ne devrait-ce pas être n m ? n2nm
Mark Reitblatt
Je ne pense pas que ce soit "trivialement en coNP". Au moins, ce n'est pas trivialement évident pour moi. Le certificat "évident" serait une chaîne l dans la langue, et une puissance k telle que l k ne soit pas dans la langue. Mais il n'est pas immédiatement évident pour moi pourquoi un tel mot doit être de taille polynomiale. C'est peut-être par un simple fait de la théorie des automates que j'écarte. lklk
Mark Reitblatt
Un défaut apparent encore plus grave est que vous sautez de chaque clause étant satisfiable individuellement à la formule entière étant satisfiable. Sauf si je fais une mauvaise lecture, bien sûr.
Mark Reitblatt
Je suis d'accord qu'il n'est pas clair que la circularité est en coNP. D'un autre côté, je ne vois aucun problème dans le reste de l'argument (maintenant que j'ai mis n = m ). Si chaque clause est satisfaite par la même assignation, alors l'instance 3SAT est satisfaite par cette assignation. n=m
Yuval Filmus
17

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.

Jeffrey Shallit
la source
6

@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.LLLL

(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).>

Peter Taylor
la source
Tu as raison. J'ai supprimé mon message incorrect.
Dave Clarke
Concernant l'adaptation avec : Je pense qu'un DFA minimal devrait toujours avoir exactement un état d'acceptation, à savoir l'état de départ. Peut-être que plus d'états acceptants peuvent arriver, mais ils ont alors besoin d'une transition ε vers l'état de départ. ε
Raphael
1
@Raphael, considérons à nouveau L = a * | b *. Un DFA dont l'état de départ est le seul état acceptant et qui accepte a et b doit accepter (a | b) *.
Peter Taylor
Sur la question de la décidabilité, encore une fois: supposons que vous ayez un DFA avec n états dont n a accepte. Supposons qu'il accepte un mot w , et accepte également w 2 , w 3 , ..., w n a + 1 . Ensuite, il accepte w x pour x > 0 . (La preuve est une application simple du principe du pigeonnier). S'il est possible de montrer que le contre-exemple minimal (minimisant | w | ) ( w , xnnaww2w3wna+1wxx>0|w|wx) à la circularité du langage accepté par le DFA a une longueur limitée par une fonction de n alors des tests de force brute sont possibles. Je soupçonne que | w | < = n + 1 , mais je ne l'ai pas prouvé. n|w|<=n+1
Peter Taylor
Pour donner suite à l'idée de @ Raphael ci-dessus. L'idée de l'état de départ = accepter uniquement l'état est incorrecte pour ce problème, mais elle capture une propriété intéressante. Lorsque M est un minDFA, l'état de départ est le seul état accepté si et seulement si L (M) est l'étoile Kleene d'un langage sans préfixe. Ceci est l'un de mes morceaux de trivia DFA préférés et je suis donc rapide à le partager! ;)
mikero
5

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ω , 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 nA=(Q,Σ,δ,q0,F)|Q|=nL(A)nnL(A)wnn such that wL(A) but wkL(A) for some kn. The algorithm guesses w and computes δw(q)=δ(q,w) for all qQ, using O(nlogn) space (used to count up to nn). It then verifies that δw(q0)F but δ(k)wF for some kn.

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 A1,,An, we find a prime p[n,2n] and construct a ternary DFA A accepting the language L(A)=¯{2w12w22wp:wiL(A1+(imodn))}.

(With some more effort, we can make A binary as well.) It is not difficult to see (using the fact that p is prime) that L(A) is circular if and only if the intersection L(A1)L(An) is empty.
Yuval Filmus
la source
0

Every sL of length p>0 can be written as xyiz where x=z=ϵ , y=wϵ . It's obvious that |xy|p and |y|=|w|>0. It follows that the language is regular for non-empty inputs, by the pumping lemma.

For w=ϵ , 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.

chazisop
la source
1
The pumping lemma is a necessary, but not sufficient, condition for regularity. In particular, there are nonregular languages satisfying the pumping condition. Also, Rice's theorem would say that {M|L(M) is circular} is undecidable. This does not mean that {D|L(D) is circular} is undecidable (where D is a DFA, M a TM)! For instance, emptiness testing for DFAs is decidable, while emptiness testing for TMs is not.
alpoge
1
Here's a non-computable circular language. Let D={0x1:xR}, where R is some non-computable language (e.g. codes of halting TMs). Then D is circular but clearly non-computable (an oracle for D can be used to decide R).
Yuval Filmus
2
@Peter, have you read this answer? It was trying to prove that any circular language (without the condition of regularity) is regular.
Yuval Filmus
1
@Yuval, my mistake. @chazisop, the pumping lemma is useful for proving non-regularity of languages, but not regularity. (Besides, the assertion of your first sentence reduces to "Every sL of length p>0 can be written as yi where yϵ", which is clearly false).
Peter Taylor
1
Yes, I use CIRCULARITY/TM to refer to this. CIRCULARITY/DFA is probably decidable.
chazisop