| Abstrakt: | Analyzujeme dva paralelné modely - Generatívny systém (ďalej už len G-systém) a alternujúci Turingov stroj (ďalej už len ATS). Táto práca sa zaoberá porovnaním týchto dvoch paralelných modelov, resp. porovnaním ich tried zložitosti, vzhľadom na dve miery zložitosti - čas a priestor.
Najskôr prinášame základné definície modelov, tried zložitosti a notácie, ktorú budeme používať. Nasleduje prehľad už dokázaných tvrdení, prípadne triviálne vyplývajúcich tvrdení, z už dokázaných.
Ďalej v práci porovnávame triedy zložitosti oboch modelov sformulovaním a dokázaním horných a dolných odhadov. Pri horných odhadoch popíšeme simuláciu jedného modelu druhým a dokážeme jej správnosť. Dolné odhady dokážeme nájdením "kontrapríkladových" jazykov a ukážeme, že, za určitých okolností, jeden model "kontrapríkladový" jazyk vie akceptovať, resp. generovať a druhý nie.
|
|---|