Synchronizing Sequence

Today I found another interesting problem in Sipser (refer to 1.59). The problem is the problem of synchronizing sequence, and is a "starred" problem! We are to find the upper bound of a k-state synchronizable DFA (which we are to show as $k^3$).
The definition of synchronizing sequence is somewhat intuitive. Let $M$ be a DFA and $h$ be a state of it called home. A synchronizing sequence for $M$ and $h$ is a string $s \in \Sigma^*$, where $\delta(q,s)=h$ for every $q \in Q$.

A little bit of research in net yielded interesting facts about synchronizing sequence. The problem of estimating the length of synchronizing sequence has a long history and one very important result was Cerny's conjecture which says $(k-1)^2$ is the upper bound of shortest synchronizing sequence of a k-state synchronizable DFA. He was Czech, and the paper was in his native language, so I couldn't make out a single word of what he has written.

I got hold of a paper by A. N. Trahtman, in which he proved that

every n-state aperiodic DFA with a state that is accessible from every state of the automaton has a synchronizing word of length not greater than $\frac{n(n-1)}{2}$, and therefore, for aperiodic automata as well as for automata accepting only star-free languages, the Cerny´s conjecture holds true.

Certain terms seem alien to me at first sight. For example, a star-free language is a regular language if it can be described by a regular expression constructed from the letters of the alphabet, the empty set symbol, union and concatenation but no Kleen star. An aperiodic monoid needs a bit discussion, but I will shorten it because I do not have much of an idea about it right now. An aperiodic semigroup is a semigroup such that for every $x \in S$, there exists an integer $n$ so that $x^n=x^{n+1}$. An aperiodic monoid is, in short, an aperiodic semigroup which is monoid. A syntactic monoid $M(L)$ for a language $L$ is the smallest monoid that recognizes language $L$ (??). Schutzenberger concluded that a language is star free if it is accepted by a DFA with aperiodic syntactic transition monoid. Now this transition monoid need a lot of discussion on semiautomation, so I leave it for another blog. Readers may take the pain to write down something about it, I will appreciate it.

I am marking up this blog for further discussion, not before I learn a bit about these terms though. Before writing this blog, I didn't have much of an idea how group theory can be linked to language theory. This discussion gave an insight!