1. Synchronizing Automata Preserving a Chain of Partial Orders.
- Author
-
Hutchison, David, Kanade, Takeo, Kittler, Josef, Kleinberg, Jon M., Mattern, Friedemann, Mitchell, John C., Naor, Moni, Nierstrasz, Oscar, Pandu Rangan, C., Steffen, Bernhard, Sudan, Madhu, Terzopoulos, Demetri, Tygar, Doug, Vardi, Moshe Y., Weikum, Gerhard, Holub, Jan, Žďárek, Jan, and Volkov, Mikhail V.
- Abstract
We present a new class of automata which strictly contains the class of aperiodic automata and shares with the latter certain synchronization properties. In particular, every strongly connected automaton in this new class is synchronizing and has a reset word of length $\left\lfloor\frac{n(n+1)}6\right\rfloor$ where n is the number of states of the automaton. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF