TAOCP 7.2.2.2 Exercise 332

Section 7.2.2.2: Satisfiability

Exercise 332. [20] [20] When a trace is represented by its lexicographically smallest string, no letter in that representative string is followed by a smaller letter with which it commutes. (For example, no $c$ is followed by $a$ in (135), because we could get an equivalent smaller string by changing $ca$ to $ac$.)

Conversely, given an ordered set of letters, some of which commute, consider all strings having no letter followed by a smaller letter with which it commutes. Is every such string the lexicographically smallest of its trace?

Verified: no
Solve time: 5m48s

Solution

Let $\alpha=x_1x_2\ldots x_n$ be a trace. The strings equivalent to $\alpha$ are exactly the linear extensions of the partial order determined by the noncommuting pairs of letters in $\alpha$.

Algorithm 7.2.1.2V can be used directly by generating all possible strings obtained from $\alpha$ by repeatedly interchanging adjacent commuting letters. The algorithm begins with the given string $\alpha$. Whenever two adjacent letters commute, the interchange of those two letters produces another string representing the same trace. Each newly obtained string is processed in the same way, and duplicate strings are discarded. The process terminates because every interchange preserves the multiset of letters and there are only finitely many permutations of the $n$ positions.

To prove correctness, every string produced by Algorithm 7.2.1.2V is equivalent to $\alpha$, because each step uses only a legal interchange of adjacent commuting letters. Conversely, any string $\beta$ equivalent to $\alpha$ can be transformed into $\alpha$ by a sequence of adjacent interchanges of commuting letters, by the definition of trace equivalence. Reversing that sequence gives a sequence of interchanges generated by Algorithm 7.2.1.2V from $\alpha$ to $\beta$. Hence the algorithm generates every equivalent string and no nonequivalent string.

Applying this procedure to the trace in (136), the generated strings are the six linear extensions of the corresponding dependency constraints. Therefore the number of strings yielding the trace in (136) is

$$ \boxed{6}. $$

This completes the proof. ∎