Computer Science

Computer Science ›› 2020, Vol. 47 ›› Issue (11A): 599-603.doi: 10.11896/jsjkx.200300096

• Interdiscipline & Application • Previous Articles     Next Articles

Designs and Implementations of Algorithms for Searching Terminal Words of Automata

SUN Shi-yuan, HE Yong   

  1. 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).

PDF (PC)

506

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|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.

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

CLC Number: 

  • TP301
[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.
[1] LU Chen-yang, DENG Su, MA Wu-bin, WU Ya-hui, ZHOU Hao-hao. Federated Learning Based on Stratified Sampling Optimization for Heterogeneous Clients [J]. Computer Science, 2022, 49(9): 183-193.
[2] SHAO Zi-hao, YANG Shi-yu, MA Guo-jie. Foundation of Indoor Information Services:A Survey of Low-cost Localization Techniques [J]. Computer Science, 2022, 49(9): 228-235.
[3] ZHANG Yuan, KANG Le, GONG Zhao-hui, ZHANG Zhi-hong. Related Transaction Behavior Detection in Futures Market Based on Bi-LSTM [J]. Computer Science, 2022, 49(7): 31-39.
[4] SUN Gang, WU Jiang-jiang, CHEN Hao, LI Jun, XU Shi-yuan. Hidden Preference-based Multi-objective Evolutionary Algorithm Based on Chebyshev Distance [J]. Computer Science, 2022, 49(6): 297-304.
[5] WANG Yong, CUI Yuan. Cutting Edge Method for Traveling Salesman Problem Based on the Shortest Paths in Optimal Cycles of Quadrilaterals [J]. Computer Science, 2022, 49(6A): 199-205.
[6] LI Dan-dan, WU Yu-xiang, ZHU Cong-cong, LI Zhong-kang. Improved Sparrow Search Algorithm Based on A Variety of Improved Strategies [J]. Computer Science, 2022, 49(6A): 217-222.
[7] LU Chen-yang, DENG Su, MA Wu-bin, WU Ya-hui, ZHOU Hao-hao. Clustered Federated Learning Methods Based on DBSCAN Clustering [J]. Computer Science, 2022, 49(6A): 232-237.
[8] HU Cong, HE Xiao-hui, SHAO Fa-ming, ZHANG Yan-wu, LU Guan-lin, WANG Jin-kang. Traffic Sign Detection Based on MSERs and SVM [J]. Computer Science, 2022, 49(6A): 325-330.
[9] YANG Jian-nan, ZHANG Fan. Classification Method for Small Crops Combining Dual Attention Mechanisms and Hierarchical Network Structure [J]. Computer Science, 2022, 49(6A): 353-357.
[10] ZHANG Jia-hao, LIU Feng, QI Jia-yin. Lightweight Micro-expression Recognition Architecture Based on Bottleneck Transformer [J]. Computer Science, 2022, 49(6A): 370-377.
[11] WANG Fang-hong, FAN Xing-gang, YANG Jing-jing, ZHOU Jie, WANG De-en. Strong Barrier Construction Algorithm Based on Adjustment of Directional Sensing Area [J]. Computer Science, 2022, 49(6A): 612-618.
[12] TIAN Zhen-zhen, JIANG Wei, ZHENG Bing-xu, MENG Li-min. Load Balancing Optimization Scheduling Algorithm Based on Server Cluster [J]. Computer Science, 2022, 49(6A): 639-644.
[13] LIU Jian-mei, WANG Hong, MA Zhi. Optimization for Shor's Integer Factorization Algorithm Circuit [J]. Computer Science, 2022, 49(6A): 649-653.
[14] CHEN Bo-chen, TANG Wen-bing, HUANG Hong-yun, DING Zuo-hua. Pop-up Obstacles Avoidance for UAV Formation Based on Improved Artificial Potential Field [J]. Computer Science, 2022, 49(6A): 686-693.
[15] ZHANG Zhi-long, SHI Xian-jun, QIN Yu-feng. Diagnosis Strategy Optimization Method Based on Improved Quasi Depth Algorithm [J]. Computer Science, 2022, 49(6A): 729-732.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.