Open AccessA Note on erný Conjecture for Automata over 3-Letter Alphabet
Author(s) -
Adam Roman
Publication year - 2008
Publication title -
j. autom. lang. comb.
Language(s) - English
DOI - 10.25596/jalc-2008-141
We show that the alphabet size can play an essential role in the issue of automata synchronization. We give an example of 5-state automaton (over 3-letter alphabet) not isomorphic to Cerny's one, with the minimal synchronizing word of length (n-1)2=16. It is known [2] that there is no such automaton for 2-letter alphabet.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom