计算机科学 ›› 2019, Vol. 46 ›› Issue (11A): 535-538.
陈雪萍, 何勇, 肖芬芳
CHEN Xue-ping, HE Yong, XIAO Fen-fang
摘要: 文中给定整数n>1,对任意整数定义了自动机Cn,i,确定了自动机的簇{Cn,i|0≤i<n}中的同步自动机及它们的最短同步字。此外,根据自动机的转移损耗函数和字的权重平均损耗函数,分析了该类同步自动机在一些经典应用中的优势。
中图分类号:
[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. |
[1] | 肖芬芳,何勇,胡斌梁,王志喜. 拟陷阱同步自动机的最短同步字的长度 Length of the Shortest Synchronizing Words for Quasi-trapped Synchronizing Automata 计算机科学, 2012, 39(11): 191-193. |
|