Fehlerliste

• Seite 83 Der Satz Notice that the edge colours only the vertex colours are used to steer the derivation. ist ungrammatisch und irreführend. Es sollte vielmehr heißen Notice that only the edge colours are used to steer the derivation. (Ich wurde von John Colby darauf aufmerksam gemacht.)
• Seite 295 Exercise 141. Den Status des Leibniz'schen Prinzips in der Mengenlehre habe ich erheblich unterschätzt. Es läuft nämlich auf die Identität von Indiscernibles hinaus. Mengenlehre mit Leibniz'schem Prinzip wurde von Jan Mycielski untersucht. Die Strukturtheorie solcher Universen ist alles andere als einfach, siehe Ali Enayat: "Leibnizian models of set theory", The Journal of Symbolic Logic 69, 2004, 757 - 789.
• Seite 108, (2.22) Es muss auf der linken Seite heißen A → a (Christian Wurm hat das entdeckt.)
• Seite 409. Theorem 5.45 ist falsch für k ≥ 3. Dies ist das Ergebnis von Makoto Kanazawa, Gregory M. Kobele, Jens Michaelis, Sylvain Salvati und Ryo Yoshinaka: The Failure of the Strong Pumping Lemma for Multiple Context-Free Languages (unveröffentlichtes Manuskript).
• Seite 425-426 Die Behauptung, dass indizierte Grammatiken nur PTIME Sprachen erzeugen, wurde von Bill Rounds 1973 widerlegt ("Complexity in Recognition in Intermediate-Level Languages", in: Proceedings 14th Annual IEEE Symposium on Switching and Automata Theory, 145 - 158. IEEE Computer Science, Northridge, CA). (Danke an Hans-Jörg Thiede für diesen Hinweis.)
• Seite 470 Definition 6.2 sollte die Bedingung enthalten, dass L nicht leer ist.
• Seite 472 Die Behauptung, MSO könne zwischen einer Klasse, die das leere Wort enthält und dieser Klasse ohne das leere Wort unterscheiden, ist falsch. Dies gilt aber für QML. Mit der Bedingung, dass L nichtleer ist, ist das Problem dann verschwunden. (Geoffrey Pullum hat dies Problem entdeckt.)
• Page 502 Die Behauptung, dass wir einen Transducer in einen deterministischen Transducer übersetzen können, ist natürlich falsch. Der implizite Gebrauch des analogen Satzes für endliche Automaten ist unzulässig. Das Problem ist nämlich, dass auf der einen Seite Zeichenketten auf genau eine Weise minimal zerlegt werden können. So hat zB das Paar ⟨a, a⟩ zwei Zerlegungen in ein Produkt der Paare ⟨a : ε⟩ oder ⟨ε : a⟩.
• Seite 520, Example (6.172) Dieser Beispielsatz ist ungrammatisch. Es sollte vielmehr heißen John is believed to be responsible for himself.