| Abstrakt: | V práci sa zaujímame o viachlavové dvojsmerné konečnostavové automaty
a o pomocou nich definované zložitostné triedy. Zaoberáme sa výpočtovou silou
rôznych modelov vzhľadom na počet čítacích hláv a ohraničenie obratovej miery
zložitosti. Analyzujeme a prezentujeme najznámejšie výsledky z tejto oblasti, s cieľom porovnať ich s výsledkami na rôznych zoslabených modeloch (jednosmerné automaty, automaty nezávislé od vstupu, zametajúce automaty, atď.). Popisujeme aj všeobecný model – viachlavový alternujúci stroj (MAM) používajúci nekonečne veľa stavov. Odhady zložitosti získané pre tento model sú aplikovateľné aj na automaty. Na deterministickom variante tohto modelu dokážeme dolný odhad na počet obratov. Dôsledkom nami získaného odhadu je separácia deterministických
a nedeterministických zariadení. Ukážeme existenciu hierarchie na obratovú mieru
zložitosti pre MAM.
|
|---|