| Meno: | Peter
|
|---|
| Priezvisko: | Kostolányi
|
|---|
| Názov: | Rovnomerné využívanie prechodov v konečných automatoch
|
|---|
| Vedúci: | prof. RNDr. Branislav Rovan, PhD.
|
|---|
| Rok: | 2011
|
|---|
| Kľúčové slová: | deterministický konečný automat, prechodová vyváženosť, prechodovo vyvážený automat, prísne prechodovo vyvážený automat, slabo prechodovo vyvážený automat, rovnomerné využívanie prostriedkov
|
|---|
| Abstrakt: | Výskum rovnomerne zaťažených výpočtových modelov je inšpirovaný predovšetkým oblasťou vývoja počítačového hardvéru, kde rovnomerné využívanie častí daného hardvérového systému môže mať viacero pozitívnych dôsledkov pre jeho činnosť. Teoretické štúdium vyvážených výpočtových modelov môže prispieť k pochopeniu otázky, ktoré výpočtové problémy možno riešiť s rovnomerným využívaním prostriedkov. Prvé výsledky v tejto oblasti predstavujú práce Ivana Kováča
o rovnomernom využívaní stavov v konečných automatoch.
Práca definuje a opisuje rôzne triedy deterministických konečných automatov s rovnomerným využívaním prechodov a triedy jazykov takýmito automatmi akceptované. Definované triedy automatov sa líšia v sile požiadavky kladenej na rovnomernosť využívania prechodov. Najsilnejšia je definícia prísne prechodovo vyváženého automatu, pri ktorej sa počas výpočtu na každom slove využívajú všetky prechody približne rovnako veľa ráz. Ďalšou definovanou triedou sú prechodovo vyvážené automaty. Prechody takýchto automatov sa využívajú približne rovnako veľa ráz na všetkých slovách určitej dĺžky dohromady. Najslabšia je definícia slabo prechodovo vyváženého automatu, ktorá rozširuje okruh prechodovo vyvážených automatov na dobre opísateľnú triedu.
Práca definuje a skúma uvedené triedy automatov a triedy nimi akceptovaných jazykov s ambíciou ich čo najlepšie opísať. Pre každú z definovaných tried vyvážených jazykov sú dokázané ich uzáverové vlastnosti a v závere práce sa predkladajú tvrdenia o vzájomných vzťahoch týchto tried, ako aj o ich vzťahoch k triedam stavovo vyvážených jazykov.
|
|---|