PREFACE





Comments (LaTex
notation used)



Change "four" to "three"
and "25" to "27"



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



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



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




CHAPTER 1





Comments (LaTex
notation used)



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



Change "empty letter"
to "empty string".



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






Replace "range" by
"codomain".



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



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






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



Replace "inputs" with
"outputs".






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




CHAPTER 2





Change "range" to "codomain".



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









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






Change font of u to roman
bold.









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



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



Add \pi_L^{(n)} before f_mult



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



Change "right" to "left".



Replace "continuous" by
"twice continuously differentiable".



Add "slope of the" before
"tangent".



Change "concave" to
"convex".



Change second > to = and
third to >=












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



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



Add "even" at the end of the
line.



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



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






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



Delete the superscript (n)



Add 1 to \lceil \log_2 n
\rceil



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






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



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



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



Replace the statement of
Prob. 2.12 b) by "Show that the size and depth of a dualrail
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."



Change n log n to n log^2
n



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



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




CHAPTER 3








Change "smaller" to "larger"



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



Change superscript (T) to
(n)






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



Insert "c," after "choice
input,"



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



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






Add "and size" before "of"



Change "machine" to "memory"



Change x1 to x and "itself"
to "zero".



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



Add "UnboundedMemory"
between "the" and "RAM"



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.



Add "input address" after
"output words"



Add 2 after second ( on lines
1 and 17






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



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



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



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












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



Change SATISFIABILITY to SAT



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



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



Change Thm. to Def. in two
places



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






Change "nondeterministic" to
"deterministic"



Change "quadratic" to
"cubic"



Change "CIRCUIT SAT" to
"SATISFIABILITY"



Move > up and move 1 right









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."



Change "fixed" to "free".




CHAPTER 4






156

15

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






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



Leftmost label should
be y instead of x



Caption should refer to
Fig. 4.3









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



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



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



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$."



Insert "accessible" before
"states"



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









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



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












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



Change \gamma to \epsilon



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



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



After "respectively" add "a
designated nonterminal start symbol"



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



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



Add "containing at least one
nonterminal symbol" to end of line









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



Change "every language" to
"the language"



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






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






Change i \leq n1 to i
\leq n



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



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



Change "terminals" to "nonterminals"



Change i \leq n1 to i
\leq n



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






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



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




CHAPTER 5





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









Delete last ) in this line



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



Insert "Breadthfirst search
is used."



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



Delete "repeated; that is,
the computation is"



Delete "breadthfirst
searching"









Add "directed" at the
beginning of the line



Change "languages" to
"grammars"






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



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



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



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



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



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



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



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."



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



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



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



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



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



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



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."






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






Change "rules" to "definition"









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






In caption, change _1 to _2
and _2 to _1



Add "and L_2 is recursively
enumerable" before comma



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



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



Change "accepts" to "halts"



Add "and encoding" after
"constructing"



Change "empty tape" to
"emtpy string"



Change "accepts" to "halts on"



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



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






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



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.



Change "accepting" to
"rejecting"



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






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






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



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






Make p bold and precede by
"state"






Change "primitive" to
"partial".

237

2

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




CHAPTER 6





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






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."



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$}$)."



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



Add "commutative" before
"ring"



Insert "over a field R" after
A



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









Insert "commutative" before
"ring"






Insert "commutative" before
"ring







251 
Theorem 6.4.3 
Because Figure 6.4 on page 252 doesn't include
computation of Y, depth bound on line 6 should be D(n) = 2D(n/2) + O(log n).
Also, change depth bound on line 8 in theorem to O(n). 

15 
Change to T(n) = 2T(n/2) + 6M(n/2)
+ 2(n/2)^2 

4 
Delete "closed" 

1, 2, 4 
Change * to \cdot 
252 
Fig. 6.14 


4, 6, 7 
Change * to \cdot 

8 
Delete "closed" 

















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

















Section 6.8.1 
New title : "Sorting Via Bitonic Merging".
Apparently, it is a common error, which I have also committed, of referring
to Batcher's bitonic merging as oddeven merging. To correct all the errors
that result, changes must be made to the following pages: 18 (TOC), 2713,
301, 30911, 316, 320, 410, 481, 482, 555. Changes are also required to
the following pages in the Index: 625, 648, 650, 661, 664, 665. 


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



Exchange y_1 and y_3 and
exchange y_0 and y_2






Change ninput to 2ninput



Change (n/2) (log n) to n (log n + 1)



Change \log n to \log n + 1



Change C(1) = 1, D(1) = 1 to C(0) = 1, D(0) = 1



Change + 2^{k1} to + 2^k and k2^{k1} to (k+1)2^k



Change D(k) = k to D(k) = k + 1









Add "commutative" before "ring"



Insert "over a field" after
"A"



Insert "over fiels" after
"that"






Insert "over a field" after
"A"






Change limit on product from
n1 to k1



Change C(1) = 1 to C(0) = 1 and D(1) = 1 to D(0) = 1



Change k2^{k1} to (k+1)2^k







CHAPTER 7








Add "in words" after "messages"



Change "message" to "word"



Change "unitlength" to "word"









Change "x[a_j]" to
"x[n+1a_j]" for j = n, n1, 1









Add , $n = 2^k$ before period.



Replace phrase starting
"or ..." with "to $p1 processors and $n  (p1) \lceil n/p \rceil$ integers
to the remaining processor"






Replace "one unit" with "zero"



Change "adds" to "sets", insert "to" before "the sum"






Change "adds to" to "sets" and add "to" before "the product"






After "array" add "and
another n1 steps to compute the last entry $c_{n,n}$."



Replace "n cells" by "as far as 2n1 cells"; Change 4n+2 to 8n2









Change "descending" to "ascending"



Change "ascending" to "descending"



Change (d1) to (d2),
a_1, 0) to a_2)





14

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



Add missing arrow to box 1



Replace by "A fully normal descending algorithm has the above steps followed by the steps in reverse order."



Replace "or descending" by
"(descending)"



Change "in" to "with", and
add
"(2T(n)) additional" before "parallel".



Delete "Each step of"; change n to 2d



Change "linear" to $n \times n$



Change 2 \sqrt{m} 1 to 2
\sqrt{m} 2; Change $m \times m$ to $\sqrt{m} \times \sqrt{m}$



Change 2 \sqrt{m} 1 to 2 \sqrt{m} 2



Change "\leq 2d" to "< 2d"



Change "\leq (2d)" to "< (2d)"



Before second period add
", where $0 \leq i,j \leq n1$






Change $1 \leq j \leq n$ to $0 \leq j \leq n1, j\not = k$



Change $1 \leq i \leq n$ to $0 \leq i \leq n1, i\not = k$



Change $C_{i,j,k}$ to $C_{i,j,0}$



Replace text beginning
"The first" with the following: "For $1 \leq i \leq n/4$ ($n/4 +1 \leq i \leq
n/2$) the top output of switch $i$ is connected to the top input of the $i$th
switch in the upper (lower) copy of $P_{n/2}$ and the bottom output is
connected to the bottom input of the $i$th switch in the lower (upper) copy of
$P_{n/2}$. The connections of output switches are the mirror image of the
connections of the input switches."



Replace "first" by "second"



Add "algorithm" after "hypercube"






Replace "in" with "with slowdown factor" and delete "steps"



Add "by destination
address" before "cooperatively"



Before "The first" add the
following: "To compare destinations, move messages to adjacent vertices on the
hypercube, compare, and then reverse the process. (Move them by sorting by
appropriate addresses.)"



Change $1 \leq i \leq k$ to $0 \leq i \leq k1$









Replace "is fully normal"
by "consists of a fixed number of normal and fully normal sequences of
steps"






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




CHAPTER 8








Delete "where $k \geq
1$,"



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






Delete NSPACE(r(n)) and add
"deterministic and nondeterministic spacebounded" before "classes".


14

Change 8.5.6 to 8.5.5TEXT



Add "for some $k \geq
1$"



The
proof of Theorem 8.6.1 has been reworked for clarity.

345

12

Change node_1 to node_2TEXT



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



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



Change VALIDITY with SATISFIABILITY



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



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.)



Replace "gate" by "circuit"









Change "Construct" to "Let"



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



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




CHAPTER 9





In caption second sentence is
"The input $x_2$ has fanout 2."









Add 4 to 3k and to  3 log_2 n



Change 3 to 4 in two places



Move the text from lines 24
and 25 to this line



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



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



Replace = 2n4 with \geq 2n3




CHAPTER 10





Caption  Replace text
starting "can be" with "Input vertices are on the bottom; edges are directed
upward. Four pebbles are shown on the graph when pebbling the leftmost
output."



Change "graph" by "of Fig. 10.1"






After "least" add "$k$ pebbles,"

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 k1TEXT


16

Change k to k1TEXT


11

Change D and E to boldTEXT

478

1

Change and to orTEXT



Drop   inside first set of ( )






Add "rows of" after "and"









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



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



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."



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



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



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



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



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



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



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






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







CHAPTER 11





Replace "by a factor of
$2^{\beta}$" by "to $S^{\beta}$"



Add "namely $\beta \approx
7$," after the comma



Replace "by a factor of
about 128" by "from S to about S^7$"



Increase step numbers 1322 by 1



Change \geq to = at end of line









Add "and the output" after "A"






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




CHAPTER 12





Replace "subtrees (leaves)"
by "leaves"



Add "H_{k1} with" after "of"
and delete "with copies of H_{k1}" and replace "itself" with "H_1"



Lines made thicker to make them all visible



Replace "a ddimensional" with "nprocessor"



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



Add "of" to the section heading



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



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



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



proportional to $n \log n$."



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



chord and a chord perpendicular to it."



Add "from the root" after "path"



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




BIBLIOGRAPHY





Citations may be off by one, two
or three places






Change "Mealey" to "Mealy"



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









Insert "directed graph 10"



Delete Euler's constant
entry















Change "Mealey" to "Mealy"



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



Delete "of closed semirings"






Delete "closed semirings"






Delete "closed" and move 251
to preceding line



Change "binary," to "binary 78"



