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<n,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: Automaton Cn,i, Shortest synchronizing word, Synchronizing automaton, 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.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!