Geodesic
The Černý conjecture and 1-contracting automata
Henk Don1
1Radboud University Nijmegen, the Netherlands
The electronic journal of combinatorics, Tome 23 (2016) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A deterministic finite automaton is synchronizing if there exists a word that sends all states of the automaton to the same state. Černý conjectured in 1964 that a synchronizing automaton with $n$ states has a synchronizing word of length at most $(n-1)^2$. We introduce the notion of aperiodically 1-contracting automata and prove that in these automata all subsets of the state set are reachable, so that in particular they are synchronizing. Furthermore, we give a sufficient condition under which the Černý conjecture holds for aperiodically 1-contracting automata. As a special case, we prove some results for circular automata.
DOI : 10.37236/5616
Classification : 68Q45
Mots-clés : deterministic finite automaton, synchronizing word

Henk Don  1

1 Radboud University Nijmegen, the Netherlands 
@article{10_37236_5616,
     author = {Henk Don},
     title = {The {\v{C}ern\'y} conjecture and 1-contracting automata},
     journal = {The electronic journal of combinatorics},
     year = {2016},
     volume = {23},
     number = {3},
     doi = {10.37236/5616},
     zbl = {1350.68167},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/5616/}
}
TY  - JOUR
AU  - Henk Don
TI  - The Černý conjecture and 1-contracting automata
JO  - The electronic journal of combinatorics
PY  - 2016
VL  - 23
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/5616/
DO  - 10.37236/5616
ID  - 10_37236_5616
ER  - 
%0 Journal Article
%A Henk Don
%T The Černý conjecture and 1-contracting automata
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/5616/
%R 10.37236/5616
%F 10_37236_5616
Henk Don. The Černý conjecture and 1-contracting automata. The electronic journal of combinatorics, Tome 23 (2016) no. 3. doi: 10.37236/5616

Cité par Sources :