有限自动机重置问题的算法研究进展

Advances on algorithms for problems of resetting finite automata

论述了最近10多年有限自动机重置问题在算法方面的研究进展。首先形式定义一些基本概念和四个有关重置的问题,给出这些问题的计算复杂性结果;然后回顾了2008年前的算法发展历程和若干结论;接着将2008年后的算法分为判定自动机是否可重置的基本算法、短重置字求解算法和最短重置字求解算法三类,分别对各个算法背后的思想、复杂度、生产的重置字的质量和存在的问题等进行分析;最后总结了这些算法的评估标准和优化策略,给出了理论上须要进一步探讨的问题。

The research progress of the algorithms for problems of resetting finite automata in the past decade were reviewed.Firstly, some basic concepts and four problems related resetting were formally defined, and then the computational complexity results of these problems were given.Secondly,the development of the algorithm before 2008 and the conclusions were reviewed.Thirdly, the algorithms born after 2008 were divided into three categories:the basic algorithm to determine whether the automata can be resettable, the algorithm for finding a short reset word and the algorithm for finding the shortest reset word. For each algorithm, the idea behind it, the complexity measurement, the quality of the produced reset word, and the drawbacks were analyzed. Finally, the valuation criteria, the strategies for optimizing of these algorithms were summarized, and the problems that need to be further explored in algorithmic theory were discussed.