Discrete Mathematics & Theoretical Computer Science, Vol 15, No 3 (2013)

Font Size:  Small  Medium  Large

The Černý conjecture for automata respecting intervals of a directed graph

Mariusz Grech, Andrzej Kisielewicz


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