## Example

\(
\def\sa#1{\tt{#1}}
\def\dd{\dot{}\dot{}}
\)

On the alphabet $A=\{\sa{a},\sa{b},\sa{c},\sa{d}\}$
$$\sa{a}\approx \sa{b}\approx \sa{c}\approx \sa{d} \approx \sa{a}\
\Rightarrow\
\sa{abcdabcd} \equiv \sa{badbdcac}$$
due to the following commutations:

#
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.

## References

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