Reset Sink Complexity of Regular Ideals
Frigeri, Achille, Rodaro, Emanuele · Virtual Community of Pathological Anatomy (University of Castilla La Mancha) · 2025
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)\ge C\|I\|$.