![]() |
Discrete Mathematics & Theoretical Computer Science |
The Cerný'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.
Source : ScholeXplorer
IsRelatedTo ARXIV 1708.04864 Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.1708.04864
|