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.

125 Problems in Text Algorithms

Example

Problem 114: Partially Commutative Alphabets

References