K. Rüdiger Reischuk
Komplexitätstheorie, Band I: Grundlagen:
Maschinenmodelle, Zeit- und Platzkomplexität
Teubner Verlag Stuttgart, 1999
Druckfehler:
- S. 40: Zeile -5: ihrer Lösung
- S. 111: in Theorem 2.2.27 füge
hinzu: ... Graphen G = (V_1 u V_2, E) mit
|V_1|=|V_2| genau dann ...
- S. 130: 1. Abschnitt im Beweis
von Theorem 3.1.1: ersetze ... Anahl
der Nullen und Einsen ...
durch ... Anzahl der a's und b's ...
- S. 294: Allquantor in der 1. Formel, Subscripts: ersetze i
in [1,t] durch i in [0,t-1] und j in [1,t+1] durch j in [1,t]
- S. 299: letzte Zeile: repräsentiert
- S. 325: Abbildung 6.11: die Mengeninklusionen
in der 2. Zeile sind verdreht.
Es gilt sogar, dass DCFL eine echte Teilmenge von DTime(LIN) ist und ebenso CFL von NTime(LIN),
was man etwa an der Sprache an bn cn sieht, die nicht kontextfrei ist.
Jeden Hinweis auf weitere Druckfehler, Verbesserungsvorschläge sowie Anmerkungen (positiv sowie negativ) nehme ich gerne entgegen: [email protected]
