### Interpreting a New Kind of Monotonicity

The following theorem is a slight generalisation from the original monotonicity and greedy theorem:

Thm. Let R : A ← A be a preorder and S : A ←There is a way to interpret the new monotonicity condition:FA be monotonic on Rº in the sense that S .FRº . Tº ⊆ Rº . S where T :FA ←FA satisfies S . T ⊆ S. Then min R . Λ⦇S⦈ ⊇ ⦇min R . ΛS . T⦈.

S .Here we are comparing two partial solutionsFRº . Tº ⊆ Rº . S y b a a' y x a'

`a`

and `b`

, where `b`

is worse than `a`

. A complete solution `y`

is generated from `b`

. The monotonicity condition says that instead of choosing `b`

as the input, we should take another partial solution `a'`

which is transformed from `a`

by `T`

, since from `a'`

one can generate another complete solution `x`

which is better than `y`

.
The interpretation is a bit strange, though. It seems that we are mixing two different levels of solutions. The premise compares `a`

and `b`

, but the conclusion is that a solution generated from `b`

is worse than another solution generated from `a'`

, which is transformed from `a`

.

R a ----- b | | T | | ↓ | a' | S | | S | | ↓ ↓ x ----- y RIt seems to be more sensible if what the monotonicity says is like this:

R a ----- b | | T | | T ↓ ↓ a' b' | | S | | S ↓ ↓ x ----- y RThe partial greedy theorem is a special case of this theorem, where

`T`

is a coreflexive. When deriving the activity-selection problem, I do have to do some "coreflexive propagation" and fusion to make the monotonicity look like the second diagram. Maybe this peculiarity would be understood if we can solve some concrete problem by this theorem.
Another point to make: If `T`

is entire, then the conditions of the theorem would imply the original monotonicity condition:

S .Then we can just apply the original greedy theorem and get rid ofFRº . Tº ⊆ Rº . S ⇒ { composition is monotonic } S .FRº . Tº . T ⊆ Rº . S . T ⇒ { T entire } S .FRº ⊆ Rº . S . T ⇒ { S . T ⊆ S } S .FRº ⊆ Rº . S.

`T`

. So this theorem is interesting only if `T`

is not entire, which is just the case of partial greedy theorem.
And finally, we can also prove a similar variation of thinning theorem. This would potentially allow more problems to be solved by identifying this new kind of monotonicity.

--

More clarifications needed...

Labels: Program Derivation

<< 回到主頁