Ist die Menge aller primitiven Wörter eine primäre Sprache?

17

Ein Wort w heißt primitiv , wenn es kein Wort v und k>1 so dass w=vk . Die Menge Q aller primitiven Wörter über einem Alphabet Σ ist eine bekannte Sprache. WLOG können wir wählen Σ={a,b} .

Eine Sprache L ist Primzahl , wenn für jede Sprache A und B mit L=AB haben wir A={ϵ} oder B={ϵ} .

Ist Q prime?

Mit Hilfe eines SAT - Solver ich zeigen konnte , dass wir entweder {a,b}A oder {a,b}B als sonst {ababa,babab}Q kann nicht faktorisierenden in A und B stecken aber seitdem fest.

Henning
quelle

Antworten:

13

Die Antwort ist ja. Angenommen , wir haben eine Faktorisierung Q=AB .

Eine einfache Beobachtung ist, dass A und B disjunkt sein müssen (da wir für wABw2Q ). Insbesondere kann nur eines von A,Bϵ enthalten . Wir können davon ausgehen , oBdA (da der andere Fall völlig symmetrisch ist) , dass ϵB . Dann, da a und b nicht in nicht leere Faktoren zerlegt werden können, müssen wir a,bA .

Als nächstes erhalten wir, dass ambnA (und ganz analog bmanA ) für alle m,n>0 durch Induktion auf m :

Für m=1 müssen wir , da abnQ , abn=uv mit uA,vB . Da uϵ , muss v für einige k n bk . Aber wenn k > 0 ist , dann erhalten wir, da b A ist , b 1 + kQ , einen Widerspruch. Soknk>0bAb1+kQv=ϵ undabnA .

Für den induktiven Schritt, da am+1bnQ haben wir am+1bn=uv mit uA,vB . Da wieder uϵ haben wir entweder v=akbn für einige 0<k<m+1 oder v=bk für einige k<n . Aber im ersteren Fall istv nach der Induktionshypothesebereits inA , so dassv2Q Widerspruch ist. Im letzteren Fall müssen wirk=0 (dhv=ϵ ), dawirvonbAb1+kQ . Sou=am+1bnA .

Betrachten wir nun den allgemeinen Fall von primitiven Wörtern mit r Abwechslungen zwischen a und b , dh w ist entweder am1bn1amsbns , bm1an1bmsans (für r=2s1 ), am1bn1ams+1 oderbm1an1bms+1 (fürr=2s); wir können zeigen, dass sie alle inAindemwirInduktion aufr. Was wir bisher gemacht haben, betraf die Basisfäller=0undr=1.

Für r>1 wir eine andere Induktion für m1 , die in etwa so funktioniert wie die für r=1 oben:

Wenn m1=1 , dann ist w=uv mit uA,vB , und da uϵ , hat v weniger als r Wechsel. Also ist v (oder seine Wurzel, falls v selbst nicht primitiv ist) nach der Induktionshypothese für r in A für einen Widerspruch wie oben, es sei denn, v = ϵ . So w = u A .rv=ϵw=uA

Wenn m1>1 in jeder Faktorisierung w=uv mit uϵ , v entweder hat weniger Alternationen (und seine Wurzel ist in A außer wenn v=ϵ durch die Induktions Hypothese auf r ) oder einem kürzeren ersten Block (und ihre Wurzel ist in A, es sei denn, v=ϵ nach der Induktionshypothese zu m1 ). In jedem Fall bekommen wir , dass wir müssen v=ϵ , dh w=uA .


Q:=Q{ϵ}Q=ABABQAB={ϵ}a,bAB

abaAbBwQw=uvuA{ϵ}vB{ϵ}baAB

  • baAababa,aBabaAababABabaBbabAbababaABBababABbababbabABabab,bababababAabaB(ba)4ABbababBaA(ab)3ABbababAB
  • baBbabBAabaABababaAB

Ich bin mir derzeit nicht sicher, wie ich darüber hinaus vorgehen soll. Es wäre interessant zu sehen, ob das obige Argument systematisch verallgemeinert werden kann.

Klaus Draeger
quelle
Wow, du hast meinen Respekt. Ich werde es heute oder morgen später durchgehen, da ich momentan keine Zeit habe, aber ernsthaft beeindruckt bin :) Es hat ein paar Stunden gedauert, bis ich herausgefunden habe, dass {a, b} in A sind, aber ich habe es nicht ausgenutzt Das ist kein primitives Wort. Wie sind Sie an dieses Problem herangegangen (oder haben Sie es einfach gemacht?)? Wie lange haben Sie gebraucht, um diesen Beweis zu erbringen?
Henning
Aϵ,abanbnab,abb,abbb,
4
Q{ϵ}
1
Gute Frage! Ich muss mich in diesem Fall bei Ihnen melden.
Klaus Draeger
2
Danke für die Kommentare und entschuldige die Verspätung. Der Fall, in dem wir das leere Wort einfügen möchten, scheint komplizierter zu sein (siehe Update).
Klaus Draeger