朱 凯, 毋国庆, 吴理华, 袁梦霆

1(武汉大学 计算机学院,湖北 武汉 430072)

2(华南农业大学 数学与信息学院,广东 广州 510642)

1 引 言

有限自动机的重置(或同步)问题[1],最早由Černý在1964年提出,重置的概念从此逐渐受到关注和不间断的研究,形成了许多成果,吸引了来自计算机、数学、控制和生物领域的研究人员,这些成果已应用在离散事件系统控制、软件测试、生物信息计算[2-4]和机器人[5]等领域.重置有限自动机的关键是构造重置字(或序列):有限自动机通过运行重置字w,将从任意一个未知的或无法观测到的状态到达某个特定状态qw.这仅依赖于w自身,而与w开始运行时有限自动机所处的状态q0无关.比如,Stojanovic等人[4]2003年发表在《Nature Biotechnology》上的研究成果提出了一种称为MAYA的分子自动机,可与人对弈TIC-TAC-TOE游戏.这种自动机经过一轮对弈后需要运行重置字,将自动机带到“新一轮游戏”状态.再比如,Huffman编码作为主流的数据压缩方法之一,当压缩的文本出现错误时,仅仅一个小错误就会毁掉整个编码串.为确保数据的可靠性,可采用特殊的编码方式,向压缩数据中插入重置字,使得不论出现什么错误,解码器都可以通过运行重置字恢复.于是在一定程度上得到了抗错误的数据压缩方法[6].近年来,关于重置这一经典概念又激起了新的研究兴趣,这得益于重置字已被泛化到变迁系统的博弈和无限状态系统[7]上,对诸如分布式数据网络和嵌入式实时系统这一类的复杂系统建模有着更大的意义……