50 Jahre Uni Lübeck

Prof. Dr. math. K. Rüdiger Reischuk

Korrekturen


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: reischuk@tcs.uni-luebeck.de