Composing short 3-compressing words on a 2 letter alphabet

Alessandra Cherubini, Achille Frigeri, Zuhua Liu

A finite deterministic (semi)automaton $\mathcal{A}=(Q,\Sigma ,\delta )$ is $k$-compressible if there is some word $w\in {\Sigma }^{+}$ such that the image of its state set $Q$ under the natural action…