Diploma thesis

Súvis G-systémov a Alternujúcich Turingových strojov

Porovnanie zložitostných tried GTIME, ATIME, GSPACE a ASPACE

Mojím prínosom je preskúmať zatiaľ neznáme vzťahy medzi zložitostnými triedami vyššie spomenutých paralelných modelov.

Kapitoly budú zrejme tri:

1. Kapitola 1: Základné pojmy a definície
2. Kapitola 2: Horné odhady
3. Kapitola 3: Dolné odhady

Aktuálna verzia diplomovky.

Aktuálne materiály (články):

• Alternation and power of non-determinism
• Lokálna verzia (Alternation and power of non-determinism)
• Iterative tree automata, Alternating turing machines and uniform boolean circiuts: Relationships and characterization
• Lokálna verzia (Iterative tree automata...)
• Alternation
• Lokálna verzia (Alternation)
• Strong optimal lower bounds for Turing machines that accept nonregular languages
• Lokálna verzia (Strong optimal lower bounds...)