Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423664 | Electronic Notes in Discrete Mathematics | 2016 | 6 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Mariusz Grech, Andrzej Kisielewicz,