|
|
|
|
|
|
5.72 Definition(a) M is dual-monotonic on L just in case, for each  with  and each s with  we have that  . |
|
|
|
|
|
|
|
|
(b) M is dual-monotonic on  just in case M is dual-monotonic on each  . |
|
|
|
|
|
|
|
|
(c) M is dual-monotonic just in case M is dual-monotonic on each  . |
|
|
|
|
|
|
|
|
(d)  |
|
|
|
|
|
|
|
|
(e)  |
|
|
|
|
|
|
|
|
What is the relationship between [TxtEx]dual-monotonic and [TxtEx]class-dual-monotonic? What is the relationship between [TxtEx]dual-monotonic and [TxtEx]dual-strong-monotonic? |
|
|
|
|
|
|
|
|
5-18 Show that [TxtEx]class-dual-weak-monotonic = [TxtEx]dual-weak-monotonic. |
|
|
|
|
|
|
|
|
5-19 In the discussion following Definition 5.50 we mentioned that the the global version of monotonicity is equivalent to strong monotonicity. This exercise establishes this fact. |
|
|
|
|
|
|
|
|
(a) Define [TxtEx]global-monotonic, a global version on monotonicity.2 |
|
|
|
|
|
|
|
|
(b) Prove that [TxtEx]global-monotonic = [TxtEx]strong-monotonic by showing that every machine which is monotonic on N is also strong monotonic. |
|
|
|
|
|
|
|
|
(a) Show that  . |
|
|
|
|
|
|
|
|
(b) Show that  . |
|
|
|
|
|
|
|
|
(c) Use Proposition 5.60 and parts (a) and (b) to deduce:  . |
|
|
|
|
|
|
|
|
5-21 Show that  . Thus conclude that the classes [TxtEx]class-weak-monotonic, [TxtEx]weak-monotonic, [TxtEx]conservative, and [TxtEx]class-conservative are all equal. |
|
|
|
 |
|
|
|
|
2Unlike for other criteria based on strategies, for monotonic identification we used [TxtEx]monotonic to denote class monotonicity instead of global monotonicity; hence this special notation for global monotonicity. |
|
|
|
|
