Hyppää sisältöön
    • Suomeksi
    • In English
  • Suomeksi
  • In English
  • Kirjaudu
Näytä aineisto 
  •   Etusivu
  • 1. Kirjat ja opinnäytteet
  • Pro gradu -tutkielmat ja diplomityöt sekä syventävien opintojen opinnäytetyöt (kokotekstit)
  • Näytä aineisto
  •   Etusivu
  • 1. Kirjat ja opinnäytteet
  • Pro gradu -tutkielmat ja diplomityöt sekä syventävien opintojen opinnäytetyöt (kokotekstit)
  • Näytä aineisto
JavaScript is disabled for your browser. Some features of this site may not work without it.

Automaattien synkronisaatiosta

Kopra, Johan (2015-04)

Automaattien synkronisaatiosta

Kopra, Johan
(04 / 2015)
Katso/Avaa
Gradu2015Kopra.pdf (346.4Kb)
Lataukset: 

Turun yliopisto
avoin
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe2015081210928

Kuvaus

Siirretty Doriasta
Tiivistelmä
Tässä tutkielmassa tarkastellaan eräitä synkronisoituviin automaatteihin liittyviä ongelmia. Pääpaino on Černýn konjektuurissa ja tienväritysongelmassa, joiden lisäksi käsitellään myös hybridikonjektuuria.

Černýn konjektuuri on otaksuma, jonka mukaan jokainen synkronisoituva n-tilainen automaatti voidaan synkronisoida enintään pituutta (n − 1)2 olevalla sanalla. Ongelma on ollut avoin 1970-luvulta asti, mutta useita osatuloksia on todistettu. Tutkielmassa esitetään niistä tärkeimmät.
Tienväritysongelma koskee sitä, millaisista suunnatuista graafeista voidaan muodostaa synkronisoituvia automaatteja. Vuonna 2009 todistetun tienvärityslauseen mukaan synkronisoituvia automaatteja voidaan muodostaa ns. primitiivisistä graafeista. Tutkielmassa esitetään tienvärityslauseen todistus.

Hybridikonjektuuri on vuonna 2010 esitetty otaksuma, jossa on yhdistetty elementtejä Černýn konjektuurista ja tienvärityslauseesta. Hybridikonjektuurin mukaan jokaisesta n solmua sisältävästä primitiivisestä graafista voidaan muodostaa synkronisoituva automaatti, jonka lyhimmän synkronisoivan sanan pituus on enintään n 2 − 3n + 3. Tutkielmassa esitetään tunnettuja osatuloksia sekä johdetaan uusi alaraja Eulerin graafeille.
Kokoelmat
  • Pro gradu -tutkielmat ja diplomityöt sekä syventävien opintojen opinnäytetyöt (kokotekstit) [9570]

Turun yliopiston kirjasto | Turun yliopisto
julkaisut@utu.fi | Tietosuoja | Saavutettavuusseloste
 

 

Tämä kokoelma

JulkaisuajatTekijätNimekkeetAsiasanatTiedekuntaLaitosOppiaineYhteisöt ja kokoelmat

Omat tiedot

Kirjaudu sisäänRekisteröidy

Turun yliopiston kirjasto | Turun yliopisto
julkaisut@utu.fi | Tietosuoja | Saavutettavuusseloste