# Additional Problem 6: Idempotent Equivalence (Preliminary version)

Assume we have a finite alphabet $\Sigma$ and there is an idempotent equivalence $xx\approx x$ between any two words in $\Sigma^+$. This equivalence means that any word or any factor $x$ can be replaced by $xx$ and $xx$ can be replaced by $x$. Such replacements imply an equivalence relation $\approx$ between words.

For a given alphabet the number of equivalence classes is finite, but grows considerably. For alphabets of sizes 1,2,3,4,5 the number of equivalence classes is respectively 1,2,7,160,332381.

Let $alpha(u)$ be the set of all letters appearing in $u$. With each $u\in A^*$ we associate a (characteristic) quadruple $\Psi(u)=(p,a,b,q)$, where $a,b\in \Sigma$, $pa$ is a shortest prefix and $bq$ is a shortest suffix of $u$ such that $alpha(pa)=alpha(bq)=alpha(u)$.

We refer to the classical book of Lothaire for a proof of the following fact. We must assume here it is valid.

### Lemma (Equivalence Criterion

Assume $\Psi(u)\;=\;(p,a,b,q),\ \ \Psi(v)\;=\;(p',a',b',q')$. Then, $$u\ \approx\ v\ \Leftrightarrow \ (\,p \approx p'\, \wedge\, a=a'\, \wedge\, b=b'\, \wedge \, q \approx q'\,).$$

We assume that the above lemma is valid and we are interested in an efficient algorithmic implentation of the lemma.

Assume integer alphabet (sortable in linear time). Show how to check if $x\approx y$ in $(n\cdot |\Sigma|)$ time, where $n=|x|+|y|$.

## References

• M. Lothaire. Combinatorics on Words. Addison-Wesley, 1983. Reprinted in 1997.
• J. Radoszewski and W. Rytter, Efficient testing of equivalence of words in a free idempotent semigroup, In J. van Leeuwen, A. Muscholl, D. Peleg, J. Pokorný, and B. Rumpe, editors, SOFSEM 2010: Theory and Practice of Computer Science, volume 5901 of Lecture Notes in Computer Science, pages 663-671. Springer, 2010.