Reset words for commutative and solvable automata

✍ Scribed by Igor Rystsov

• Book ID: 104326194
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 451 KB
• Volume: 172
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(96)00136-3

✦ Synopsis

A reset word takes all states of a finite automaton to a single state. In this paper, it is shown that the length of the shortest reset word for a solvable automaton with n states is at most n -1 and this bound is reachable.