Note that these errata apply to the first printing only; all are corrected
in the second printing, which came out in December 1997.
Front matter, List of Notations, p. xiv, first two lines:
the up arrow and down arrow are reversed; an up arrow indicates
divergence and a down arrow convergence.
Chapter 2:
p. 26, second paragraph, 3 lines from bottom of paragraph:
cL: L -> {0,1} should be cL: Sigma* -> {0,1}
p. 30, Figure 2.9:
the first row of numbers inside the frame reads 1 2 3 4 but should
read 1 2 4 7
Chapter 3:
p. 56, middle of the paragraph:
The statement "in particular, the empty state is always unreachable"
makes the implicit assumption that every state in the automaton has at
least one defined transition. If the automaton has a state reachable
from the start state and with no defined transition, then the conversion
will create a deterministic automaton where the empty state is
reachable.
p. 61, last line, and p. 62, first three lines:
parts (i) and (ii) are reversed.
p. 69, first and second paragraphs:
the words "vertex" and "vertices" should be replaced by "state" and "states"
p. 75, third paragraph, 6 lines from bottom of paragraph:
"Although L2 does not need it" should read
"Although L6 does not need it"
p. 88, Exercise 3.13 should be starred.
p. 90, Exercise 3.22 should not be starred, but Exercise 3.24 should be.
Chapter 4:
p. 113, middle of the page. The division requires time proportional to
the square of the number of digits of the operand and thus also
to the square of the space used by the Turing machine. The second
relationship below that should then read
TimeRAM=O(TimeTM*Space2TM)
p. 114, first paragraph, just before polynomial relatedness:
to clarify, add to the end of the previous sentence
(unless the machine is oversimplified, as in a RAM limited to incrementing)
p. 119, Exercise 4.19:
"quadratic" should read "polynomial"
Chapter 6:
p. 177, middle paragraph, 8 lines from the bottom of the paragraph:
"quadratic" should read "polynomial"
p. 179, item numbered "4.", second line:
"quadratic" should read "polynomial"
p. 186, first line below Theorem 6.3:
"for deterministic space" should read "for deterministic time"
p. 187, Section 6.2.2, penultimate sentence of first paragraph:
"quadratic" should read "polynomial" and n2k should read nk+1
p. 188, first paragraph, second and fourth lines:
"quadratic" should read "polynomial" and 2k should read k'
p. 190, fifth line:
"these" should read "those"
p. 198: Figure 6.7 should be at the top of p. 198
p. 211, first line:
"to set c to true" should read "to set d to true"
Chapter 7:
p. 229, second paragraph, fifth line:
"With these two problems" should read "With these problems"
p. 238, Figure 7.5:
vertices of degree 2 should be added at each side (two in all)
p. 240, Figure 7.8:
vertices of degree 2 should be added between the variable components (two in all)
p. 248, second line:
a space is needed after the footnote symbol
p. 257, last line of first paragraph: (b,b,d) should read (b,c,d)
Chapter 8:
p. 339, first and second bullets:
a space is missing between the class name (PP, then BPP) and the verb "is".
p. 354, last paragraph, 7th line:
"Holyer [1908]" should read "Holyer [1980]"
Chapter 9:
p. 364, third line of penultimate paragraph:
"from Section 4" should read "from Chapter 4"
p. 375, second line from the bottom:
the capitalization of "Says" is spurious
p. 389, in the paragraph preceding Exercise 9.9:
the end of the second line reads "ambitious results" but should read
"ambitious result"
Appendix:
p. 425, third line:
the expression should be placed in parentheses
