Primitive ord

I teoretisk informatikk , i kombinatorikk og spesielt i kombinatorikk av ord , er et primitivt ord et ord som ikke er kraften til et annet ord. For eksempel, abbaer et primitivt ord og ababer ikke primitivt siden det er kvadratet av ordet ab. Primitive ord er på en måte den kombinatoriske ekvivalenten til primtall i aritmetikk . De primitive ordene griper inn i forskjellige felt, som ligningene mellom ordene , ordene til Lyndon , de formelle språkene . De er relatert til halskjeder eller sirkulære ord . Et primitivt ord kalles også aperiodisk .

Definisjon

Et ord i et alfabet er primitivt hvis det ikke er kraften til et annet ord, derfor hvis det ikke finnes et ord som for et positivt naturlig tall. Ordet tomt er ikke primitivt. $x$ $PÅ$ $y \ ne x$ $x = y ^ {n}$ $ikke$

For et alfabet med to bokstaver er de første primitive ordene: ${\ displaystyle a, b,}$

{\ displaystyle a, b, ab, ba, aab, aba, abb, baa, bab, bba, aaab, \ ldots}

Eiendommer

Unikt

Følgende egenskaper finnes i lærebøker, for eksempel de fra Lothaire eller Shallit

Eiendom 1 - Ethvert ord er unikt skrevet som kraften til et primitivt ord.

Noen ganger finner vi navnet "rot" for å betegne det unike primitive ordet som er en kraft; det er også bemerket . Heltallet slik som er "eksponenten" av . For eksempel for , og med eksponent 3. Eiendommen er bevist ved hjelp av lemmaet nedenfor. $x$ $x$ ${\ sqrt x}$ $ikke$ ${\ displaystyle x = {\ sqrt {x}} ^ {n}}$ $x$ ${\ displaystyle x = ababab}$ ${\ displaystyle {\ sqrt {x}} = ab}$ ${\ displaystyle x = (ab) ^ {3}}$

Eiendom 2 - Konjugatene til et primitivt ord er i seg selv primitive.

Ta for eksempel . Dens konjugater er ${\ displaystyle x = abaab}$

abaab, baaba, aabab, ababa, babaa

De er alle primitive.

Eiendom 3 - Bøyningsklassen til et primitivt ord med lengde har elementer. $ikke$ $ikke$

Antall primitive ord

Da konjugatene til et primitivt ord alle er forskjellige, for hvis det var to like, ville de verifisere en ligning som er beskrevet i lemmaet nedenfor, og ville være krefter for et tredje ord, derfor skrivere. Bøyningsklassen til et primitivt ord, eller tilsvarende det sirkulære ordet som er knyttet til det ordet, kalles et aperodisk halskjede . Antall aperiodiske halskjeder med lengde , derfor er antall konjugasjonsklasser av primitive ord med lengde n på et alfabet med k bokstaver $ikke$

M_k (n) = {1 \ over n} \ sum_ {d \ mid n} \ mu (d) k ^ {n / d}

Her er Möbius-funksjonen . Siden konjugatene til et primitivt ord alle er primitive og forskjellige, er antallet primitive ord med lengde n i et alfabet med k bokstaver $\ mu$

{\ displaystyle nM_ {k} (n) = \ sum _ {d \ mid n} \ mu (d) k ^ {n / d}}

Funksjonene kalles også polynomene til krage (i variabelen ), og formelen tilskrives oberst Moreau . For følgende er oppfølgeren A001037 til OEIS . For og er de aperiodiske binære krager henholdsvis 001,011 og 0001,0011,0111. $M_k (n)$ $k$ $k = 2$ $M_k (n)$ $n = 3$ $n = 4$

Tallet er antall Lyndon-ord med lengde på bokstaver. Enhver klassekonjugasjon av et primitivt ord inneholder et enkelt element som er mindre enn det andre i en leksikografisk rekkefølge , og det er det eneste ordet Lyndon i klassen, slik at Lyndons ord danner et system av representanter for klassene med primitive ord eller aperiodiske halskjeder. $M_k (n)$ $ikke$ $k$

Lyndon og Schützenberger teorem

Eiendom 4 - Hvis og er to forskjellige primitive ord, så er det et primitivt ord for alt . Dessuten er høyst et av ordene for ikke primitivt. $x$ $y$ ${\ displaystyle x ^ {n} y ^ {m}}$ ${\ displaystyle n, m \ geq 2}$ ${\ displaystyle x ^ {n} y ^ {m}}$ ${\ displaystyle n, m \ geq 1}$

Den første delen av denne eiendommen er faktisk en omskrivning av setningen til Lyndon og Schützenberger som sier at hvis for , så og har samme rot. Dette gjelder ikke lenger hvis eller . Så for og ordet er et kvadrat. Den andre delen av uttalelsen sier at høyst et av ordene eller ikke er primitive. Hvis og er av samme lengde, er det eneste mulig ordet som er preget . For eksempel hvis og , da . Vi kan vise at hvis det er skrevet ut, generelt , med . Så, for og , vi har , og for , vi har . ${\ displaystyle x ^ {n} y ^ {m} = z ^ {p}}$ ${\ displaystyle n, m, p \ geq 2}$ $x, y$ $z$ $n = 1$ $m = 1$ ${\ displaystyle x = aba}$ ${\ displaystyle y = baab}$ ${\ displaystyle x ^ {2} y = abaababaab}$ ${\ displaystyle x ^ {n} y}$ ${\ displaystyle xy ^ {m}}$ $x$ $y$ $xy$ ${\ displaystyle x = aba}$ ${\ displaystyle y = bab}$ ${\ displaystyle xy = (ab) ^ {3}}$ ${\ displaystyle xy ^ {m}}$ ${\ displaystyle m \ leq M}$ ${\ displaystyle M = 2 + (| x | -2) / | y |}$ ${\ displaystyle x = aababa}$ $y = ab$ ${\ displaystyle M = 2 + (| x | -2) / | y | = 2 + (6-2) / 2 = 4}$ $m = 2$ ${\ displaystyle xy ^ {2} = (aabab) ^ {2}}$

Uten kant

Eiendom 5 - Et ord er primitivt hvis og bare hvis et av konjugatene er et grenseløst ord.

En kant av et ord er et ord som både er et ordentlig prefiks og et ordentlig suffiks av . Et ord uten grense er et ord som ikke har en ikke-tom kant. $w$ $w$

Demonstrasjon

Hvis ikke er primitiv, derfor av form for , så er det en kant av , og alle konjugatene til er krefter av et konjugat av , så alle har en kant. $w$ ${\ displaystyle w = y ^ {n}}$ $n \ ge2$ $y$ $w$ $w$ $w$

Anta nå som er primitiv, og er den minste av konjugatene i en fast leksikografisk rekkefølge . Vi viser at det er grenseløst. Antag tvert imot at det har en kant . Så for nonempty, og er ikke tom ellers (og derfor ) er en firkant. Ordet er et konjugat av og derfor av . Hvis , da , derfor og er minst en kube av lemmaet nedenfor. Derfor i det minste , derfor også . Men da , og er et konjugat av mindre enn , motsier hypotesen. $w$ $x$ $w$ $x$ $x$ $u$ ${\ displaystyle x = uvu}$ $u$ $v$ $x$ $w$ ${\ displaystyle z = uuv}$ $x$ $w$ ${\ displaystyle x = z}$ ${\ displaystyle uvu = uuv}$ ${\ displaystyle vu = uv}$ $x$ ${\ displaystyle x <z}$ $x$ ${\ displaystyle vu <uv}$ ${\ displaystyle vuu <uvu = x}$ ${\ displaystyle vuu}$ $w$ $x$

Et lemma

Følgende resultat er nyttig i bevis på egenskapene til primitive ord:

Teorem - La og er to ord uten ord. Følgende forhold er ekvivalente: $x$ $y$

$xy = yx$ ,
det er to heltall slik at , $n, m \ ge1$ $x ^ n = y ^ m$
det er et ord og to heltall som og . $z$ $p, q \ ge1$ $x = z ^ {p}$ $y = z ^ {q}$

Demonstrasjon

${\ displaystyle (3) \ innebærer (2)}$ . Med (3) har vi derfor (2). ${\ displaystyle x ^ {q} = (z ^ {p}) ^ {q} = (z ^ {q}) ^ {p} = y ^ {p}}$
${\ displaystyle (2) \ innebærer (1)}$ . Hvis , da , og dette ordet begynner både med og med , så (1). $x ^ n = y ^ m$ ${\ displaystyle yx ^ {n} = y ^ {m + 1} = y ^ {m} y = x ^ {n} y}$ $xy$ $yx$
${\ displaystyle (1) \ innebærer (3)}$ . Ved induksjon på . Vi kan anta at det er prefikset til , ellers bytter vi rollene til og . Hvis , da ; hvis er et skikkelig prefiks av , er det et ord uten ord som f.eks . Ved å erstatte i ligningen får vi , og forenkler . Ved gjentakelse, og for et ord , og også . ${\ displaystyle | x | + | y |}$ $x$ $y$ $x$ $y$ ${\ displaystyle | x | = | y |}$ $x = y$ $x$ $y$ $t$ ${\ displaystyle y = xt}$ ${\ displaystyle xxt = xtx}$ ${\ displaystyle xt = zt}$ $x = z ^ {p}$ ${\ displaystyle t = z ^ {q}}$ $z$ ${\ displaystyle y = xt = z ^ {p + q}}$

For å demonstrere at hvert ord har en unik rot, kan vi altså anta at et ord er skrevet på to måter som kraften til et primitivt ord, det vil si med og primitive ord. Etter tilstand (3) følger det at og , og som og er primitive, har vi og . $w$ ${\ displaystyle w = x ^ {n} = y ^ {m}}$ $x$ $y$ $x = z ^ {p}$ $y = z ^ {q}$ $x$ $y$ ${\ displaystyle p = q = 1}$ $x = y$

Språket til primitive ord

Det er tradisjonelt å skrive ned alle primitive ord på et fast alfabet. På et brev er det bare ett primitivt ord. På mer enn en bokstav er problemet med settets natur , innenfor rammen av teorien om formelle språk , stilt uten å være løst ennå (i 2016). Pál Dömösi og Masami Ito har viet en bok på mer enn 500 sider til dette spørsmålet. En gjennomgangsartikkel er av Gerhard Lischke. $Q$ $Q$

Vi vet ikke om språket er algebraisk. Holger Petersen beviste i en artikkel publisert i 1996 at språket ikke er entydig algebraisk. Han bruker til det serien som genererer antall ord på k bokstaver som er skrevet $Q$ $Q$ $Q$

{\ displaystyle Q (z) = \ sum _ {n = 0} ^ {\ infty} nM (n) = \ sum _ {n = 0} ^ {\ infty} \ sum _ {d \ mid n} \ mu (d) k ^ {n / d}}

og er basert på Chomsky-Schützenberger-setningen, ifølge hvilken serien som genererer antall ord i et entydig algebraisk språk, er en algebraisk funksjon. For å vise at serien ikke er algebraisk, bruker han et av kriteriene utviklet av Philippe Flajolet . $Q (z)$

De vanlige verktøyene for å bevise at et språk ikke er algebraisk, som Ogdens iterasjonslemma , eller andre iterasjonslemma som Bader og Mouras lemma eller til og med Ogdens utvekslingslemma , Winklmann og Ross, tillater ikke en konklusjon.

Språket til primitive ord er lukkingen av Lyndons ord ved sirkulær permutasjon . Hvis det var algebraisk, ville det være det samme siden algebraiske språk er stengt av sirkulær permutasjon. Det ble imidlertid vist av Berstel og Boasson at det ikke er algebraisk ved å anvende Ogdens lemma . $Q$ $L$ $L$ $Q$ $L$

Språk er heller ikke lineært algebraisk , men det er et deterministisk kontekstuelt språk , det vil si anerkjent av en lineært avgrenset deterministisk automat . Når det gjelder kompleksiteten i gjenkjenning, er språket i klassen DTIME (n ^ 2), dvs. at det gjenkjennes av en deterministisk Turing-maskin i kvadratisk tid. $Q$

Morfisme som bevarer primitive ord

En morfisme av en fri halvgruppe til en annen fri halvgruppe bevarer de primitive ordene hvis bildet av et primitivt ord fremdeles er et primitivt ord.

Eksempler på morfismer som bevarer primitive ord er gitt av Lyndon-morfismer som per definisjon er morfismer som bevarer Lyndon-ord. En slik morphism bevarer også primitive ord: ja, hvis er en primitiv ord, det finnes et konjugat av som er en Lyndon ord; bildet av er ved hypotese et ord av Lyndon, derfor primitivt, og bildet av , som er et konjugert ord av , er derfor også et primitivt ord. En detaljert studie av morfer som bevarer primitive ord ble gjort av Viktor Mitrana. En lang versjon er tilgjengelig online. Hovedresultatet er en karakterisering av morfismene som bevarer de primitive ordene. For dette definerer vi begrepet ren kode . En kode med variabel lengde er en ren kode hvis for noe element av roten også er en del av . Vi kan vise at en kode er ren hvis og bare hvis det er et stjerneløst språk . $f$ $x$ $y$ $x$ $f (y)$ $y$ $f (x)$ $x$ $f (y)$ $X$ $x$ $X ^ {+}$ ${\ sqrt x}$ $X ^ {+}$ $X ^ {*}$

Proposisjon - En morfisme bevarer primitive ord hvis og bare hvis det er en ren kode. ${\ displaystyle f: A ^ {+} \ til B ^ {+}}$ ${\ displaystyle f (A)}$

Merknader og referanser

Lothaire 1983 .
Shallit 2009 .
Lischke tilskriver dette resultatet til Huei-Jan Shyr og Shyr-Shen Yu, “ Ikke-primitive ord på språket ${\ displaystyle p ^ {+} q ^ {+}}$ ”, Soochow J. Math. , vol. 20, n o 4,1994, s. 535–546.
Othman Echi , “ Ikke-primitive ord med formen pq m ”, RAIRO - Theoretical Informatics and Applications , vol. 51, n o 3,2017, s. 141-166 ( ISSN 0988-3754 , DOI 10.1051 / ita / 2017012 )
Pál Dömösi og Masami Ito, kontekstfrie språk og primitive ord , World Scientific Publishing , 2014, 520 s. ( ISBN 978-981-4271-66-0 , OCLC 897020798 , online presentasjon )
Det er spesielt kapittel 8 i boka, med tittelen Some Properties of the Language of Primitive Words , som studerer språkets algebraisitet.
Gerhard Lischke, " Primitive ord og røtter av ord ", Acta Univ. Sapientiae, Informatica , vol. 3, n o 1, 2011, s. 5–34 ( arXiv 1104.442 ).
Holger Petersen, “ On the Language of Primitive Words, ” Theoretical Computer Science , vol. 161, n bein 1-2, 1996, s. 141-156 ( les online ).
(i) Philippe Flajolet, " Analytiske modeller og tvetydighet i kontekstfrie språk " , Teoretisk. Beregn. Sci. , vol. 49,1987, s. 283-309 ( DOI 10.1016 / 0304-3975 (87) 90011-9 , les online ).
Jean Berstel og Luc Boasson, “ The set of Lyndon words is not context-free ”, Bulletin of the European Association for Theoretical Computer Science 63 (1997) , vol. 63, n o 1,1997, s. 139-140.
Lischke 2011 .
Noen ganger finner vi begrepet "primitiv morfisme" for en morfisme som bevarer primitive ord, men dette begrepet er nå ganske reservert, i ordkombinatorikk, for en morfisme hvis tilhørende matrise er primitiv.
Gwénaël Richomme, “ Noen elementer i Word Combinatorics Cours 2014-2015 ” , Lirmm, 2014-2015 (konsultert 6. mai 2017 ) .
Victor Mitrana, “ Primitive morphisms ”, Information Processing Letters , vol. 64,1997, s. 277–281.
Victor Mitrana, " On morphisms preserving primitive words " , TUCS Technical Report N ° 69 , Turku Center for Computer Science,November 1996( ISBN 951-650-895-2 , åpnet 6. mai 2017 ) .

Bibliografi

M. Lothaire, kombinatorikk på ord , Addison-Wesley Publishing Co., Reading, Mass., Coll. "Encyclopedia of Mathematics og dets Applications" ( N o 17)1983, 238 s. ( ISBN 978-0-201-13516-9 , online presentasjon )- En annen revidert utgave dukket opp av Cambridge University Press , i Cambridge Mathematical Library-samlingen, i 1997, ( ISBN 978-0521599245 )
(en) Jeffrey Shallit, et andre kurs i formelle språk og automatteori , Cambridge University Press ,2009, 240 s. ( ISBN 978-0-521-86572-2 )

Relaterte artikler