List of Errors

• Page 83 The sentence Notice that the edge colours only the vertex colours are used to steer the derivation. is not grammatical and misleading. It should read instead Notice that only the edge colours are used to steer the derivation. (This has been spotted by John Colby.)
• Seite 108, (2.22)On the left hand side it must read A &u2192; a. (This has been spotted by Christian Wurm.)
• Page 295 Exercise 141. I have grossly underestimated the status of Leibniz' Principle in set theory. It comes down to the identity of indiscernibles. Set theory with Leibniz' Principle has been studied by Jan Mycielski. The structure theory of such universes is everything but easy, see Ali Enayat: "Leibnizian models of set theory", The Journal of Symbolic Logic 69, 2004, 757 - 789.
• Page 409. Theorem 5.45 ist false for k ≥ 3. This is the result of Makoto Kanazawa, Gregory M. Kobele, Jens Michaelis, Sylvain Salvati and Ryo Yoshinaka: The Failure of the Strong Pumping Lemma for Multiple Context-Free Languages (unpublished manuscript).
• Page 425-426 Die claim that indexed grammars can only generate PTIME languages has been refuted by Bill Rounds in 1973 ("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). (Thanks for Hans-Jörg Thiede for spotting this.)
• Page 470 Definition 6.2 should contain the clause that L is not empty.
• Page 472 The claim that MSO can differentiate between a class that contains the empty word and this class without the empty word is false. This does hold however for QML. Adding the condition that L is not empty the problem will disappear. (Geoffrey Pullum has noticed this.)
• Page 502 The claim that a transducer can be made deterministic is of course false. The implicit use of the analogous fact for finite automata is not licit. The problem is that while strings have a unique decomposition into letters, pairs of strings do not have such a decomposition. For example the pair ⟨a, a⟩ has two decompositions into a product of the pairs ⟨a : ε⟩ or ⟨ε : a⟩.
• Page 520, Example (6.172) This sentence is not grammatical. It should read John is believed to be responsible for himself.