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