Books and Lecture Notes

• Page 295 Exercise 141. I grossly underestimated the issue of Leibniz Principle in set theory. What it comes down to is the identity of indiscernibles. This has been investigated by Jan Mycielski. The structure theory of these universes is far from simple. See Ali Enayat: "Leibnizian models of set theory", The Journal of Symbolic Logic 69, 2004, 757 - 789.
• Page 425-426 The claim that indexed grammars generate only 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 to Hans-Jörg Thiede for discovering this.)
• Page 470 Definition 6.2 should contain the condition that L is empty.
• Page 472 The claim that MSO cannot differentiate between a class containing the empty word and one that does not is false. That claim holds for QML, though. With the condition that L be nonempty, that issue disappears. (Thanks to Geoffrey Pullum for bringing this to my attention.)
• Page 502 The passage that claims that we can transform a transducer to a determinstic machine given both input and output is false. The implicit use of the finite state theorem based on strings is illicit. This has to do with the problem that a pair of strings is not uniquely decomposable into basic pairs <a : ε> or <&epsilon : a>.