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

Designs and Implementations of Algorithms for Searching Terminal Words of Automata

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

The ranks of automata are strongly associated with the problem of the designs of parts orienters on industrial automation and Cerny-Pin conjecture on theoretical computer science.Computing ranks of automata can be turned into computing terminal words of automata.Rystsov proposed an algorithm for searching terminal words of automata with O(|A|^4)time complexity.The algorithm is the only one to compute terminal words of automata till now.Some new algorithms for searching terminal words of automata can be designed based on existing algorithms for searching synchronizing words of synchronizing automata.Theoretical analysis and experimental results show that all these new algorithms are optimizations of Rystsov algorithm.