Uma classe especial de idiomas: idiomas "circulares". Isso é conhecido?

20

Defina a seguinte classe de idiomas "circulares" sobre um alfabeto finito Sigma. Na verdade, o nome já existe para denotar uma coisa diferente que parece, usada no campo da computação de DNA. AFAICT, essa é uma classe de idiomas diferente.

Uma linguagem L é circular se, para todas as palavras ww em Σ Σ , temos:

ww pertence a L se e somente se para todos os números inteiros k > 0k>0 , w kwk pertence a L.

Essa classe de idiomas é conhecida? Estou interessado nas linguagens circulares, que também são regulares e, em particular, em:

  • um nome para eles, se eles já são conhecidos

  • a decidibilidade do problema, dado um autômato (em particular: um DFA), se o idioma aceito obedece à definição acima

vincenzoml
fonte
1
Esta é uma questão muito interessante. Duas questões relacionadas: 1) se temos um idioma regular L e um DFA associado, podemos torná-lo circular? 2) Dada qualquer linguagem L, é verdade que circ (L) é regular ou possui boas propriedades?
Suresh Venkat
ps Talvez isso seja óbvio, mas por que você acha que as linguagens circulares são uma subclasse das linguagens regulares?
Suresh Venkat
3
@Suresh, acho que ele está definindo uma linguagem para ser circular se for a) regular; b) satisfaz uma propriedade de fecho w L , n N : w nLwL,nN:wnL .
Peter Taylor
Crosspost em MO .
Hsien-Chih Chang
1
Talvez não deva postar agradecimentos, mas essa foi minha primeira pergunta e apreciei muito a qualidade dos comentários, respostas e discussão. Obrigado.
precisa saber é o seguinte

Respostas:

19

Na primeira parte, mostramos um algoritmo exponencial para decidir a circularidade. Na segunda parte, mostramos que esse é um problema coNP. Na terceira parte, mostramos que toda linguagem circular é uma união de linguagens da forma r + (aqui r pode ser o regexp vazio); a união não é necessariamente disjunta. Na quarta parte, exibimos uma linguagem circular que não pode ser escrita como uma soma disjunta r + i .r+rr+Eu

Editar: Incorporadas algumas correções após os comentários de Marcos. Em particular, minhas afirmações anteriores de que a circularidade é coNP-completa ou NP-difícil são corrigidas.

Editar: Corrigida a forma normal de r i a r + i . Exibiu uma linguagem "inerentemente ambígua".rEur+Eu


Continuando o comentário de Peter Taylor, veja como decidir (extremamente ineficientemente) se um idioma é circular, considerando seu DFA. Construa um novo DFA cujos estados sejam n- pares dos estados antigos. Este novo DFA executa n cópias do DFA antigo em paralelo.nn

Se o idioma não for circular, haverá uma palavra w, de modo que, se o passarmos pelo DFA repetidamente, começando com o estado inicial s 0 , obteremos os estados s 1 , , s n de modo que s 1 esteja aceitando apenas um dos outros não está aceitando (se todos estão aceitando, então a sequência s 0 , , s n deve alternar para que w esteja sempre no idioma). Em outras palavras, temos um caminho de s 0 , , s nws0s1,,sns1s0 0, , SnW- 1 a s 1 ,, s n em que s 1 está aceitando, mas um dos outros não está aceitando. Por outro lado, se o idioma é circular, isso não pode acontecer.s0 0, , Sn - 1s1, , Sns1

Portanto, reduzimos o problema a um simples teste de acessibilidade direcionada (basta verificar todos os n- tufos possíveis "ruins" ).n


O problema da circularidade é difícil de coNP. Suponha que recebamos uma instância 3SAT com n variáveis x e m cláusulas C 1 , ... , C m . Podemos supor que n = m (adicione variáveis ​​fictícias) e que n seja primo (caso contrário, encontre um primo entre n e 2 n usando o teste de primalidade da AKS e adicione variáveis ​​e cláusulas fictícias).nx⃗ mC1, , Cmn = mnn2 n

Considere o seguinte idioma: "a entrada não possui a forma x 1x n onde x i é uma atribuição satisfatória para C i ". É fácil construir um O ( n 2 ) DFA para esse idioma. Se o idioma não for circular, haverá uma palavra w no idioma, cujo poder não está no idioma. Como as únicas palavras que não estão no idioma têm comprimento n 2 , w deve ter comprimento 1 ou n . Se for de comprimentox⃗ 1x⃗ nx⃗ EuCEuO ( n2)Wn2W1n1 , considere w n vez (ele ainda está no idioma), de modo que w é na linguagem e w n não está no idioma. O fato de que w n não está nos meios de linguagem que w é uma atribuição satisfatória.1WnWWnWnW

Por outro lado, qualquer atribuição satisfazer traduz em uma palavra comprovando a não circularidade da língua: a atribuição satisfazer w pertence à língua, mas w n não. Portanto, o idioma é circular se a instância 3SAT for insatisfatória.WWn


Nesta parte, discutimos uma forma normal para linguagens circulares. Considere algumas DFA para uma linguagem circular L . Uma sequência C = C 0 , ... é real se C 0 = s (o estado inicial), todos os outros estados estão aceitando, e C i = C j implica C i + 1 = C j + 1 . Assim, toda sequência real é eventualmente periódica, e há apenas muitas seqüências reais finitas (já que o DFA possui muitos estados finitos).euC= C0 0, C0 0= sCi=CjCi+1=Cj+1

Dizemos que uma palavra se comporta de acordo com CC se a palavra leva o DFA de estado c i para o estado c i + 1 , para todo i . O conjunto de todas essas palavras E ( C ) é regular (o argumento é semelhante à primeira parte desta resposta). Note-se que E ( C ) é um subconjunto de L .cici+1iE(C)E(C)L

Dada uma sequência real C , defina C k como a sequência C k ( t ) = C ( k t ) . A sequência C k também é verdadeiro. Desde há apenas finitamente muitos diferentes seqüências C k , a linguagem D ( C ) , que é a união de todos E ( C k ) também é regular.CCkCk(t)=C(kt)CkCkD(C)E(Ck)

Afirmamos que D ( C ) tem a propriedade de que se x , y D ( C ) então x y D ( C ) . De fato, suponha que x C k e y C l . Então x y C k + l . Assim, D ( C ) = D ( C ) + pode ser escrito na forma rD(C)x,yD(C)xyD(C)xCkyClxyCk+lD(C)=D(C)++ para alguma expressão regular r .r+r

Cada palavra w nos corresponde língua para alguma seqüência verdadeira C , ou seja, não existe uma verdadeira seqüência C que w se comporta de acordo com. Assim G é a união de D ( C ) sobre toda a sequência verdadeira C . Portanto, toda linguagem circular tem uma representação da forma r + i . Por outro lado, todo idioma é circular (trivialmente).wCCwLD(C)Cr+i


Considere a linguagem circular L de todas as palavras sobre a , b que contenham um número par ou a 's ou um número par de b ' s (ou ambos). Mostramos que não pode ser escrito como uma soma disjunta r + i ; por "disjunção" queremos dizer que r + ir + j = .La,babr+ir+ir+j=

Let NiNi be the size of the some DFA for r+ir+i, and N>maxNiN>maxNi be some odd integer. Consider x=aNbN!x=aNbN!. Since xLxL, xr+ixr+i for some ii. By the pumping lemma, we can pump a prefix of xx of length at most NN. Thus r+ir+i generates z=aN!bN!z=aN!bN!. Similarly, y=aN!bNy=aN!bN is generated by some r+jr+j, which also generates zz. Note that ijij since xyLxyL. Thus the representation cannot be disjoint.

Yuval Filmus
fonte
There seem to be a number of errors here. You're reducing from UNSAT, not SAT, so you're showing it's coNP-hard. What's your polynomial time witness for (non)-membership?
Mark Reitblatt
"Since the only words not in the language have length n2n2" Shouldn't that be nmnm?
Mark Reitblatt
I don't think it's "trivially in coNP". At least, it's not trivially obvious to me. The "obvious" certificate would be a string ll in the language, and a power kk such that lklk isn't in the language. But it's not immediately obvious to me why such a word must be polynomially-sized. Maybe it's by a simple fact of automata theory that I'm overlooking.
Mark Reitblatt
An even more serious apparent flaw is that you jump from each clause being satisfiable individually to the whole formula being satisfiable. Unless I am misreading, of course.
Mark Reitblatt
I agree that it's not clear that circularity is in coNP. On the other hand, I see no problems in the rest of the argument (now that I've put n=mn=m). If each clause is satisfied by the same assignment, then the 3SAT instance is satisfied by this assignment.
Yuval Filmus
17

Here are some papers that discuss these languages:

Thierry Cachat, The power of one-letter rational languages, DLT 2001, Springer LNCS #2295 (2002), 145-154.

S. Hovath, P. Leupold, and 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 undecidable, TCS 314 (2004), 445-449.

Jeffrey Shallit
fonte
6

@Dave Clarke, L = a*|b* would be circular, but L* would be (a|b)*.

In terms of decidability, a language LL is circular if there is an LL such that LL is the closure under + of LL or if it is a finite union of circular languages.

(I'm dying to redefine "circular" replacing your >> with . It simplifies things a lot. We can then characterise the circular languages as those for which there exists a NDFA whose starting state has only epsilon-transitions to accepting states and has an epsilon-transition to each accepting state).

Peter Taylor
fonte
You are right. I've removed my incorrect post.
Dave Clarke
Regarding adaption with : I am thinking that a minimal DFA should always have exactly one accepting state, namely the start state. Maybe more accepting states can happen, but then they need an εε-transition to the start state.
Raphael
1
@Raphael, consider again L = a*|b*. A DFA whose start state is the only accepting state and which accepts a and b must accept (a|b)*.
Peter Taylor
On the question of decidability, again: suppose you have a DFA with nn states of which nana are accepting. Suppose it accepts a word ww, and also accepts w2w2, w3w3, ..., wna+1wna+1. Then it accepts wxwx for x>0x>0. (Proof is a straightforward application of the pigeonhole principle). If it's possible to show that the minimal (minimising |w||w|) counterexample (ww, xx) to the circularity of the language accepted by the DFA has length bounded by a function of nn then brute force testing is possible. I suspect that |w|<=n+1|w|<=n+1, but I haven't proved it.
Peter Taylor
To follow up on @Raphael's idea above. The idea of start state = only accept state is wrong for this problem, but it does capture some interesting property. When M is a minDFA, the start state is the only accept state if and only if L(M) is the Kleene star of a prefix-free language. This is one of my favorite DFA trivia tidbits and thus I am quick to share it! ;)
mikero
5

Edit: A complete (simplified) PSPACE-completeness proof appears below.

Two updates. First, the normal form described in my other answer appears already in a paper by Calbrix and Nivat titled Prefix and period languages of rational ωω-langauges, unfortunately not available online.

Second, deciding whether a language is circular given its DFA is PSPACE-complete.

Circularity in PSPACE. Since NPSPACE=PSPACE by Savitch's theorem, it is enough to give an NPSPACE algorithm for non-circularity. Let A=(Q,Σ,δ,q0,F)A=(Q,Σ,δ,q0,F) be a DFA with |Q|=n|Q|=n states. The fact that the syntactic monoid of L(A)L(A) has size at most nnnn implies that if L(A)L(A) is not circular then there is a word ww of length at most nnnn such that wL(A)wL(A) but wkL(A)wkL(A) for some knkn. The algorithm guesses ww and computes δw(q)=δ(q,w)δ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
fonte
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
fonte
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