Synchronizing monotonic automata

We show that if the state set Q of a synchronizing automaton A = (Q, ∑, δ) admits a linear order such that for each letter a ∈ ∑ the transformation δ(_, a) of β preserves this order, then A possesses a reset word of length |Q| - 1. We also consider two natural generalizations of the notion of a reset word and provide for them results of a similar flavour. © 2004 Elsevier B.V. All rights reserved.Several useful comments of the anonymous referees of the proceedings version [1] of this paper are gratefully acknowledged. The authors acknowledge support from the Education Ministry of Russian Federation, Grants E02-1.0-143 and 04.01.059, the Russian Foundation for Basic Research, Grant 01-01-00258, the President Program of Leading Scientific Schools, Grant 2227.2003.1, and the INTAS (through Network Project 99-1224 “Combinatorial and Geometric Theory of Groups and Semigroups and its Applications to Computer Science”)