| Meno: | Pavol
|
|---|
| Priezvisko: | Panák
|
|---|
| Názov: | Konečné automaty so žetónmi
|
|---|
| Vedúci: | prof. RNDr. Branislav Rovan, PhD.
|
|---|
| Rok: | 2011
|
|---|
| Blok: | INF
|
|---|
| Kľúčové slová: | žetón, jednosmerné a dvojsmerné, žetónové automaty, výpočtová sila
|
|---|
| Abstrakt: | V práci skúmame výpočtovú silu jednosmerných konečných automatov so žetónmi pre rôzne počty žetónov a hláv. Uvádzame dôkaz nárastu výpočtovej sily jednosmerných žetónových automatov v závislosti od pridávania hláv. Podobný nárast výpočtovej sily žetónových automatov sme ukázali aj pri zväčšovaní počtu žetónov. Dokázali sme rozdielnosť jednosmerných žetónových deterministických a nedeterministických automatov. Rozobrali sme aj tému, či je možné zameniť jeden žetón za jednu hlavu a naopak, v ktorej sme ukázali, že takéto zámeny nie sú možné bez určitej straty výpočtovej sily žetónového automatu. V neposlednom rade sme dokázali hornú hranicu počtu "sensing" hláv, ktoré sú schopné kompenzovať stratu jedného žetóna.
|
|---|