Unambiguous Automata

摘要

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 minimal length of a synchronizing pair in a complete synchronized unambiguous automaton. The proofs are based on results on unambiguous monoids of relations.