The input to the algorithm is an automaton \({A} = (Q,\Sigma ,\delta )\)  with \(n\)  states and \(k\)  input letters.
The goal is to find its reset threshold \(r\) .
In the first step, we check if \({A}\)  is synchronizing by the well-known procedure [1]}, which checks for every two states \(p,q \in Q\)  whether they can be mapped to one state; this is doable in \(\mathcal {O}(kn^2)\) .
Then we get upper bounds on the reset threshold by using polynomial-time heuristics.
For this, we use the Eppstein algorithm [2]} at first, and then the enhanced beam algorithm [3]}.
The found upper bound helps the main procedure make better decisions.
