Discrete Mathematics & Theoretical Computer Science, Vol 11, No 1 (2009)

Font Size:  Small  Medium  Large

On the length of shortest 2-collapsing words

Alessandra Cherubini, Andrzej Kisielewicz, Brunetto Piochi


Given a word $w$ over a finite alphabet $\Sigma$ and a finite deterministic automaton $\A = \< Q,\Sigma,\delta \>$, the inequality $|\delta(Q,w)| \leq |Q|-n$ means that under the natural action of the word $w$ the image of the state set $Q$ is reduced by at least $n$ states. The word $w$ is $n$-collapsing if this inequality holds for any deterministic finite automaton that satisfies such an inequality for at least one word. We prove that for each alphabet $\Sigma$ there is a $2$-collapsing word whose length is $\frac{|\Sigma|^3+6|\Sigma|^2+5|\Sigma|}{2}$. Then we produce shorter $2$-collapsing and $2$-synchronizing words over alphabets of $4$ and $5$ elements.

Full Text: PDF PostScript