计算机科学 ›› 2019, Vol. 46 ›› Issue (11A): 535-538.

• 综合、交叉与应用 • 上一篇    下一篇

一类同步自动机及损耗函数分析

陈雪萍, 何勇, 肖芬芳   

  1. (湖南科技大学计算机科学与工程学院 湖南 湘潭411201)
  • 出版日期:2019-11-10 发布日期:2019-11-20
  • 通讯作者: 何勇(1970-),男,博士,教授,CCF会员,主要研究方向为形式语言与自动机理论,E-mail:yonghe@hnust.cn。
  • 作者简介:陈雪萍(1993-),女,硕士生,CCF会员,主要研究方向为自动机理论,E-mail:1771400880@qq.com。
  • 基金资助:
    本文受国家自然科学基金(61572013),湖南省科技计划项目(2013FJ4047),湖南省研究生科研创新基金(CX2017B637)资助。

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

摘要: 文中给定整数n>1,对任意整数定义了自动机Cn,i,确定了自动机的簇{Cn,i|0≤i<n}中的同步自动机及它们的最短同步字。此外,根据自动机的转移损耗函数和字的权重平均损耗函数,分析了该类同步自动机在一些经典应用中的优势。

关键词: 权重平均损耗, 同步自动机, 转移损耗函数, 自动机Cn,i, 最短同步字

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

中图分类号: 

  • 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.
[1] 肖芬芳,何勇,胡斌梁,王志喜.
拟陷阱同步自动机的最短同步字的长度
Length of the Shortest Synchronizing Words for Quasi-trapped Synchronizing Automata
计算机科学, 2012, 39(11): 191-193.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!