30

In this sentence, change 6 to 8 and move the sentence to line 39

 

30

Insert "Finally, Part II contains Chapters 6 and 7 which introduce algebraic and combinatorial circuits and parallel machine models, respectively."

 

31

Delete "introduces ... It" and move sentence after line 35. 

9

1

Insert as first sentence "An {\bf alphabet} is a finite set with at least two elements."

 

26

Change "empty letter" to "empty string".

 

-8

Change "(red,1)" to "(green,1)".

10

Sect. 1.2.5

Click here for cleaner definitions of directed graph, path, etc.

11, 12, 13

 

Replace "range" by "codomain".

13

-6,-7

Put | | around x on line -7 and around f(x) and g(x) on line -6.

15

-2

Add "other than $\epsilon" after "strings" (twice) -

16

-10

Delete "and output".

25

-6

Replace n^2/24 by n^2/16.

26

24

Replace "inputs" with "outputs".

 

-14

Replace n^3 by n^6.

31

12

Change {0,1} to {a,b,c,d}

40

3,4

Change "range" to "codomain".

43

-10

Change x_1^1 x_2^0 x_3^1 = 1 to x_1^1 \vee x_2^0 \vee x_3^1 = 0.

 

-1

Change $y_1$ to $f$ 

51

-1

Change n = 8 to n = 3.

52

1

Change (1,0) to (0,1) twice.

56

22

Click here for a clearer discussion of load balancing.

61

-10

Change font of |u| to roman bold.

62

13, 14

Delete | |.

65

2

Delete Fig.

67, 70, 71, 72

Change M_{int}(n) to M_{int}(n,c)

67

4

Insert "O(3^{\log_2 n})" after =

68

4

Add \pi_L^{(n)} before f_mult

 

7

After s. add "and $\pi_L^{(n)}$ is the projection operator defined on page 50."

69

15

Change "right" to "left".

 

23,27

Replace "continuous" by "twice continuously differentiable".

 

24

Add "slope of the" before "tangent".

 

25

Change "concave" to "convex".

71

17

Change second > to = and third to >=

72

-5

Change second n to n+1

73

3

Change f(x) to f(w)

74

11

Delete "of an n-tuple"

75

5, 15

Replace \log_2 n by \log_2 (n+1) twice on line 5 and once on line 15

76

15

The above error on page 75 introduces small errors on lines 15, 16, 23, 26, 27, and 31-34. Click here to see the corrections.

 

17

Add "even" at the end of the line.

 

26,27

Change the first two subscripts on the e's to 0 and 1.

78

20

Change "Each vertex has fan-in 2, no" to "The root has two descendants as does every other vertex except for leaves which have none. No"

79

2

Replace -/y by -1/y

 

17

Replace (d+1)N(d) by N(d+1)

 

22

Delete the superscript (n)

80

4,8,10

Add 1 to \lceil \log_2 n \rceil

 

8

Change 2^{n-1} to 2^n -1, 3 2^{n-1} to 2^{n+1}, and -1 on the right.

 

9

Change n+1 to n.

83

2

Change upper limit on second integral from n+1 to n

 

8

Add "(each vertex except a leaf has two descendants)" after "binary tree".

 

Caption to 2.24

Change "depth two and b) depth 4" to "depth one and b) depth 3"

85

3

Replace the statement of Prob. 2.12 b) by "Show that the size and depth of a dual-rail logic circuit for a function $f: {\cal B}^{n} \mapsto {\cal B}$ are at most twice the circuit size (plus the NOTs for the inputs) and at most one more than the circuit depth of $f$ over the basis \{{\sc and}, {\sc or}, {\sc not}\}, respectively."

86

24

Change n log n to n log^2 n

88

4

Change "B^n -> B^n" to B^n -> B^{kn}"

 

7

Add "0 < q < 2 ^k < \log_2 n" after comma

94

9, 10

Change \delta to \lambda

95

20

Change "smaller" to "larger"

 

-11

Change C_{\Omega} to D_{\Omega}

96

-14

Change superscript (T) to (n)

 

-7

Delete first sentence

98

6

Replace \delta_1, \lambda_1, \delta_1, \lambda_1 with "C_{\Omega}(\delta, \lambda) and D_{\Omega}(\delta, \lambda)"

 

19

Insert "c," after "choice input,"

 

27

Replace (q,a) with (q,a,c)

101, 102

 

The exposition on these pages will be improved in the next printing. (Click here to see the improvements.)

103

-2

Replace w by i

111

7

Add "and size" before "of"

 

17

Change "machine" to "memory"

113

23

Change x-1 to x and "itself" to "zero".

 

2nd column, line 3

Add new line: "CLR R_0   Clear the contents of R_0"

114

11,12

Add "Unbounded-Memory" between "the" and "RAM"

 

14

Delete "if M is in C and" and add the phrase "(A stronger definition requiring that M also be in C is used in Section 3.8.)" after sentence.

115

11

Add "input address" after "output words"

117

1, 17

Add 2 after second ( on lines 1 and 17

 

14

Change 2(m to (2m

119

11

Change (q',C) to (q',a',C)

120

2

Add "a)" before "$M$" and "b) $M$" before "accepts"

 

3

Replace this line with "and only if it is in $L$."

121

11

Change \sqrt{2 \pi} to \sqrt{2 \pi n}

124

3

Change "S(n)" to "S"

125

Fig. 3.25

Change c_0 to c_1

126

14

Delete (s_{j-1,t-1})

 

Fig. 3.26

Change output gate of SC_1 and its top input gate to OR gates, shrink circles

128

21,22

Change SATISFIABILITY to SAT

129

-4

Change \subseteq to \in in both places and replace L by L*

 

-1

Add "if $w \in L$ and 0 if $w \not\in L$".

131

Fig. 3.28

Change Thm. to Def. in two places

132

15

Change "Design a DTM" to "Design an NTM"

 

-12

Delete "that"

133

4

Change "nondeterministic" to "deterministic"

 

9

Change "quadratic" to "cubic"

 

10

Change "CIRCUIT SAT" to "SATISFIABILITY"

138

Fig. 3.31

Move > up and move 1 right

147

-3

Change z_i to c_i

149

18

Change n^2 to n^4

150

10

Add "Hint: Because such RAM programs can only have a finite number of registers, encode the contents of the TM tape as a number to be stored in one register."

151

2

Change "fixed" to "free".

155

Fig. 4.2

0 missing on top edge

156

15

Change "on input 1" to "on input 0"TEXT

158

11

second L_1 should be L_2

161

Fig. 4.6

Replace label "0" in (c) by "a"

162

Fig. 4.8

Leftmost label should be y instead of x

165

Fig. 4.15

Caption should refer to Fig. 4.3

 

6

Delete "of length k"

 

9

Change "s" to "s = q_t"

168

6

Change $r_{1,5}^{(5)} & = & 010 + (010)(10+010)^{\ast}$ to $r_{1,5}^{(5)} & = & 010 + (010)(10+010)^{\ast}(\epsilon + 10 + 010)$

 

9

Change $\epsilon + 01 + (010)(01+010)^{\ast} to $\epsilon + 01 + (01)(01+001)^{\ast} (\epsilon + 0) = (01+010)^{\ast}$

169

19, 20, 21

n \geq 0, delete r in rs = 0^d, change n to n-1 in exponent

172

-3

Add "For this purpose we extend the state transition function $\delta$ to strings $\mbox{\boldmath $a$} \in \Sigma^{\ast}$ recursively by $\delta(q,\epsilon) = q$ and $\delta (q, \sigma \mbox{\boldmath $a$}) = \delta (\delta(q, \sigma), \mbox{\boldmath $a$})$ for $\sigma \in \Sigma$."

173

3

Insert "accessible" before "states"

 

6

Insert "with finite $R_L$" after $\Sigma$.

174

-3

Change $q_0$ to $s_0$

175

-1

Change k+1 to j+1

176

7

Change "$q_R$ is an" to "$q_3$ is in a"

 

9

Change "{$q_1$}, {$q_2$, $q_3$}" to "{$q_3$}, {$q_1$, $q_2$}"

 

16

Change ",s," to ",[s],"

 

28

Change "fewer" to "more"

 

31,34,36

Change "$R$ to "$R_L$

 

-3

Change "{$q_1$}, {$q_2$, $q_3$}" to "{$q_3$}, {$q_1$, $q_2$}"

180

2

Change \gamma to \epsilon

 

Fig. 4.26

Change label from s to f to $\beta, \epsilon, \epsilon$

181

9

After "finite set $\Sigma$" insert ", with $|\Sigma| \geq 2$,"

 

14

After "respectively" add "a designated non-terminal start symbol"

182

-11

Change "$a \in V^+$ to "$a \in {\cal N}^+$

 

-10

Change {\cal N}^+ to {\cal N}

 

-10

Add "containing at least one non-terminal symbol" to end of line

183

-2

Change "1}" to "0}"

184

3

Change cMNc to cMcNc

 

-2

Add "L(G) and L(G) \cup {\epsilon}" after "languages" and change "grammar" to "grammars G"

185

-2

Change "every language" to "the language"

 

-1

Due to q -> \epsilon, G_M is not regular. Add text explaining conversion to regular language. The new page 185.

187

-4

Delete "We"

 

-3

Replace "keep the rule" by "except for", delete "and eliminate the rest as follows", delete "and", and add "or B => \epsilon"

189

-5

Delete ( and )

 

-1

Change i \leq n-1 to i \leq n

190

1

Add "and $b_{i,i+1}$" to beginning of line

 

6

Change b_{n-1,n} to b_{n,n+1}

 

9

Change "terminals" to "nonterminals"

 

10

Change i \leq n-1 to i \leq n

 

-1

Change subscript "i" in "($C \to w_i$)" to "i+2"

197

15

Change "$L$" to "$L(G)$"

201

14

The second regular expression is $(01+001)^{\ast}$.

202

-9

Remove {w | ... } and drop b) and make sentence singular

210

25

Add "exactly the" between "accepts" and "strings"

212

8

Change q_4 to q_3

213

-2

Change M_1 to M_k

214

-4

Delete last ) in this line

215

5

Insert "and the tape head at the leftmost position" after "blank tape"

216

4

Insert "Breadth-first search is used."

 

9

Add "one" at beginning, change "inputs" to "input", and add "on each step" after "tape".

 

10

Delete "repeated; that is, the computation is"

 

11

Delete "breadth-first searching"

 

-4

Change DTM to TM

218

-5

Change DTMs to TMs

 

-2

Add "directed" at the beginning of the line

219

14

Change "languages" to "grammars"

 

20

Add \beta, after \Gamma,

 

22

Add ", and not others." at end of line

220

1

Change "Rule (d)" to "Rule (e)"

 

2

Change $\beta$ to $\beta ]$ and delete "(e) removes ]"

 

7

Change "xq -> xq" to "xq -> px"

 

-5

Add Since an NDTM can be simulated by a DTM, all strings accepted by a TM can be generated deterministically in sequence."

221

16

Change the second instance of z'' to z'''

 

-13

Change "valid" to "canonical" and "can be described" to "are a subset of the strings defined".

 

-12

Replace the period that follows in this paragraph with "which a TM can analyze to insure that for each state and tape letter there is a valid action."

 

-3

Add "<, >, \widehat{<}, \widehat{>}"

 

-1

Add "preceded by $\beta$ and" after "U"

222

1

Change \widehat{[} to \widehat{w}_1

 

7

Add "It then changes < to $\widehat{<}$" before "moves"

 

10

Add "U returns to $\widehat{<}$ and removes the mark."

 

Fig 5.10

Add "The left end-of-tape marker is the blank symbol \beta" to the caption. Put \beta in a new first cell.

223

10

Replace sentence "This follows ..." by "Each must be contained in $([(<\{0, 1, \beta, \mbox{\bf L}, \mbox{\bf R}\} \# 1^{\ast}>)^3 ])^{\ast}$ and have a transition for each state and tape letter."

 

12

Delete "canonical"

 

13

Replace "does not correspond to a valid encoding" by "is not canonical".

 

-3

Add "that" in "such the"

224

20

Change "rules" to "definition"

 

-10

Delete "not"

225

9

Change w_j to w_i

226

7

Change L_2 to {\cal B}^{\ast} and add ${\cal B}$ after "alphabet"

 

 

Click here to see corrections on pages 227 through 233.

227

Fig 5.12

In caption, change _1 to _2 and _2 to _1

 

8

Add "and L_2 is recursively enumerable" before comma

228

-5

Replace "it" by "the tape" and delete "then"

228

4

Replace "if w is in L(M)" by "if and only if M halts on w"

 

-5

Change "accepts" to "halts"

 

-3

Add "and encoding" after "constructing"

 

-2

Change "empty tape" to "emtpy string"

229

10

Change "accepts" to "halts on"

 

13

Change T(M,w) to L(T(M,w))

 

15

Change T(M,w) to \rho(T(M,w))

 

16

Change second "it" to M

 

-5

Add "over ${\cal B}$" before period

230

9

In this paragraph state that T(M,w) simulates M on w and recognizes strings in L in parallel by alternatively simulating one step in each computation until one of them halts. The current argument presumes that L is recursive, not just recursively enumerable.

 

-8

Change "accepting" to "rejecting"

231

 

Replace "zero function" by "predecessor function" and delete "predecessor function" from line 8 page 232. Insert "zero function" definition after Definition 5.9.1.

232

3

Add )

233

4

Insert new paragraph stating correspondences between building blocks of partial recursive functions (composition, primitive recursion, minimilization) and straight-line programs, programs with for-loops and while loops.

 

-12

Change w_1 to w_i

234

-5

Change "L(M) = \emptyset" to "L(M) is infinite"

235

5

Change "L(G) = \emptyset" to "L(G) \not = \emptyset" and delete the hint

 

-13

Make p bold.

 

-12

Make p bold and precede by "state"

 

-10

Delete ", a"

236

6

Change "primitive" to "partial".

237

2

Add "Algebraic circuits combine operations drawn from an algebraic system."TEXT

239

19

Replace sentence by "In this section we introduce rings, fields and matrices, concepts widely used in this chapter."

 

21

Add "and Fields

 

22

Replace sentence by "Rings and fields are algebraic systems that consists of a set with two special elements, $0$ and $1$, and two operations called addition and multiplication that obey a small set of rules."

 

-7

Make sentence part of preceding paragraph and add sentence "A {\bf field} is a commutative ring in which each element other than \mbox{\boldmath $0$} has a {\bf multiplicative inverse} (for all $a \in R$, $a \not= \mbox{\boldmath $0$}$, there exists an element $a^{-1}$ such that $ a \ast a^{-1} = \mbox{\boldmath $1$}$)."

 

-6

Change "Let N be the natural numbers (the set of non-negative integers)." to "Let Z be the set of positive and negative integers." and change the second instance of N to Z.

242

-8

Add "commutative" before "ring"

243

1,3,7

Insert "over a field R" after A

 

13

Replace "the ring of positive and negative integers" with "a field R"

 

17,18

Change "ring" to "field"

245

11,19

Insert "commutative" before "ring"

247

8

Insert 3 before log n

 

-5

Insert "commutative" before "ring

 

-1,-2,-5

Change A+B to A*B

250

16

Change A^{*} to AxB

 

-3

Change "ring" to "field"

253

8

Change "ring" to "field"

254

5

Change "ring" to "field"

257

4

Change "ring" to "field"

260

2

Change "ring" to "field"

 

-6

Change "substituting A for x, we have" with "it can be shown"

263

-11

Add space after "If"

271

-1

Change <= to <

 

-5

Change <= to <

272

Fig. 6.11

Change the labels $y_1$, $y_0$, $y_2$, $y_3$ to $y_3$, $y_2$, $y_1$, $y_0$

273

Fig. 6.12

Exchange y_1 and y_3 and exchange y_0 and y_2

274

Prob. 6.1

Change N to Z

 

-16

Insert "over a field" after "A"

275

-6

Insert "over fiels" after "that"

276

5,6

Change "ring" to "field"

 

16

Insert "over a field" after "A"

 

-3,-4

Change 2n-1 to n

277

19

Change limit on product from n-1 to k-1

283

-8

Change "our" to "an"

286

287

 

 

-14

Change "right" back to "left" as in first printingTEXT

321

1

Change in \sqrt{n} to 3\sqrt{n}

329

-10

Add ", for example"

330

10

Delete "where $k \geq 1$,"

 

-3

Add "(Definitions of time and space on Turing machines are given in Section 8.4.2.)"

337

20

Change k^n to 2^{n^k}TEXT

 

21

Change k^n to 2^{n^k}TEXT

338

-6

Change 8.5 to 8.6

341

8

Delete NSPACE(r(n)) and add "deterministic and nondeterministic space-bounded" before "classes".

 

-14

Change 8.5.6 to 8.5.5TEXT

343

3

Add "for some $k \geq 1$"

 

-15

The proof of Theorem 8.6.1 has been reworked for clarity.

345

-12

Change node_1 to node_2TEXT

346

-10

Change NPSPACE(r(n)) \subseteq coNPSPACE(r(n)) to coNPSPACE(r(n)) \subseteq NPSPACE(r(n))

 

-8

Change coNPSPACE(r(n)) \subseteq NPSPACE(r(n)) to NPSPACE(r(n)) \subseteq coNPSPACE(r(n))

347

15

Change VALIDITY with SATISFIABILITY

 

19

Change \overline{VALIDITY} to coVALIDITY and fix related text.

363

-8

The statement "which implies that there is a path from \overline{x} to x" is incorrect. It is necessary to say that an instance is a "No" instance if and only if there is a variable x such that there is a path in G from x to \overline{x} and one from \overline{x} to x and to use this fact in the proof. Only small changes are needed in the argument. Figure 8.15 changed to add edges for (\overline{x}_3 \vee x_1). (Click here to see correction.)

381

-1

Replace "gate" by "circuit"

385

-4

Change b^T to c^T

386

4

Change "1" to "0".

 

6

Change "Construct" to "Let"

 

7

Replace this line with "${\cal T}$ be a set variables that have value 1. Let ${\cal T}$ be empty initially. Cycle"

 

10

Change "is" to "are" and add "Show that all satisfying assignments contain ${\cal T}$."

402

Fig. 9.4

In caption second sentence is "The input $x_2$ has fan-out 2."

 

-10

Changed 2s' -2 to 2s' +2

407

12,13

Changed (n_j -1) to n_j

411

-1

Add -4 to -3k and to - 3 log_2 n

412

1

Change 3 to 4 in two places

435

19

Move the text from lines 24 and 25 to this line

 

24

Replace the text "more ..." with "at least e(|V|/2)/2 edges."

 

-6

Replace "more than e(5n/2)" with "at least e(5n/2)/2 edges."

454

-7

Replace = 2n-4 with \geq 2n-3

471

-9

Change Problem 10.28 to Section 10.8

474

-2

Change first exponent of n to n + \lceil log n \rceilTEXT

477

-16

Change k to k-1TEXT

 

-16

Change k to k-1TEXT

 

-11

Change D and E to boldTEXT

478

1

Change and to orTEXT

 

7

Drop | | inside first set of ( )

 

14

Delete last "and rows"

 

15

Add "rows of" after "and"

 

-3

Change 2/9 to 1/3

479

7,9,10

Delete \sqrt{2}

 

11

Change n^2/6 to n^2/27; 2\sqrt{2} to 16; 6\sqrt{S} to 27\sqrt{S}; 2/9 to (.35); n^6/2 to n^6/3

482

Fig. 10.9

Change the labels $y_2$, $y_1$, $y_4$, $y_3$ to $y_4$, $y_3$, $y_2$, $y_1$

497

9,10

Replace "has a (1/\mu, m, \tau)-flow" with "is (\alpha,n,m,p)-independent for the appropriate values of \alpha, n, m, and p."

500

13

Replace "the (1/\mu, m, \tau)-flow property" with "(\alpha,n,m,p)-independence"

 

15

Replace "a (1/\mu, m, \tau)-flow" with "is (\alpha,n,m,p)-independent"

 

16

Replace everything after "for" with $p = p = \min (\lambda n, \tau(\mu m)) + \mu m"

 

18

Delete "(b)" and "(x)" after "\tau^{ast}" and the first instance of "\tau(x)"

 

25

Replace everything after "f" with is $(1/\nu, n, m, p)$-independent for $p = \tau^{\ast} + \mu m$.

521

-3

Replace "has an (\alpha, m, p)-flow" with "is $(\alpha, n, m, p)$-independent"

 

-3

Replace "has an (\alpha, m, q)-flow" with "$(\alpha, n, m, q)$-independent"

524

-12

Delete "tight"

 

-11

Add "that are within a factor of $O(\log ^2 n)$ of one another

 

-10

Change "tight" to "good"

538

Fig. 11.3

Increase step numbers 13-22 by 1

540

1

Change \geq to = at end of line

542

-16

Change ab/S to \sqrt{ab/S}

581

15

Replace "subtrees (leaves)" by "leaves"

 

16

Add "H_{k-1} with" after "of" and delete "with copies of H_{k-1}" and replace "itself" with "H_1"

585

Fig. 12.4

Lines made thicker to make them all visible

 

-6

Replace "a d-dimensional" with "n-processor"

589

-12

Reduce space between V and comma

590

3

Add "Since the lemma is true if the cost of any vertex exceeds 1/3, assume the converse."TEXT

 

5

Change "consists of the regioiu outside of all edges and vertices" to "is the face of unbounded area."TEXT

 

7

Strike the phrase "; that is, the face has ... "TEXT

591

-12

Change "a) L" to "a) H"

 

8,9,10

Change "the cycle defined by e" to $\xi(3)$

 

12

Change "the cycle defined by (x,y)" to $\xi((x,y))$

 

13

Change "the cycle defined by (x,y)" to $\xi((x,y))$

 

13

Replace "the assumption that" with "If greater than 2c(V)/3, $\xi((x,y))$ is a cycle with fewer faces which is contradicted.

 

-11

Change "e) L" to "e) H"

 

-9

After "empty" add "and $l = h = m$"

 

-7 and -6/DIV>

Change r_l and r_h to l and h

592

19

Change 2c(v)/3 to 7c(v)/9TEXT

593

1

Add "of" to the section heading

594

15

Change "P = 4" to "P = 7"

599

2

The problem now states "Show that every layout of a balanced binary tree on $n$ leaves in which the

 

2

root and the leaves are placed on the boundary of a convex region has area

 

2

proportional to $n \log n$."

 

5

Add "{\bf Hint:} Consider an inscribed quadrilateral defined by the longest

 

5

chord and a chord perpendicular to it."

600

10

Add "from the root" after "path"

 

16

Change "2c(V)/3" to "7c(V)/9"

 

 

Citations may be off by one, two or three places

609

Ref [103]

Make Kung an author

615

3 (8 in 2nd)

Change "Mealey" to "Mealy" 

626

10, Left Col

Change "binary 564" to "binary 78, 564"

630

9, Left Col

Delete "closed semiring"

632

-18, Left Col

Add 615

636

26, Left Col

Insert "directed graph 10"

637

-11, -12, -13

Delete Euler's constant entry

641

-18, Right Col

Delete "closed"

643

11, Left Col

Delete 612

644

1, Right Col

Change 613 to 614

646

7, Right Col

Add 612

648

18 and 19

Change "Mealey" to "Mealy" 

653

32, Left Col

Change "directed graph, maximal ..." by adding "10" after "graph"

655

-17, Right Col

Delete "of closed semirings"

656

8, Left Col

Add "of semirings"

658

8, Right Col

Delete "closed semirings"

 

12, Right Col

Add "semirings"

659

-14, Left Col

Delete "closed" and move 251 to preceding line

670

24, Left Col

Change "binary," to "binary 78"

672

5, Right Col

Insert "walk 10"