Original title: Vztah determinismu a nedeterminismu pro lineární čas
Translated title: Relation of determinism and non-determinism for linear time
Authors: Juračka, Matej ; Koubek, Václav (advisor) ; Kučera, Petr (referee)
Document type: Master’s theses
Year: 2011
Language: slo
Abstract: [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.
Keywords: alternating Turing machine; relation of determinism and non-determinism; separation of complexity classes; alternujuci Turingov stroj; separacia tried zlozitosti; vzt'ah determinizmu a nedeterminizmu

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/49450

Permalink: http://www.nusl.cz/ntk/nusl-493812


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Master’s theses