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

doi:10.11896/jsjkx.200300096

计算机科学 ›› 2020, Vol. 47 ›› Issue (11A): 599-603.doi: 10.11896/jsjkx.200300096

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

孙士远, 何勇

湖南科技大学计算机科学与工程学院湖南湘潭 411201

出版日期:2020-11-15 发布日期:2020-11-17
通讯作者: 何勇(yonghe@hnust.edu.cn)
作者简介:2499644391@qq.com
基金资助:
国家自然科学基金(61572013)

Designs and Implementations of Algorithms for Searching Terminal Words of Automata

SUN Shi-yuan, HE Yong

School of Computer Science and Engineering,Hunan University of Science and Technology,Xiangtan,Hunan 411201,China

Online:2020-11-15 Published:2020-11-17
About author:SUN Shi-yuan,born in 1995,master,is a member of China Computer Federation.His main research interest include theory of automaton and so on.
HE Yong,born in 1970,Ph.D,professor,is a member of China Computer Federation.His main research interests include Formal language and automata theory.
Supported by:
This work was supported by the National Natural Science Foundation of China (61572013).

摘要/Abstract

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

关键词: Eppstein预处理, 同步对, 同步字, 终结字

Abstract: The ranks of automata are strongly associated with the problem of the designs of parts orienters on industrial automation and Černý-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|⁴) 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.

Key words: Eppstein pre-processing, Synchronizing pair, Synchronizing words, Terminal words

中图分类号:

TP301

孙士远, 何勇. 自动机终结字查找算法的设计与实现[J]. 计算机科学, 2020, 47(11A): 599-603. https://doi.org/10.11896/jsjkx.200300096

SUN Shi-yuan, HE Yong. Designs and Implementations of Algorithms for Searching Terminal Words of Automata[J]. Computer Science, 2020, 47(11A): 599-603. https://doi.org/10.11896/jsjkx.200300096

参考文献

[1] GROSSMAN D D,BLASGEN M W.Orienting mechanical parts by computer-controlled manipulator [J].IEEE Transactions on Systems,Man,and Cybernetics,1975(5):561-565.
[2] NATARAJAN B K.An algorithmic approach to the automated design of parts orienters[C]//27th Annual Symposium on Foundations of Computer Science.IEEE,1986:132-146.
[3] ERDMANN M A,MASON M T.An exploration of sensorless manipulation[J].IEEE Journal on Robotics and Automation,1988,4(4):369-379.
[4] NATARAJAN B K.Some paradigms for the automated design of parts feeders[J].The International journal of robotics research,1989,8(6):98-109.
[5] ČERNÝ J.Poznamka k homogenym eksperimentom s konechnymi automatami,Math[J].Fyz.Cas,1964,14:208-215.
[6] STARKE P H.Eine Bemerkung über homogene Experimente[J].Elektronische Informationsverarbeitung und Kybernetik,1966,2(4):257-259.
[7] ČERNÝ J,PIRICKÁ A,ROSENAUEROVÁ B.On directableautomata[J].Kybernetika,1971,7(4):289-298.
[8] EPPSTEIN D.Reset sequences for monotonic automata[J].SIAM Journal on Computing,1990,19(3):500-510.
[9] DUBUC L.Sur les automates circulaires et la conjecture de Černy[J].RAIRO-Theoretical Informatics and Applications,1998,32(1/2/3):21-34.
[10] KARI J.Synchronizing finite automata on Eulerian digraphs[J].Theoretical Computer Science,2003,295(1/2/3):223-232.
[11] ANANICHEV D S,VOLKOV M V.Synchronizing monotonic automata[J].Theoretical Computer Science,2004,327(3):225-239.
[12] ANANICHEV D S.The mortality threshold for partially monotonic automata[C]//International Conference on Developments in Language Theory.Springer,Berlin,2005:112-121.
[13] ANANICHEV D S,VOLKOV M V.Synchronizing generalized monotonic automata[J].Theoretical Computer Science,2005,330(1):3-13.
[14] VOLKOV M V.Synchronizing automata preserving a chain ofpartial orders[J].Theoretical Computer Science,2009,410(37):3513-3519.
[15] ROMAN A.Synchronizing finite automata with short resetwords[J].Applied Mathematics and Computation,2009,209(1):125-136.
[16] ANANICHEV D,GUSEV V,VOLKOV M.Slowly synchroni-zing automata and digraphs[C]//International Symposium on Mathematical Foundations of Computer Science.2010:55-65.
[17] STEINBERG B.The Černý conjecture for one-cluster automata with prime length cycle[J].Theoretical Computer Science,2011,412(39):5487-5491.
[18] BERLINKOV M V.Synchronizing automata on quasi-euleriandigraph[C]//International Conference on Implementation and Application of Automata.Springer,Berlin,2012:90-100.
[19] CHEN X P,HE Y,XIAO F F. Synchronization of Certain Family of Automata and Consumption Function Analysis[J].Computer Science,2019,46(S2):535-538.
[20] CUI Z H,HE Y,SUN S Y. Synchronizing Bounded Partially Ordered Automata[J].Chinese Journal of Computers,2019,42:610-623.
[21] RYSTSOV I K.Rank of a finite automaton[J].Cybernetics and Systems Analysis,1992,28(3):323-328.
[22] ALMEIDA J,STEINBERG B.Matrix mortality and the Černý-Pin conjecture[C]//International Conference on Developments in Language Theory.Springer,Berlin,Heidelberg,2009:67-80.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

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

Designs and Implementations of Algorithms for Searching Terminal Words of Automata

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

Metrics

本文评价

推荐阅读 0

[1]	朱凯, 毋国庆, 袁梦霆. 关于同步部分规约的有限自动机的优化问题的近似难度 On Hardness of Approximation for Optimized Problem of Synchronizing Partially Specified Deterministic Finite Automata 计算机科学, 2020, 47(5): 14-21. https://doi.org/10.11896/jsjkx.200200073
[2]	陈雪萍, 何勇, 肖芬芳. 一类同步自动机及损耗函数分析 Synchronization of a Certain Family of Automata and Consumption Function Analysis 计算机科学, 2019, 46(11A): 535-538.
[3]	肖芬芳,何勇,胡斌梁,王志喜. 拟陷阱同步自动机的最短同步字的长度 Length of the Shortest Synchronizing Words for Quasi-trapped Synchronizing Automata 计算机科学, 2012, 39(11): 191-193.