Article ID Journal Published Year Pages File Type
6423664 Electronic Notes in Discrete Mathematics 2016 6 Pages PDF
Abstract
In this paper we consider the Černý conjecture in terminology of colored digraphs corresponding to finite automata. We define a class of colored digraphs having a relatively small number of junctions between paths determined by different colors, and prove that digraphs in this class satisfy the Černý conjecture. We argue that this yields not only a new class of automata for which the Černý conjecture is verified, but also that our approach may be viewed as a new more systematic way to attack the Černý conjecture in its generality, giving an insight into the complexity of the problem.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,