Název:
Vztah determinismu a nedeterminismu pro lineární čas
Překlad názvu:
Relation of determinism and non-determinism for linear time
Autoři:
Juračka, Matej ; Koubek, Václav (vedoucí práce) ; Kučera, Petr (oponent) Typ dokumentu: Diplomové práce
Rok:
2011
Jazyk:
slo
Abstrakt: [eng][cze] Result of this work is a reconstruction of proof, that non-deterministic linear time is strictly more powerful than deterministic linear time. We focus on completeness and clarity either of proof itself, either of all auxiliary propositions, which lead to this result.Výsledkem práce je rekonstrukce důkazu, že třídy jazyků akceptovaných deterministickým a nedeterministickým strojem v lineárním času jsou různé. Soustředíme se přitom na úplnost a srozumitelnost jak samotného důkazu, tak i všech přípravních tvrzení, které k němu vedou. Výsledkem práce je rekonstrukce důkazu, že třídy jazyků akceptovaných deterministickým a nedeterministickým strojem v lineárním času jsou různé. Soustředíme se přitom na úplnost a srozumitelnost jak samotného důkazu, tak i všech přípravních tvrzení, které k němu vedou. Výsledkem práce je rekonstrukce důkazu, že třídy jazyků akceptovaných deterministickým a nedeterministickým strojem v lineárním času jsou různé. Soustředíme se přitom na úplnost a srozumitelnost jak samotného důkazu, tak i všech přípravních tvrzení, které k němu vedou.
Klíčová slova:
alternujuci Turingov stroj; separacia tried zlozitosti; vzt'ah determinizmu a nedeterminizmu; alternating Turing machine; relation of determinism and non-determinism; separation of complexity classes