Extremal synchronizing circular automata

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ý automa...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2021-12, Vol.281, p.104817, Article 104817
Main Authors: He, Yong, Chen, Xueping, Li, Gang, Sun, Shiyuan
Format: Article
Language:English
Subjects:
Augmented state
Characteristic group
Defected state
Skipped state
Uncoupling letter
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0890-5401
1090-2651
DOI:10.1016/j.ic.2021.104817