00:05:00
|
Algorithmus 1.2.4 Blockverfeinerungsalgorithmus
|
00:22:15
|
Bemerkung 1.2.8. Bei Termination liefert der Algorithmus mit seiner Blockaufteilung genau die Klasseneinteilung von Q nach ~A
|
00:32:30
|
1.3 NEA "Minimierung"
|
00:45:00
|
Bemerkung 1.3.1. Zusammenfassen von Zuständen führt von geg. NEA i.a. nicht zu einem kleinstmöglichen NEA
|
00:48:30
|
Bemerkung 1.3.2. Für minimale NEA's einer reg. Sprache gilt i.a. nicht die Isomorphie
|
00:54:30
|
Definition einer Turingmaschine
|
01:05:30
|
Definition der Klassen P, NP und PSPACE
|
01:10:40
|
Definition PSPACE vollständig
|
01:21:15
|
Def inition 1.3.2. NEA-MIN, NEA-EQUIV, NEA-UNIV, NEA-EMPTY
|