Synchronizing finite automata with short reset words

摘要

Finding synchronizing sequences for finite automata is a very important problem in many practical applications (part orienters in industry, reset problem in biocomputing theory, network issues, etc.). Problem of finding the shortest synchronizing sequence is NP-hard, so polynomial algorithms probably can work only as heuristic ones. In this paper we propose two versions of polynomial algorithms which work better than well-known Eppstein’s greedy algorithm and it is modification, a cycle algorithm, introduced by Trahtman.