The Černý conjecture for automata respecting intervals of a directed graph
Mariusz Grech, Andrzej Kisielewicz
Abstract
The Černý's conjecture states that for every
synchronizing automaton with n states there exists a
reset word of length not exceeding (n-1)2. We
prove this conjecture for a class of automata preserving certain
properties of intervals of a directed graph. Our result unifies and
generalizes some earlier results obtained by other authors.
Full Text: PDF PostScript