L'ensemble de tous les mots primitifs est-il une langue privilégiée?

17

Un mot ww est appelé primitif , s'il n'y a pas de mot vv et k > 1 dek>1 sorte que w = v kw=vk . L'ensemble de tous les mots primitifs sur un alphabet est une langue bien connue. WLOG nous pouvons choisir .Q QΣ ΣΣ = { a , b }Σ={a,b}

Un langage est premier , si pour chaque langue et avec nous avons ou .LLA AB BL = A B L=ABA = { ϵ } A={ϵ}B = { ϵ }B={ϵ}

Q prime?

Avec l'aide d'un solveur SAT, je pourrais montrer que nous avons soit ou , sinon ne peut pas être factorisé dans et , mais ont été bloqués depuis lors.{ a , b } A {a,b}A{ a , b } B {a,b}B{ a b a b a , b a b a b } Q {ababa,babab}QA ABB

Henning
la source

Réponses:

13

La réponse est oui. Supposons que nous ayons une factorisation Q = A BQ=AB .

Une observation facile est que AA et BB doivent être disjoints (puisque pour w A BwAB nous obtenons w 2Qw2Q ). En particulier, un seul de A , BA,B peut contenir ϵϵ . On peut supposer wlog (puisque l'autre cas est complètement symétrique) que e BϵB . Ensuite , depuis una et bb ne peuvent pas être pris en compte dans les facteurs non vides, nous devons avoir un , b Aa,bA .

On obtient ensuite que a m b nAambnA (et, de façon tout à fait analogue, b m a nAbmanA ) pour tout m , n > 0m,n>0 par induction sur mm :

Pour m = 1m=1 , depuis un b nQabnQ , il faut avoir un b n = u vabn=uv avec u A , v BuA,vB . Puisque u ϵuϵ , vv doit être b kbk pour certains k nkn . Mais si k > 0k>0 , alors puisque b AbA on obtient b 1 + kQb1+kQ , contradiction. Doncv = εv=ϵ , et un b nAabnA .

Pour l'étape d' induction, depuis une m + 1 b nQam+1bnQ , nous avons un m + 1 b n = u vam+1bn=uv avec u A , v BuA,vB . Depuis encore u ϵuϵ , on a soit v = a k b nv=akbn pour quelque 0 < k < m + 10<k<m+1 , soit v = b kv=bk pour certains k <nk<n . Mais dans le premier cas, vv est déjà dans AA par l'hypothèse d'induction, donc v 2Qv2Q , contradiction. Dans ce dernier cas, il faut avoir k = 0k=0 (ie v = εv=ϵ ) étant donnéde b AbA nous obtenons b 1 + kQb1+kQ . Alors u = a m + 1 b nAu=am+1bnA .

Considérons maintenant le cas général des mots primitifs avec rr alternances entre aa et bb , c'est-à-dire que ww est soit a m 1 b n 1a m s b n sam1bn1amsbns , b m 1 a n 1b m s a n sbm1an1bmsans (pour r = 2 s - 1r=2s1 ), a m 1 b n 1a m s+ 1am1bn1ams+1 , oub m 1 a n 1b m s + 1bm1an1bms+1 (pourr=2sr=2s); nous pouvons montrer qu'ils sont tous dansA enAutilisant l'induction surrr. Ce que nous avons fait jusqu'à présent a couvert les cas de baser=0r=0etr=1r=1.

Pour r > 1r>1 , nous utilisons une autre induction sur m 1m1 , qui fonctionne à peu près de la même manière que celle pour r = 1r=1 ci-dessus:

Si m 1 = 1m1=1 , alors w = u vw=uv avec u A , v BuA,vB , et puisque u ϵuϵ , vv a moins de rr alternances. Donc vv (ou sa racine dans le cas où vv lui-même n'est pas primitif) est dans AA par l'hypothèse d'induction sur rr pour une contradiction comme ci-dessus à moins que v = ϵv=ϵ . Donc w = u Aw=uA .

Si m 1 > 1m1>1 , dans toute factorisation w = u vw=uv avec u ϵuϵ , vv soit a moins d'alternances (et sa racine est en AA sauf si v = ϵv=ϵ par l'hypothèse d'induction sur rr ), soit un premier bloc plus court (et son racine est en A sauf si v = ϵv=ϵ par l'hypothèse d'induction sur m 1m1 ). Dans les deux cas nous obtenons que nous devons avoir v = εv=ϵ , soit w = u Aw=uA .


Le cas de Q : = Q { ϵ }Q:=Q{ϵ} est un peu plus compliqué. Les choses évidentes à noter sont que dans toute décomposition Q = A BQ=AB , AA et BB doivent être des sous-ensembles de Q Q avec A B = { ϵ }AB={ϵ} . En outre, un , ba,b doit être contenue dans A de BAB .

Avec un peu de travail supplémentaire, on peut montrer que aa et bb doivent être dans le même sous-ensemble. Dans le cas contraire, supposons que wlog a AaA et b BbB . Disons que w Q wQ a une factorisation correcte si w = u vw=uv avec u A { ϵ } et v B { ϵ } . Nous avons deux sous-cas (symétriques) selon où va b a (il doit être enA or B since it has no proper factorization).

  • If baA, then aba has no proper factorization since ba,aB. Since abaA would imply ababAB, we get abaB. As a consequence, bab is neither in A (which would imply bababaAB) nor in B (which would imply ababAB). Now consider the word babab. It has no proper factorization since babAB and abab,baba are not primitive. If bababA, then since abaB we get (ba)4AB; if bababB, then since aA we get (ab)3AB. So there is no way to have bababAB, contradiction.
  • The case baB is completely symmetric. In a nutshell: bab has no proper factorization and cannot be in B, so it must be in A; therefore aba cannot be in A or B; therefore ababa has no proper factorization but also cannot be in either A or B, contradiction.

I am currently not sure how to proceed beyond this point; it would be interesting to see if the above argument can be systematically generalized.

Klaus Draeger
la source
Wow, you have my respect. I'll go through it later today or tomorrow as I don't have time right now, but I am seriously impressed :) It took me a few hours to get that {a, b} are in A but I didn't exploit that \epsilon is not a primitive word. How did you approach this problem (or was it "just do it"?)? How long did it take you to come up with that proof?
Henning
Thanks! I got the main idea (showing that any nonempty proper suffix of words must be in A) by thinking about what happens to some "simple" words. ϵ,a, and b were relatively straightforward, an or bn were out of the question, and considering ab,abb,abbb, got me on the right path.
Klaus Draeger
4
Your proof is beautiful and not as hard as I thought (I feel quite stupid now, I spent some time thinking about it). However it seems to heavily relay on epsilon not being element of Q. Is Q{ϵ} also prime?
Henning
1
Good question! I'll have to get back to you on that one.
Klaus Draeger
2
Thanks for the comments, and sorry for the delay. The case where we want to include the empty word seems to be more complicated, see update.
Klaus Draeger