Toistovapaat Merkkijonot

Toistovapaat merkkijonot ja tietokonealgebra


Tiivistelmä

Sanat eli merkkijonot kuuluvat teoreettisessa tietojenkäsittelyssä perusobjekteihin, joten niiden rakenteiden analysointi on yksi tämän tieteenalan keskeisistä tutkimuskohteista.

Norjalainen matemaatikko Axel Thue [7] (1863-1922) aloitti sanojen rakenteita koskevan systemaattisen tutkimuksen vuosisatamme alussa. Hänen perustavanlaatuisille tuloksilleen, jotka koskevat annetusta aakkostosta muodostettavissa olevia äärettömiä toistovapaita eli säännöllisyyksiä välttäviä sanoja, on löydetty useita sovellutuksia matematiikan eri aloilta. Toistovapaat sanat ovat äskettäin herättäneet mielenkiintoa myös musiikin alalla, ks. Laakso [5].

Olkoon X nelikirjaiminen aakkosto {a,b,c,d }. Raportissa [3] (Keränen 1992) esitimme tietokoneen avulla löydetyn Abelin neliöistä vapaan endomorfismin g: X* -> X* (kuvauksen joka säilyttää sanojen toistovapauden), jonka koko on |g(abcd)| = 340. Endomorfismi g määritellään seuraavasti. Kirjaimen a kuvasana on

g(a) = abcacdcbcdcadcdbdabacabadbabcbdbcbacbcdcacbabdabacadcbcdcacdbcbacbcdcacdcbdcdadbdcbca

ja muiden kirjainten b, c, d kuvasanat g(b), g(c), g(d) saadaan syklisellä permutaatiolla edeltävistä sanoista g(x), missä kirjain x kuuluu aakkostoon X.

Kaikki tällä hetkellä tunnetut menetelmät, ks. [1] (Carpi 1994), rajoittamattoman pituisten Abelin neliöistä vapaiden sanojen konstruoimiseksi aakkostossa X perustuvat tämän endomorfismin g rakenteeseen. Kuitenkaan ei tiedetä, onko aakkostossa X mahdollista määritellä Abelin neliöistä vapaita endomorfismeja, joiden koko olisi pienempi kuin yllämainittu koko 340. Tämän kysymyksen ja muiden algebrallisia rakenteita koskevien ongelmien ratkaiseminen on kehittymässä uudeksi hyvin haastavaksi ja kiehtovaksi tietokonealgebran tutkimusalaksi.

Vuonna 1961 Erdös [2, s. 240] esitti kysymyksen, voidaanko Abelin neliöt välttää äärettömissä sanoissa, ts. onko Abelin neliöistä vapaiden sanojen määrä ääretön annetussa aakkostossa. Abelin neliö tarkoittaa ei-tyhjää äärellistä (mutta muutoin mielivaltaista) pituutta olevaa sanaa uv, missä u ja v ovat toistensa permutaatioita. Esimerkiksi abcacb on Abelin neliö. Sanaa kutsutaan Abelin neliöistä vapaaksi, jos sen osasanojen joukossa ei ole yhtään Abelin neliötä. Esimerkiksi sana abacaba on Abelin neliöistä vapaa, kun taas abcdadcada ei ole (se sisältää osasanan cda dca).

Vuonna 1970 Pleasants [6] osoitti, että viisikirjaimisessa aakkostossa voidaan määritellä Abelin neliöistä vapaita äärettömiä sanoja.

Nelikirjaimisen aakkoston tapaus oli pitkään avoin, kunnes vuonna 1991, ks. Keränen [3], onnistuimme todistamaan että em. endomorfismin g iterointi tuottaa "raja-arvonaan" Abelin neliöistä vapaan äärettömän sanan. Kaulakorun kuvassa tämän äärettömän (itseänsä lukevan) sanan alku, ts. g(abcacd ) = g(a) g(b) g(c) g(a) g(c) g(d), on esitetty 6*85 värillisen, kuudella kierroksella olevan, monitahokkaan avulla. Kierrokset alkavat alhaaltapäin ja jokainen niistä esittää ketjun alusta luettujen kirjainten kuvasanoja. Siten ensimmäinen kierros on g(a), toinen kierros on g(b), ja niiden jälkeen tulevat g(c), g(a), g(c) ja g(d).

Nelikirjaiminen aakkosto on erikoisasemassa siinä että se on pienin aakkosto, jonka äärettömissä sanoissa Abelin neliöt voidaan välttää. Todellakin, kolmen kirjaimen tapauksessa jokainen pituutta 8 oleva sana sisältää Abelin neliön. Voisiko tämä erikoisasema jotenkin liittyä luonnon käyttämään perimän koodiin? - Myös DNA rakentuu neljästä eri merkistä.

Osa tästä tiivistelmästä on julkaistu artikkelissa [4].


Viitteet

  1. A. Carpi. On the number of abelian square-free words on four letters. Technical report, Preprint no. R.I. 110/94/IC, pages 1-15, Istituto di Cibernetica del C.N.R., Arco Felice - Napoli, Italy, 1994.

  2. P. Erdös. Some unsolved problems. Magyar Tud. Acad. Mat. Kutató Int. Közl., 6:221-254, 1961.

  3. V. Keränen. Abelian squares are avoidable on 4 letters. In W. Kuich, editor, Proc. ICALP '92, Lecture Notes in Comp. Sci., volume 623, pages 41-52. Springer-Verlag, Berlin, 1992.

  4. V. Keränen. Toistovapaat merkkijonot ja tietokonealgebra. In C. Gefwert, P. Orponen, and J. Seppänen, editors, Proc. Logic, Mathematics and the Computer, Publications of the Finnish Artificial Intelligence Society, Symposiosarja, volume 14, pages 250-257. Hakapaino, Helsinki, 1996.

  5. T. Laakso. Musical redering of an infinite repetition-free string. In C. Gefwert, P. Orponen, and J. Seppänen, editors, Proc. Logic, Mathematics and the Computer, Publications of the Finnish Artificial Intelligence Society, Symposiosarja, volume 14, pages 292-297. Hakapaino, Helsinki, 1996.

  6. P.A.B. Pleasants. Non-repetitive sequences. Proc. Cambridge Phil. Soc., 68:267-274, 1970.

  7. A. Thue. Über unendliche zeichenreihen. Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania, 7:1-22, 1906.