CLR cover

Problem 114: Partially Commutative Alphabets

The study of words over a partially commutative alphabet is motivated by the representation of concurrent processes in which letters are names of processes and commutativity corresponds to the non-concurrency of two processes.

We consider an alphabet $A$ for which some pairs of letters commute. This means that we can transform the word $uabv$ to $ubav$, for any commuting pair $(a,b)$. The corresponding (partial) commutativity relation on $A$ denoted by $\approx$ is assumed to be symmetric.

Two words are equivalent (with respect to the commutativity relation), denoted by $u\equiv v$, if one word can be transformed into the other by a series of exchanges between adjacent commuting letters. Observe that $\equiv$ is an equivalence relation while $\approx$ usually is not.

Design an equivalence test that checks if $u\equiv v$ for two words $u$ and $v$ of length $n$ in $A^*$ and that runs in time $O(n |A|)$.
Consider projections of words on pairs of letters.


  • R. Cori and D. Perrin. Automates et commutations partielles. ITA, 19(1):21-32, 1985.