I&C Journal 2021 Journal Article
Extremal synchronizing circular automata
- Yong He
- Xueping Chen
- Gang Li
- Shiyuan Sun
An n-state synchronizing automaton is said to be extremal if it has the reset threshold ( n − 1 ) 2. An extremal synchronizing automaton is specially called an extreme synchronizing automaton if it is no longer an extremal synchronizing automaton after the removal of at least one letter. The Černý automata provide an infinite sequence of extreme synchronizing automata. Besides this, up to isomorphism, only eight isolated examples of extreme synchronizing automata on at least three states have been found. Since the Černý automata and one of the eight isolated examples are circular, one may say that almost all known extreme synchronizing automata are circular. In 2006, Trahtman conjectured that no other extreme synchronizing automaton on at least three states exists. In this paper, all extremal synchronizing circular automata and all extreme synchronizing circular automata are determined. As a consequence, Trahtman's conjecture is confirmed for circular automata.