Article ID Journal Published Year Pages File Type
10334371 Theoretical Computer Science 2005 11 Pages PDF
Abstract
In an earlier paper, we have studied reset words for synchronizing automata whose states admit a stable linear order. Here we show that the same bound on the length of the shortest reset word persists for synchronizing automata satisfying much weaker stability restriction. This result supports our conjecture concerning the length of reset words for synchronizing automata accepting only star-free languages.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,