Errata for "Elements of Finite Model Theory"


1. Page 21, bibliographic notes. Credits to Chandra/Harel 1980 for
   identifying queries as the main object of study in finite model
   theory is missing. 

2. Page 16, line -16: "In general, Theorem 2.1..." should be
   "In general, Theorem 2.6..."

3. Page 39, last paragraph. There is an informal argument that
   for more complicated properties combinatorial game proofs are more
   involved. While certainly true, the example of an n-ary tree is
   not a good one, as a very easy modification of the preceeding proof
   (simply by adding extra n-1 edges to each node) shows that being an
   n-ary tree is not FO-expressible. (thanks to David Richerby). 

5. Page 58, In the definition of \frak{A} \simeq_0^{bij} \frak{B} in
   line -1, condition |A|=|B| is missing.

6. Page 64, Exercise 4.14: a basic r-local formula should be 
   defined as \alpha(\vec x) which is r-local around one of the 
   variables x_i (in the definition given, \alpha only depends 
   on x_i).

7. Page 77, line 11: \equiv_k should be \equiv_{k+2}.

8. Page 79, line -7: "q_i <_a p_j" should be "q_i <_a q_j".

9. Page 81, condition (5.8): \equiv_i should be \equiv_{k-i}. 

10. Page 106, equation (6.11), \nu_i=t should be \nu_i \subseteq t. 
   (thanks to Pablo Barcelo for catching the #7-#10).

11. p. 116, line 9: V should be \vec{V}; line 10: \vec{U} should be
   \vec{V}. 

12. p. 178, definition 10.1, second sentence. "A set X \subseteq A"
   should be changed to "A set X \subseteq U"  

13. p 178, paragraph 4, fifth sentence: "If X^i \subseteq X^{+1}"
   should be changed to "If X^i \subseteq X^{i+1}" 
   (#10-12, thanks to Anthony Widjaja To)

14. Page 204 (section 10.7). It should be noted that an earlier version
   of Gurevich's conjecture asking whether the set of Ptime queries is
   r.e. was formulated by Chandra and Harel in 1982. (Thanks to David
   Harel for pointing this out).

15. Page 236, line -6, the last expression: 2^{kn+k^2} should be 
   2^{kn-k^2}. The remaining calculations do not apply, but it is 
   still very easy to see that the sequence converges to 0.

16. Page 237, line 3: the expression should be divided by 
   2^{\binom{n}{2}}. 
   (thanks to Luc Segoufin for catching #14 and #15).

17. Page 256, line 6 should read "\pi(Q(A))=Q(\pi(A))" (thanks to
   Steven Lindell).

18. Page 273, exercise 13.17. FO^{gen}_{act}(M,\sigma) should be
    FO^{gen}(M,\sigma) (thanks to Anthony Widjaja To)

19. Page 277, the complexity of containment of unions of conjunctive
    queries is NP-complete, not \Pi^p_2-complete as stated.
    \Pi^p_2-completeness applies if queries are give by relational algebra
    expressions, as described in Chapter 6 (thanks to Frantisek Simancik).