The maximum length of a segment satisfying a monotonic predicate (with A.J.M. van Gasteren)

The maximum length of a segment satisfying a monotonic predicate

For a given sequence $f\left( {i : 0 ≤ i < N}\right)$ , $f\left( {i : x ≤ i < y}\right)$ with $0 ≤ x ≤ y ≤ N$ is called "a segment of length

Let, with $0 ≤ x ≤ y ≤ N,B \times y$ be some predicate on segment $f\left( {i : x ≤ i < y}\right)$ such that

\underline {{A}} (x, h, k, y: 0 ≤ x ≤ h, k ≤ y ≤ N: B h k \vee ¬ B \times y);

such a predicate is called "monotonic". We know many examples of monotonic predicates, such as:

• all elements positive
• all elements equal
• ascending not containing adjacent, non-empty, equal sub- segments
• having its first differences of alternating signs.

For a $B$ that holds for any empty segment we shall derive a program establishing $R$ given by

$R : c = \max \left( {x,y : 0 ≤ x ≤ y ≤ N ∧ B \times y : y - x}\right)$

To begin with we approach the problem in the standard way by introducing a variable n satis-

[{P}_{0} : c = \max \left( {x,y : 0 ≤ x ≤ y ≤ n.\Lambda B \times y : y - x}\right) ∧ 0 ≤ n ≤ N\text{,}]

[\left\lbrack {n : \text{int};c,n : = 0,0\text{：invariant}{P}_{0}}\right\rbrack ]

[\text{z do}n ≠ N \rightarrow }]

"increase n by 1 under invariance of Po"

[\text{II}\overset{od}{ = }]

From $P \cap n ≠ N$ we conclude

\begin{array}{l} \max (x, y: 0 ≤ x ≤ y ≤ n + 1 ∧ B \times y: y - x) = \ \underline {{M A X}} (x: 0 ≤ x ≤ n + 1 ∧ B x (n + 1): n + 1 - x) \underline {{m a x}} c; \ \end{array}

for the sake of convenience we rewrite the last line as

(n + 1 - \min (x: 0 ≤ x ≤ n + 1 ∧ B x (n + 1): x)) \max c,

which suggests the introduction of a variable $h$ satisfying ${P}_{1}$ ,given by

[{P}_{1} : h = \operatorname{MIN}\left( {x : 0 ≤ x ≤ n ∧ B \times n : x}\right) ]

This yields a program of the structure

1. $n,h :$ int ; $c,n,h \mathrel{\text{:=}} 0,0,0$ (invariant) ${P}{0} ∧ {P}{1}$

[\text{；}\frac{d}{do}n ≠ N \rightarrow }]

\begin{array}{l} " e s t a b l i s h P _ {1} (n + 1 / n)" \ ; c := (n + 1 - h) \max c {P _ {0} (n + 1 / n) } \ ; n := n + 1 {P _ {0} \wedge P _ {1} } \ \end{array}

[\text{II}\overset{\text{ed}}{ = }]

Without exploiting any property of $B$ (beyond the fact that it holds for the empty segment), the Linear Search Theorem tells us that there is only one way of establishing $P_{1}(n + 1 / n)$ , viz.

A v G 27/EWD 846-2

h := 0; \underline {{d o}} \rightarrow B h (n + 1) \rightarrow h := h + 1 \underline {{o d}}

which - disregarding the evaluations of $B$ - gives in general rise to a quadratic algorithm.

From the monotonicity of $B$ ,however,we can conclude that the solution of the equation $h : {P}{1}$ is at most the solution of $h : {P}{1}\left( {n + 1/n}\right)$ ; hence, establishing ${P}_{1}\left( {n + 1/n}\right)$ can be implemented by

\underline {{d o}} \vdash B h (n + 1) \rightarrow h := h + 1 \underline {{o d}}

which - again disregarding the evaluations of $B$ - gives rise to a linear algorithm.

Note. From the above analysis follows that the mono- tonicity requirement on B is stronger than necessary: a "one-sided" monotonicity

\underline {{A}} (x, k, y: 0 ≤ x ≤ k ≤ y ≤ N: B \times k \vee ¬ B \times y)

would have sufficed. An example of such a $B$ is

B \times y \equiv A (j: x ≤ j < y: f x ≤ p _ {j})

(End of Note.)

Three remarks are in order. We have postulated that B holds for the empty segment because - see R- we did not care to define MAX over an empty bag. If B holds for any one-element segment, it is often convenient to deal with $N = 0$ separately; for $N > 0$ , the repetition can then be initialized with $n = 1$ and has $h < n$ as a further invariant.

A v g 27 / EWD 846 - 3

Secondly, the analytical structure of $B$ is, thanks to some transitivity, often such that the nett effect

can be captured by a modest alternative statement, say of the form

i f \dots \rightarrow s k i p [ ] \dots \rightarrow h := n f _ {i}

Thirdly, the assignment statement

c := (n + 1 - h) \max c

is equivalent to a skip in the case $n + 1 - h ≤ c$ , a situation implied by $N - h ≤ c$ . Once established, however, $N - h ≤ c$ is an invariant of the repetition; hence we can strengthen the guard by its negation $h + c < N$ . But since $n ≤ h + c$ is a further invariant of the repetition $n ≠ N ∧ h + c < N$ can be simplified to just $h + c < N$ .

By way of illustration we give the solution for $B \times y \equiv \underline{A}\left( {j : x ≤ j < y : fx ≤ {fj}}\right)$ .

\therefore N = 0 \rightarrow c := 0

\begin{array}{l} \mathbb {I} N > 0 \rightarrow {n, h: i n t; c, n, h := 1, 1, 0 \ ; \underline {{d o}} h + c < N \rightarrow \ i f f (n) ≥ f (h) \rightarrow s k i p [ ] f (n) < f (h) \rightarrow h := n \ ; n := n + 1; c := (n - h) \max c \ \frac {o d}{7} \ \end{array}

$\therefore m = \frac{3}{11}$

A v g _ {2 7} / E W D 8 4 6 - 4

The above $B$ is one of one-sided monotonicity. Had we chosen

B \times y \equiv \underline {{A}} (j: x ≤ j < y: f x = f _ {j})

we would have posed The Plateau Problem (see [o], p. 203, which deals with the special case that the given sequence is ordered). Its solution is obtained by replacing the inner alternative statement in the above by

i f f (n) = f (h) \rightarrow s k i p [ ] f (n) ≠ f (h) \rightarrow h := n f _ {i}

[0] Gries, David; "The Science of Programming", Springer-Verlag, New York-Heidelberg-Berlin, 1981.

drs. A.J.M.van Gasteren BP Venture Research Fellow Dept. of Mathematics and Computing Science University of Technology 5600 MB EINDHOVEN The Netherlands

16 February 1983 prof. dr. Edsger W. Dijkstra Burroughs Research Fellow Plataanstraat 5 5671 AL NUENEN The Netherlands