O conjunto de todas as palavras primitivas é um idioma principal?

Uma palavra é chamada primitiva , se não houver palavra e modo que . O conjunto de todas as palavras primitivas sobre um alfabeto é uma linguagem bem conhecida. WLOG, podemos escolher .$w$$v$$k > 1$$w = v^k$$Q$$\Sigma$$\Sigma = \{ a,b \}$

Um idioma é primo , se para todos os idiomas e com tivermos ou .$L$$A$$B$$L = A \cdot B$$A = \{\epsilon\}$$B = \{ \epsilon \}$

Q prime?

Com a ajuda de um solucionador SAT, eu poderia mostrar que temos ou , caso contrário não pode ser fatorado em e , mas ficaram presos desde então.$\{a,b\} \subseteq A$$\{a,b\} \subseteq B$$\{ ababa, babab \} \subset Q$$A$$B$

A resposta é sim. Suponha que temos um fatoração .$Q = A\cdot B$

Uma observação fácil é que e devem ser disjuntos (já que para obtemos ). Em particular, apenas um de pode conter . Podemos supor WLOG (uma vez que o outro caso é completamente simétrica) que . Em seguida, uma vez que e não podem ser tidos em conta factores não vazios, temos de ter .$A$$B$$w\in A\cap B$$w^2\in Q$$A,B$$\epsilon$$\epsilon\in B$$a$$b$$a,b\in A$

Em seguida, obtemos que (e, completamente analogamente, ) para todos por indução em :$a^mb^n\in A$$b^ma^n\in A$$m,n>0$$m$

Para , desde , que deve ter com . Como , deve ser para alguns . Mas se , desde que obtemos , contradição. Então , e . $m=1$$ab^n\in Q$$ab^n = uv$$u\in A, v\in B$$u\neq\epsilon$$v$$b^k$$k\le n$$k>0$$b\in A$$b^{1+k}\in Q$$v=\epsilon$$ab^n\in A$

Para o passo indutivo, uma vez que que tem com . Desde que novamente , temos para alguns , ou para alguns . Mas no primeiro caso, já está em pela hipótese de indução, então , contradição. Neste último caso, é preciso ter (isto é, ) uma vez que a partir de obtemos . Assim, .$a^{m+1}b^n\in Q$$a^{m+1}b^n = uv$$u\in A, v\in B$$u\neq\epsilon$$v = a^kb^n$$0<k<m+1$$v=b^k$$k<n$$v$$A$$v^2\in Q$$k=0$$v=\epsilon$$b\in A$$b^{1+k}\in Q$$u=a^{m+1}b^n\in A$

Agora considere o caso geral de palavras primitivas com alternações entre e , ou seja, é , (para ), ou (para ); podemos mostrar que eles estão todos em usando indução em . O que fizemos até agora cobriu os casos base e .$r$$a$$b$$w$$a^{m_1}b^{n_1}\ldots a^{m_s}b^{n_s}$$b^{m_1}a^{n_1}\ldots b^{m_s}a^{n_s}$$r=2s-1$$a^{m_1}b^{n_1}\ldots a^{m_{s+1}}$$b^{m_1}a^{n_1}\ldots b^{m_{s+1}}$$r=2s$$A$$r$$r=0$$r=1$

Para , usamos outra indução em , que funciona da mesma maneira que a de acima:$r>1$$m_1$$r=1$

Se , então com e, como , possui menos que alternâncias. Então (ou sua raiz no caso de não ser primitivo) está em pela hipótese de indução em para uma contradição como acima, a menos que . Então .$m_1=1$$w=uv$$u\in A, v\in B$$u\neq\epsilon$$v$$r$$v$$v$$A$$r$$v=\epsilon$$w=u\in A$

Se , em qualquer fatoração com , possui menos alternâncias (e sua raiz está em menos que pela hipótese de indução em ), ou um primeiro bloco mais curto (e sua raiz está em A, a menos que pela hipótese de indução em ). Em ambos os casos temos que devemos ter , ou seja, .$m_1>1$$w=uv$$u\neq\epsilon$$v$$A$$v=\epsilon$$r$$v=\epsilon$$m_1$$v=\epsilon$$w=u\in A$

O caso de é bastante mais complicado. O óbvio a ser observado é que, em qualquer decomposição , e devem ser subconjuntos de com . Além disso, deve ser contido em .$Q' := Q\cup\{\epsilon\}$$Q = A\cdot B$$A$$B$$Q'$$A\cap B = \{\epsilon\}$$a,b$$A\cup B$

Com um pouco de trabalho extra, pode-se mostrar que e devem estar no mesmo subconjunto. Caso contrário, assumir WLOG que e . Digamos que tenha uma fatoração adequada se com e . Temos duas subcasas (simétricas), dependendo de onde vai (deve estar em ou pois não possui fatoração adequada).$a$$b$$a\in A$$b\in B$$w\in Q'$$w=uv$$u\in A\setminus\{\epsilon\}$$v\in B\setminus\{\epsilon\}$$ba$$A$$B$

• Se , então não tem fatoração adequada desde . Desde implicaria , temos . Como conseqüência, não está em (o que implicaria ) nem em (o que implicaria ). Agora considere a palavra . Não possui fatoração adequada, já que e não são primitivos. Se , então desde temos$ba\in A$$aba$$ba,a\notin B$$aba\in A$$abab\in A\cdot B$$aba\in B$$bab$$A$$bababa\in A\cdot B$$B$$abab\in A\cdot B$$babab$$bab\notin A\cup B$$abab,baba$$babab\in A$$aba\in B$$(ba)^4\in A\cdot B$ ; se , em seguida, uma vez que chegarmos . Portanto, não há como ter , contradição.$babab\in B$$a\in A$$(ab)^3\in A\cdot B$$babab\in A\cdot B$
• O caso é completamente simétrico. Em poucas palavras: não possui fatoração adequada e não pode estar em , portanto deve estar em ; portanto não pode estar em ou ; portanto, não possui fatoração adequada, mas também não pode estar na contradição ou$ba\in B$$bab$$B$$A$$aba$$A$$B$$ababa$$A$$B$

Atualmente, não tenho certeza de como proceder além desse ponto; seria interessante ver se o argumento acima pode ser sistematicamente generalizado.