Typographical errors and clarifications: Page viii, line 2: "Multiprocessor Scheduling / 65" should be Multiprocessor Scheduling / 66" Page 12 - caption for Figure 2.1 should be "Truth table of P -> Q". Page 12 - last 2 paragraphs: "a conjunction of disjunction of literals" should be "a conjunction of a disjunction of literals" "a disjunction of conjunction of literals" should be "a disjunction of a conjunction of literals" Page 14 - first sentence of the Example: there is a parenthesis "(", but there is no ")" until the end of the sentence; there should be a ")" before the "." Page 14 - first Example: "C1: P v " should be "C1: P v Q". Page 15 - Figure 2.4: 1. the column for C should have 8 more occurrences of "T" for the positions 5-8 and 13-16 2. the column for F1 should have 8 "F" at the ositions 17-24 3. the column for F2 should have "F" at the positions 5-6, 13-14, 21-22, 29-30 4. the column for F3 should have "T" at the positions 2, 4-8, 10, 12-32 5. the column for F4 should have "T" at the positions 2-4, 6-16, 18-20, 22-32 (optional) Page 16, line -3, step (3) of Resolution procedure: the definition of Ri(S) is given at page 26, lines -6,-5. (The next edition will give this definition before step (3).) Page 17 - C_7 is the resolvent of C1 and C_4 (not C_2). Page 29, line 9: "A subtstring" should be "A substring" Page 29, line -5: "L(\alpha^*)=L(a)^*" should be "L(\alpha^*)=L(\alpha)^*" Page 35, picture of "Sensor_Controller". The arrows labelled with "no_pedestrian" and "turn_don't_walk" should have a reversed sense (between S_0 and S_1). (optional) Page 42, definition of task "T_i": can write T" instead of "T_i" because the index "i" in not appearing in "S", "c", "d", "D". We can say "a task is T=(S,c,d,D,p), where ..." and "D=S+d". Page 44 - Section 3.2.1, line 6: "It does need to wait..." should be "It does not need to wait..." (optional) Page 45, Schedulabity Test 1: "U=\sum_{i=1}^n \frac{c_i}{p_i}" is the definition of "the total utilization of a task set" and the necessary and sufficient condition is "U <= 1" only if the stated conditions for tasks are met. In the next edition, I may point out that now that "If U > 1, then there is no feasible schedule for these tasks". (optional) Page 46, Schedulability Test2: It is not clear if U <= 1. So, maybe it is better to say something like "lim_{n\to\infty} n(2^{1/n} -1) = ln 2 \approx 0.6931" which is less than 1 but still O.K. (anyway more 0.5) (optional) Page 47, line 3: "a k exists" maybe it is better "a positive integer k exists" Page 51 - Proof, line 8: "interchanged" should be "interchange". Page 54 - 1st paragraph, last sentence: "J1" should be "J2". Page 56 - First example: "J3: c3 = 15" should be "J3: c3 = 20" Page 57 - Example, line 10: "c1 = 50" should be "c2 = 50". Page 57, line -3 of paragraph "A sporadic task J_2 ...": "J_1" should be "J_2". Page 57, line 2 of paragraph "Schedulability Test 7: ...": "U_s=c_i/p_s" should be "U_s=c_s/p_s". Page 58, line 9 of Section "3.2.2": "low-prioirty" should be "low-priority". (optional) Page 62, line 14: "the precedence constraints are:" maybe is better to say "the precedence constraints between blocks are:" (optional) Page 62, Example: Maybe it is better to say somewhere at the end of it that "L=LCM(p_1,p_2,p_3)=12" (optional) Page 62, Algorithm, statement "2.": Is "T_{i,j}$ a notation for "T_i(j)"? Yes. Moreover, the expression "(k-1)p_i+d_i" doesn't contain "j"? Is it O.K.? Yes, each block in the the same task is initially assigned the same deadline. (optional) Page 62, Algorithm, statement "3.": By "d'_S- c'_S" do you meant "d_{S'}-c_{S'}"? I mean that "'" belongs to S, not to d or c, isn't it? Yes. (optional) Page 63, Figure 3.18: the graphical representation for T_2, maybe it is better to highlight the break between T_{2,2} and T_{2,1}? At time 6, since c_{2,2} = 2. I wasn't able to understand where can be T_{2,3} and T_{2,4}? Are they the same like T_2(3) and T_2(4)? Yes. (optional) page 63, line 2 of paragraph "Without ...": Maybe it is better to say after "Figure 3.18." something like "Figure 3.18 because T_2(2) should be before 5 time units and T_2(4) should be before 5+6=11 time units". (optional) Page 63, line 5 of section 3.2.5: Maybe it is better to say after [Mok, 1984] something similar to "A task in a critical section cannot be preempted" Page 64 - Example: "At time 8 after completing the second block of T1..." should be "At time 8 after completing the first block of T1..." Figure 3.20: deadline arrows for T2 should be at 4 and 14. Page 64, Example: I think there is an error "d_2=4" should be "d_2=5" or leave "d_2=4", but say at the last line of Example (just before Figure 3.20), "T_2 is scheduled and it misses its deadline at time 14" not "15"! (optional) Page 65, the paragraph "Therefore, we ...": It is unclear what is "q"? Is it some small real number able to define a possible delay? Page 65 - q is the length of the critical section Figure 3.22: deadline arrows for T2 should be at 4 and 14. Page 66 - Example: J3: S3 = 0 (optional) Page 67, the paragraph "Let C(i) ...": Maybe it is better to say somewhere that "let L(i)=D(i)-C(i) denote .." and "... n <= m". (optional) Page 69, line 3 of the paragraph "To derive ...": Maybe it is better to say instead of "3 regions:" something like "3 disjoint regions and k is a positive integer denoting the number of time units" (optional) Page 69, definition "F(k,i) =...": In the left hand-side it appears "i", but it doesn't appear on the right-hand side! Maybe it is better to say "C_j(i)" instead of "C_j" and "L_j(i)" instead of "L_j"? Yes, or we can omit i from F(k,i) if it is understood that the function is evaluated at an instant of time. Page 71, line -3 above from Figure 3.28: "=GCD(8,3,2,7)" should be "=GCD(10,8,3,2,7)" (optional) Page 71, Figure 3.28: what kind of schedule is used? It seems to me it isn't EDF or LL! It is RM with the following strategy: starting with an available processor, schedule as many tasks as possible, then do the same for the next available processor and so on. Rearrrange tasks in each processor to reduce context switching. Page 87, line 3: "finte" should be "finite" Page 88, Figure 4.1: "NEAR_CROSSING" shouldn't be "BEFORE_CROSSING"? Either label would be fine. And the last "GATE_DOWN" shouldn't be "GATE_UP"? "GATE_DOWN" is correct since the gate moves up only after crossing by the train. Page 89 - section 4.2, 2nd paragraph: "The following data structures and functions to access the labels..." should be "The following data structures and functions are used to access the labels..." (optional) Page 90, line 9: Maybe it is better "the array labeled[][]" as "the boolean array labeled[][]" Page 93, lines 6-7: In "O(length(f)*,(number ..." is not quite an expression, the "," should be deleted to have a multiplication operation. Page 116 - Section 4.6.1, line 6: "outdoing" should be "outgoing". Page 118, line 6 of the paragraph "Isomorphic BDDs": "h(high(v))=high(v_2)." should be "h(high(v_1))=high(v_2)." (optional) Page 119, Output of "Algorithm Restrict": Maybe it is better to add ", that is f|x=b" after "above restriction" (optional) In the next edition, two (small) examples will be included in Section 4.7.1 to illustrate the minimum and the maximum delay algorithms, respectively. Page 124 - Figure 4.8: min_count procedure: "max" on the first line after "begin" should be "min". Page 138 - Figure 4.2: transition from n2 to t2 should be labeled "p2 requests". Page 150 - Section 6.3, line 2: detele "to". Page 151, line 4 of the paragraph "Safety Assertion in English": "crossing the gate" should be "crossing, the gate" Page 151 (comments): TrainApproach and Crossing on pages 151-152 refer to the events of the train being (first) detected by the approach sensor and starting to cross the railroad crossing as detected by the Crossing sensor, respectively. Although they do not adhere to the RTL syntax, I meant to use these to signify instantaneous events (though not external). They might be considered state transition events, from non-TrainApproach to TrainApproach and from non-Crossing to Crossing, respectively. I did not use ^ (uparrow) since TrainApproach is itself an instantaneous event (as detected by the sensor), for instance, rather than the start of an action. Page 154, line 2 of the paragraph "Rewriting ...": "(x)<= g_1(x)" should be "f(x)<=g_1(x)" Page 156, Figure 6.1: the arrow from the node "g2(x)" to the node "f(x)" should be labelled with "-30" not "30". Page 159, Figure 6.2: the 15-th and 19-th node in the tree have redundant literals, namely "\not G \not B \not G" should be "\not G \not B" and "\not G \not D \not G" should be "\not G \not D". Page 160, line -3 before Section 6.6.1: "is" should be deleted from "in S_1 is unsatisfiable". (optional) Page 173, lines -5,-6: We say "A parallel mode with no child modes is equivalent to an atomic mode.". Why (because a formal definition of "equivalency" is missing)? They are equivalent because both have no internal structure. (optional) Page 176, last line of Section 6.9.2: "chapter 4" may be "Chapter 4". Page 179, line -10: "<= @(M->, x)." should be "<= @(PASSED->, x)." Page 190, line 7 of paragraph "I/O Automaton": "statesA)" should be "states(A)". (This refers to the second occurrence of "states(A)".) Page 191, line -7: "speed up: [0,t_{speedup}], slow: [0,t_{speedup}], and stop: [0,t_{speedup}], where" should be "speedup: [0,t_{speedup}], slow: [0,t_{slow}], and stop: [0,t_{stop}], where". (this refers to "speed up" without blank, and the two substitutions [slow/speedup] and [stop/speedup]. Page 191, line -2: "speed up" should be "speedup" (optional) Page 195: First time, I wasn't able to see the difference between a "timed word" and "timed trace". I just could guess that a timed word is an element of (\Sigma x R_+)^* and not \Sigma^* x R_+^*. The same missunderstanding I did it for "timed language" and "timed process". Moreover, I see the definition of "UnTime(L) \subset\Sigma^*" as: UnTime(L)={\rho_1 \rho_2 ... | \exists \tau_1, \tau_2 such that (\rho_1,\tau_1)(\rho_2,\tau_2) ... \in L} Please, am I right? Yes. Page 199, the line before "Example": "(v_{I-1}+\tau_i-\tau_{I-1})" should be "(v_{i-1}+\tau_i-\tau_{i-1})" (optional) Page 200, line 8 and line 11: the name "Buchi" has two dots over "u" (in LaTeX this symbol is \"u). Page 440, line 9 of paragraph "Throughout ...": "two-valued variables i1, i2, j1, and j2 are:" should be "two-valued variables i0, i1, j0, and j1 are:" (optional) Page 440, paragraph "Throughout ...": As explained by "x_i \in {0,1}", "two-valued" refers to something like "i=2 means i0=true and i1=false". Page 473, line 8: "[Burch et al., 1990a]" should be "[Burch et al., 1990b]" ============================================================== Many thanks go to Dr. Andrei Stefan of the National University of Singapore (NUS) for careful reading, detailed comments, and clarifying suggestions. Thanks also go to Dr. Qin Shengchao, also of NUS, for additional comments. Finally, thanks go to students in my COSC 6384 class. ==============================================================