Mathematics in Computer Science
Marie-Pierre Béal, Eugen Czeizler, Jarkko Kari, Dominique Perrin · 2008
We give a new presentation of two results concerning synchronized automata. The first one gives a linear bound on the synchronization delay of complete local automata. The second one gives a cubic bound for the mini- mal length of a synchronizing pair in a complete synchronized unambiguous automaton. The proofs are based on results on unambiguous monoids of re- lations. Mathematics Subject Classification (2000). 68Q45; 20M35; 94A45; 68R15.