G2 Master’s thesis, polytechnic Master’s thesis
Rauzy-graafit äärettömien sanojen kombinatoriikassa
Authors: Whiteland Markus
Publishing place: Turku
Publication year: 2013
Abstract
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.
UTU Research Portal