G2 Pro gradu, diplomityö, YAMK-opinnäytetyö
Rauzy-graafit äärettömien sanojen kombinatoriikassa
Tekijät: Whiteland Markus
Kustantaja: University of Turku
Kustannuspaikka: Turku
Julkaisuvuosi: 2013
Tiivistelmä
Tämä tutkielma käsittelee äärettömien sanojen Rauzy-graafeja, jotka ovat tärkeitä työkaluja äärettömien sanojen kombinatoriikassa. Rauzy-graafit esiteltiin 1980-luvun alkupuolella äärettömien sanojen rakenteen havainnollistamisen apuna, mutta pian huomattiin että ne ovat myös hyödyksi teorian kannalta. Niitä on käytetty sanojen kombinatoriikassa 1980-luvun lopulta tähän päivään asti ja ne ovat osoittautuneet hyvin tehokkaaksi työkaluksi. Rauzy-graafien vahvuus on erityisesti äärettömien sanojen rakenteen tarkastelussa pelkästään äärellisten tekijöiden avulla.
Tutkielmassa esitellään äärettömien sanojen kombinatoriikan peruskäsitteitä, joita
tarvitaan erityisesti Rauzy-graafien tarkastelussa. Käsitteet käydään läpi tarkasti,
eikä esitietoja tutkielman lukemiseksi siten vaadita. Rauzy-graafeja tarkastellaan
aluksi yleisemmässä ympäristössä, formaalisten kielten työkaluna. Erityisesti Rauzy-graafeihin kirjallisuudessa liitetyt käsitteet nähdään käytännössä äärettömien sanojen käsitteinä. Äärettömien sanojen Rauzy-graafien rakenteita tarkastellaan laajasti. Lisäksi esitellään Rauzy-graafien käyttöä äärettömien sanojen ominaisuuksien tarkastelussa. Pääpaino on Sturmin sanoissa, joiden yksinkertainen rakenne takaa niiden Rauzy-graafien helposti tarkasteltavan rakenteen. Sturmin sanojen Rauzy-graafien rakenne saadaan luonnehdittua täysin Sturmin sanojen kaksijakoisten tekijöiden avulla.
Tämä tutkielma käsittelee äärettömien sanojen Rauzy-graafeja, jotka ovat tärkeitä työkaluja äärettömien sanojen kombinatoriikassa. Rauzy-graafit esiteltiin 1980-luvun alkupuolella äärettömien sanojen rakenteen havainnollistamisen apuna, mutta pian huomattiin että ne ovat myös hyödyksi teorian kannalta. Niitä on käytetty sanojen kombinatoriikassa 1980-luvun lopulta tähän päivään asti ja ne ovat osoittautuneet hyvin tehokkaaksi työkaluksi. Rauzy-graafien vahvuus on erityisesti äärettömien sanojen rakenteen tarkastelussa pelkästään äärellisten tekijöiden avulla.
Tutkielmassa esitellään äärettömien sanojen kombinatoriikan peruskäsitteitä, joita
tarvitaan erityisesti Rauzy-graafien tarkastelussa. Käsitteet käydään läpi tarkasti,
eikä esitietoja tutkielman lukemiseksi siten vaadita. Rauzy-graafeja tarkastellaan
aluksi yleisemmässä ympäristössä, formaalisten kielten työkaluna. Erityisesti Rauzy-graafeihin kirjallisuudessa liitetyt käsitteet nähdään käytännössä äärettömien sanojen käsitteinä. Äärettömien sanojen Rauzy-graafien rakenteita tarkastellaan laajasti. Lisäksi esitellään Rauzy-graafien käyttöä äärettömien sanojen ominaisuuksien tarkastelussa. Pääpaino on Sturmin sanoissa, joiden yksinkertainen rakenne takaa niiden Rauzy-graafien helposti tarkasteltavan rakenteen. Sturmin sanojen Rauzy-graafien rakenne saadaan luonnehdittua täysin Sturmin sanojen kaksijakoisten tekijöiden avulla.
Turun yliopiston Tutkimustietojärjestelmän portaali