The Theory of Computation Bernard M.E. Moret

ERRATA (Second Printing)

With many thanks to Jonathan Goldstine and Matthias Stallmann for detailed and thoughtful comments on the third printing.

• Chapter 2:
  • p. 11, then throughout the text:
    for didactic purposes, it would be preferable to have a fixed definition for N, say not including 0, and a separate notation for the version that does include 0, say N*.
  • p. 18, second paragraph:
    the functions f and g are defined to map natural integers to natural integers for simplicity, but the definitions of asymptotic notation extend naturally to larger domains, including real numbers.
  • pp. 21-22, definition of cycle, acyclic graph, and simple cycle:
    Reorder the definitions to place the definition of simple path/simple cycle before that of acyclic graphs and change the definition of acyclic graph to be a graph without any simple cycles.
  • p. 27, last line of Section 2.5:
    the exponent should be |x|/2, not |x|
  • p. 30, Exercise 2.4:
    "natural" and "rational" should be switched.
  • p. 32, first sentence:
    the part starting with "for instance, ..." should be removed: it is at best misleading, since that bijection of Exercise 2.4 is not between N and NxN and so cannot be a candidate for pairing.
  • p. 37, Exercise 2.9:
    clarification: the set is assumed to be finite.
  • p. 39, Exercise 2.22:
    The second sentence should be removed -- as written, it sets a very hard question. (It could be modified to ask whether 11 is the smallest number for which Euler's formula will yield a quick answer, in which case it becomes again an easy question.)
  • p. 40, Exercise 2.31:
    This exercise should be starred -- it is a standard exercise in combinatorics, but requires Stirling numbers of the second kind for a concise expression or will have to be written as a complex sum using inclusion/exclusion; deriving an upper bound is easy.
• Chapter 3:
  • p. 60, Definition 3.3:
    there should be one more bullet, stating "If P is a regular expression, so is (P)"
  • p. 77, end of first paragraph:
    just before "finally ...", add "the start state of M is the pair of start states of M1 and M2"
  • p. 78, end of first paragraph:
    not an erratum, but a potentially confusing statement: when stating "we do not yet know", the "we" denotes the student or class, not the CS community -- regular expressions are definitely not closed under infinite union!
  • p. 86, part 5 of Exercise 3.4, third line:
    string 10111 should read 10101.
  • p. 86, part 2 of Exercise 3.5:
    needs clarification -- the "except in the last four characters" is ambiguous; any specific clarification will do.
  • p. 87, automaton 2 of Exercise 3.7:
    the upper right-hand vertex has two arcs leaving it, both labelled 1; the downward arc should be labelled 0.
  • p. 90, Exercise 3.23:
    clarification: "the evaluation procedure defined in Exercise 3.12" should read "the forward evaluation procedure defined in Exercise 3.12"
  • p. 92, last line of Exercise 3.33:
    "Conclude that the complement of SUB(L) is finite." should read
    "Conclude that the complement of SUB(L) is regular."
• Chapter 5:
  • p. 129, Exercise 5.5:
    the items should be numbered, not bulleted
  • p. 136, last line (last line of Exercise 5.8):
    "to the recursive functions" should read "to the primitive recursive functions"
  • p. 140, line 19 (second line of the definition of b_to_u)
    should read "b_to_u(x_) = double(b_to_u(x))" -- that is, no use of Succ in this case
  • p. 148, first line below Definition 5.7:
    the comma should be omitted
  • p. 154, third line from the bottom (definition of theta(x,y)):
    "step(x,x,y) > 0" should read "step(x,x,y) = 0"
• Chapter 6:
  • p. 212, proof of Theorem 6.7, definition of F_j(I₁,I₂): the variables J and K should be quantified universally, not existentially! This error makes nonsense out of Exercise 6.10 (same page, see next erratum).
  • p. 212, Exercise 6.10 should be removed entirely (see preceding erratum).
  • p. 219, proof of Proposition 6.1, 5th and 6th lines
    (not an error, but a potentially misleading statement):
    "It then traverses each tree in postorder and records which prefixes of the guessed string (if any) can be represented by each subtree."
    In order to record such information accurately, much more than prefix information must be stored along the way: a concatenation node, for instance, will require much more general substring information. The intent was only to state that a postorder traversal can be used, with suitable bookkeeping, to extract the prefix information.
  • p. 221, Exercise 6.25, first line of second paragraph:
    "recursive sets" should read "r.e. sets"
• Chapter 7:
  • p. 245, second line from the bottom:
    the running time is O(nN), not just O(nN²), because the dynamic program, in order to fill a cell in the table of O(nN) values, need only compute the minimum of two table values. (See also Chapter 8, p. 302.)
  • p. 282, Exercise 7.50, line 2:
    "Delta₂" should read "Sigma₂"
  • p. 282, Exercise 7.50, line 3:
    "regular expression" should read "regular expressions"
• Chapter 8:
  • p. 302, second line after the equation:
    the running time is O(nN), not just O(nN²), because the dynamic program, in order to fill a cell in the table of O(nN) values, need only compute the minimum of two table values. (See also Chapter 7, p. 245.) Similarly, the last line of the second paragraph should read "in linear time" instead of "in quadratic time".
  • p. 318, third line above Theorem 8.16:
    missing a space between "PTAS" and the following parenthesis
  • p. 341, Figure 8.11:
    R and co-R should be RP and co-RP, respectively.
  • p. 341, eighth line of first paragraph:
    "p_a + 2^-p(|x|) > 1/2" should be "p_a + 2^-p(|x|) exceeds 1/2".
  • p. 341, tenth line of first paragraph:
    "so that p_a = 1/2 - 2^-p(|x|)-1" should be "so that we have p_a = 1/2 - 2^-p(|x|)-1".
  • p. 342, eleventh line of first part of proof:
    "such that r(n)+r'(n)=q(n)" should be "such that we have r(n)+r'(n)=q(n)".
  • p. 350, Exercise 8.25, third line from end of exercise:
    there should be a space between the period and the hint.
• Chapter 9:
  • p. 389, third line before Exercise 9.9:
    "less ambitious results" should be "less ambitious result"
• Index:
  • Under "Clique" there should be a reference to pp. 333-334.