Computer Science ›› 2019, Vol. 46 ›› Issue (11A): 535-538.

• Interdiscipline & Application • Previous Articles     Next Articles

Synchronization of a Certain Family of Automata and Consumption Function Analysis

CHEN Xue-ping, HE Yong, XIAO Fen-fang   

  1. (School of Computer Science and Engineering,Hunan University of Science and Technology,Xiangtan,Hunan 411201,China)
  • Online:2019-11-10 Published:2019-11-20

Abstract: Let n be an integer greater than 1.After introducing the automaton Cn,i for each integer i,the synchronizing ones in the family {Cn,i|0≤i≤n} of automata as well as their shortest synchronizing words are determined.Moreover,in aids of the so called transition consumption functions of automata and the weighted average consumptions of words,the advantages of such synchronizing automata in some typical applications are analyzed.

Key words: Synchronizing automaton, Automaton Cn,i, Shortest synchronizing word, Transition consumption function, Weighted average consumption

CLC Number: 

  • TP301.1
[1]HOWIE J M.Automata and Languages [M].Clarendon Press,Oxford,1991.
[2] ČERN J.Poznam kakhomogeny meksperimentom s konech-nymiau to matami[J].Matematicko-fyzikalny Casopis SAV,1964,14(3):208-215.
[3]HENNIE F C.Fault detecting experiments for sequential cir-cuits[C]∥Proceedings of the Symposium on Switching Circuit Theory andLogical Design.New Jersey:USA,1964:95-110.
[4]NATARAJAN B.Some paradigms for the automated design of part feeders [J].International Journal of Robotics Research,1989,8(6):89-109.
[5]EPPSTEIN D.Reset sequences for monotonic automata[M].Society for Industrial and Applied Mathematics,Comput,1990:19500-19510.
[6]VOLKOV M V.Synchronizing automata and the cerny conjecture [C]∥International Conference on Language and Automata Theory and Applications.Berlin:Springer,2008,5196:11-27.
[7]DUBUC L.Les automates circulairesbiaisésvérifient la conjec-ture decerný[J].RAIRO Informatiquethéoriqueet Applications,1996,30(6):495-505.
[8]DUBUC L.Sur les automates circulaireset la conjecture cerný[J].RAIRO Informatiquethéoriqueet Applications,1998,32(1/2/3):21-34.
[9]KARI J.Synchronizing finite automata on Eulerian digraphs[C]∥International Symposium on Mathematical Foundations of Computer Science.Springer-Verlag,2001,259:223-232.
[10]TRAHTMAN A N.The Černý Conjecture foraperiodic automata[C]∥Discrete Mathematics Theory Computer Science,2007,9(2):3-10.
[11]STEINBERG B.The Černý conjecture for one-cluster automata with prime length cycle[J].Theoretical Computer Science,2011,412(9):5487-5491.
[12]ANANICHEV D S,VOLKOV M V.Synchronizing generalized monotonic automata[J].Theoretical Computer Science,2005,330:3-13.
[13]CUI Z H,HE Y,SUN S Y.Synchronizing bounded partially ordered automata[J].Chinese Journal of Computers,2017,1-13.
[14]PNATARAJAN B.Some paradigms for the automated design of part feeders[J].International Journal of Robotics Research,1989,8(6):89-109.
[15]LEE D,YANNAKAKIS M.Principles and methods of testing finite state machines-A survey[J].Proceedings of the IEEE,1996,84(8):1090-1123.
[16]BENENSON Y,PAZ-ELIZUR T,ADAR R,et al.Programmable and autonomouscomputing machine made of biomolecules,Nature,2001,414(1):430-434.
[17]BENENSON Y,ADAR R,PAZ-ELIZUR T.DNA molecule provides acomputing machine with both data and fuel[J].Procee-dings of theNational Academy of Science of the USA,2003,100(5):2191-2196.
[18]MARTYUGIN P.Complexity of problemsconcerning reset wordsfor cyclic and Eulerian automata [J].Theoretical Computer Science,2012,450(7):3-9.
Full text



[1] DU Wei, DING Shi-fei. Overview on Multi-agent Reinforcement Learning[J]. Computer Science, 2019, 46(8): 1 -8 .
[2] GAO Li-zheng, ZHOU Gang, LUO Jun-yong, LAN Ming-jing. Survey on Meta-event Extraction[J]. Computer Science, 2019, 46(8): 9 -15 .
[3] CAI Li, LI Ying-zi, JIANG Fang, LIANG Yu. Study on Clustering Mining of Imbalanced Data Fusion Towards Urban Hotspots[J]. Computer Science, 2019, 46(8): 16 -22 .
[4] YANG Zhen, WANG Hong-jun. Important Location Identification of Mobile Users Based on Trajectory Division and Density Clustering Method[J]. Computer Science, 2019, 46(8): 23 -27 .
[5] DENG Cun-bin, YU Hui-qun, FAN Gui-sheng. Integrating Dynamic Collaborative Filtering and Deep Learning for Recommendation[J]. Computer Science, 2019, 46(8): 28 -34 .
[6] ZHONG Feng-yan, WANG Yan, LI Nian-shuang. Node Selection Scheme for Data Repair in Heterogeneous Distributed Storage Systems[J]. Computer Science, 2019, 46(8): 35 -41 .
[7] SUN Guo-dao, ZHOU Zhi-xiu, LI Si, LIU Yi-peng, LIANG Rong-hua. Spatio-Temporal Evolution of Geographical Topics[J]. Computer Science, 2019, 46(8): 42 -49 .
[8] ZHANG Hui-bing, ZHONG Hao, HU Xiao-li. User Reviews Clustering Method Based on Topic Analysis[J]. Computer Science, 2019, 46(8): 50 -55 .
[9] LI Bo-jia, ZHANG Yang-sen, CHEN Ruo-yu. Method for Generating Massive Data with Assignable Distribution[J]. Computer Science, 2019, 46(8): 56 -63 .
[10] LU Xian-guang, DU Xue-hui, WANG Wen-juan. Alert Correlation Algorithm Based on Improved FP Growth[J]. Computer Science, 2019, 46(8): 64 -70 .