Reset Sink Complexity of Regular Ideals

We explore synchronizing automata from a language theoretic point of view by studying the ideal I of the reset words, focusing on the reset decomposition complexity rdc(I), and a new notion of reset sink complexity rsc(I) that we introduce. The reset sink complexity is a dual parameter to reset decomposition complexity, specifically associated with automata possessing a sink state. We first address the problem of establishing sufficient conditions for an ideal to serve as the set of reset words for minimal synchronizing automata with a sink. Next, we provide a straightforward general upper bound for rsc(I) in terms of rdc(I), which we later refine for simple (or primitive) synchronizing automata. Consequently, these results yield a quadratic upper bound on the reset threshold for any synchronizing automaton with I as the set of reset words, assuming a linear lower bound rsc(I) ≥ CkIk.