TAOCP 5.4.4 Exercise 20

A tree is **strongly $T$-fifo** if and only if it can be labeled with $T$ labels (tape numbers) so that the following two *invalid configurations* never appear: 1.

taocpmathematicsalgorithmsvolume-3medium

Section 5.4.4: Reading Tape Backwards

Exercise 20. ▶ [22] Formulate the condition “strongly $T$-fifo” in terms of a fairly simple rule about invalid configurations of tape labels, analogous to (4′).

Verified: no
Solve time: 10m09s

Solution

A tree is strongly $T$-fifo if and only if it can be labeled with $T$ labels (tape numbers) so that the following two invalid configurations never appear:

  1. A node with two children bearing the same label.
    (This would require a single merge to read two runs from the same tape, which is impossible.)

  2. A node bearing the same label as its parent.
    (This would mean a merge reads a run from a tape and writes the merged result back to that same tape, violating the “write, rewind, read all, rewind” discipline because a read and a write on the same tape would occur in the same phase without an intervening rewind.)

These two forbidden patterns are the direct analogue of the invalid configurations (4′) for ordinary $T$-fifo trees, with the parent-child equality replacing the leftmost‑child equality that characterizes $T$-fifo.

∎