On the length of shortest 2-collapsing words
Alessandra Cherubini, Andrzej Kisielewicz, Brunetto Piochi
Abstract
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