自动机终结字查找算法的设计与实现

摘要：

自动机的秩与工业自动化中的部件定向器设计问题和理论计算机科学中的?erny-Pin猜想密切相关.计算自动机的秩可以归结于查找自动机的终结字.Rystsov于1992年提出了一个时间复杂度为O(|A|4)的自动机终结字查找算法,该算法是至今仅有的专门用于计算自动机的终结字的算法.以现有同步自动机的同步字查找算法为蓝本可以设计几种自动机终结字查找的新算法.理论分析和实验结果表明,这些新算法都是Rystsov算法的优化.

关键词：终结字、同步对、同步字、Eppstein预处理

所属期刊栏目：47

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金61572013

在线出版日期：2020-12-03（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：599-603