树形偏序自动机的同步问题.pdf

第4 6卷 第9期2 0 2 3年9月计 算 机 学 报CH I N E S E J OUR NA L O F C OMP UT E R SV o l.4 6 N o.9S e p.2 0 2 3 收稿日期:2 0 2 1-1 1-2 3;在线发布日期:2 0 2 3-0 3-1 0.本课题得到国家自然科学基金(N o.6 1 5 7 2 0 1 3)资助.崔振河,博士,讲师,主要研究领域为自动机理论、知识表示与推理.E-m a i l:c u i z h h 3m a i l 2.s y s u.e d u.c n.王志喜,硕士,副教授,中国计算机学会(C C F)会员,主要研究领域为理论计算机科学、计算机算法.何 勇(通信作者),博士,教授,中国计算机学会(C C F)会员,主要研究领域为形式语言与自动机理论.E-m a i l:y o n g h e h n u s t.e d u.c n.树形偏序自动机的同步问题崔振河1)王志喜2)3)何 勇2)3)1)(中山大学计算机学院 广州 5 1 0 0 0 6)2)(湖南科技大学计算机科学与工程学院 湖南 湘潭 4 1 1 2 0 1)3)(服务计算与软件服务新技术湖南省重点实验室 湖南 湘潭 4 1 1 2 0 1)摘 要 对于给定的自动机,能将所有状态都转换到同一状态的输入字被称为该自动机的同步字.有同步字的自动机称为同步自动机.同步自动机已广泛应用于系统测试、编码、工业自动化、机器人技术及生物计算等领域.同步自动机研究的基本问题是自动机的同步问题(含同步性判定问题和同步字查找问题),最具挑战性的课题是证实或证伪关于同步自动机最短同步字长度的C e r n猜想.偏序自动机是具有一个相容偏序结构的自动机.同步自动机的研究从理论上可以归结到同步偏序自动机的研究上,因此,C e r n猜想成立当且仅当其对所有的偏序自动机都成立.现有的研究工作表明,C e r n猜想只对于一些结构较为特殊的偏序自动机类,包括单演自动机、广义单演自动机以及有界偏序自动机是成立的.作为偏序自动机的另一类特殊情形,本文研究关于树形偏序自动机的同步性检测问题,同步字查找问题以及C e r n猜想,主要贡献包括:讨论了树形偏序自动机与现有的几类偏序自动机之间的关系,说明了树形偏序自动机包含所有单演自动机和有界偏序自动机,并且不同于广义单演自动机类;给出了树形偏序自动机的同步性判定和同步字计算方法,特别地,证明了C e r n猜想对树形偏序自动机成立;设计了树形偏序自动机的专用同步算法,该算法的时间复杂度低于通用的自动机同步算法,且对任意n-状态同步树形偏序自动机都可以找到长度不超过(n-1)2的同步字.关键词 同步自动机;同步算法;C e r n猜想;相容偏序结构;树形偏序自动机中图法分类号T P 3 0 1 D O I号1 0.1 1 8 9 7/S P.J.1 0 1 6.2 0 2 3.0 1 9 6 1O n t h e S y n c h r o n i z i n g P r o b l e m o f T r e e-L i k e P a r t i a l l y O r d e r e d A u t o m a t aC U I Z h e n-H e1)WANG Z h i-X i2)3)HE Y o n g2)3)1)(S c h o o l o f C o m p u t e r S c i e n c e a n d E n g i n e e r i n g,S u n Y a t-S e n U n i v e r s i t y,G u a n g z h o u 5 1 0 0 0 6)2)(S c h o o l o f C o m p u t e r S c i e n c e a n d E n g i n e e r i n g,H u n a n U n i v e r s i t y o f S c i e n c e a n d T e c h n o l o g y,X i a n g t a n,H u n a n 4 1 1 2 0 1)3)(K e y L a b o r a t o r y o f S e r v i c e C o m p u t i n g a n d N e w T e c h n o l o g i e s o f S o f t w a r e S e r v i c e o f H u n a n P r o v i n c e,X i a n g t a n,H u n a n 4 1 1 2 0 1)A b s t r a c t A n i n p u t w o r d o f a n a u t o m a t o n i s c a l l e d a s y n c h r o n i z i n g w o r d i f i t t r a n s f e r s a l l s t a t e s t o a s i n g l e s t a t e.A n a u t o m a t o n h a v i n g a s y n c h r o n i z i n g w o r d i s c a l l e d a s y n c h r o n i z i n g a u t o m a t o n.S y n c h r o n i z i n g a u t o m a t a h a v e b e e n v a l i d l y a p p l i e d i n m a n y f i e l d s s u c h a s s y s t e m t e s t i n g,e n c o-d i n g,i n d u s t r i a l a u t o m a t i o n,r o b o t i c s a n d b i o l o g i c a l c o m p u t a t i o n.F o r t h e r e s e a r c h e s o n s y n c h r o-n i z i n g a u t o m a t a,t h e f u n d a m e n t a l p r o b l e m i s t h e s y n c h r o n i z i n g p r o b l e m,w h i l e t h e m o s t c h a l-l e n g i n g i s s u e i s t o p r o v e o r d i s a p p r o v e t h e C e r n C o n j e c t u r e c o n c e r n i n g t h e l e n g t h s o f t h e s h o r t e s t s y n c h r o n i z i n g w o r d s o f s y n c h r o n i z i n g a u t o m a t a.P a r t i a l l y o r d e r e d a u t o m a t a(i n b r i e f,p o-a u t o m a-t a)a r e t h e a u t o m a t a w h o s e s t a t e s e t i s e q u i p p e d w i t h a p a r t i a l o r d e r t h a t c o m p a t i b l e t o t h e i n p u t l e t t e r s.T h e o r e t i c a l l y,t h e r e s e a r c h o f s y n c h r o n i z i n g a u t o m a t a c a n b e a s c r i b e d t o t h e r e s e a r c h o f s y n c h r o n i z i n g p o-a u t o m a t a,t h u s,C e r n C o n j e c t u r e h o l d s p r e c i s e l y w h e n i t h o l d s f o r p a r t i a l l y o r-d e r e d a u t o m a t a.S o m e c l a s s e s o f p o-a u t o m a t a,s u c h a s m o n o t o n i c a u t o m a t a,g e n e r a l i z e d m o n o-t o n i c a u t o m a t a a n d b o u n d e d p o-a u t o m a t a,h a v e b e e n p r o v e d t o s a t i s f y C e r n C o n j e c t u r e.T r e e-l i k e p o-a u t o m a t a a r e t h e p o-a u t o m a t a w h o s e p a r t i a l l y o r d e r e d s t a t e s e t i s t r e e-l i k e,i n o r d e r t o e x-t e n d t h e r e s e a r c h o f C e r n C o n j e c t u r e t o a m o r e g e n e r a l c a s e o f p o-a u t o m a t a,t h i s p a p e r c o n s i d e r s t h e s y n c h r o n i z a t i o n o f t r e e-l i k e p o-a u t o m a t a.A m e t h o d t o c h e c k t h e s y n c h r o n i z a t i o n a n d f i n d a s y n c h r o n i z i n g w o r d(w h e n i t e x i s t s)f o r a n a r b i t r a r y t r e e-l i k e p o-a u t o m a t o n i s i n v e n t e d.W i t h t h e a p p l i c a t i o n o f s u c h a m e t h o d,t h e C e r n C o n j e c t u r e i s c o n f i r m e d f o r t r e e-l i k e p o-a u t o m a t a,a n d a s y n c h r o n i z i n g a l g o r i t h m f o r t r e e-l i k e p o-a u t o m a t a i s d e s i g n e d.P a r t i c u l l a r l y,c o m p a r e d w i t h t h e g e n e r a l s y n c h r o n i z i n g a l g o r i t h m s,t h e c u r r e n t a l g o r i t h m h a s t h e l o w e r t i m e a n d s p a c e c o m p l e x i-t i e s,a n d i t c a n f i n d a s y n c h r o n i z i n g w o r d f o r a n n-s t a t e s y n c h r o n i z i n g t r e e-l i k e p o-a u t o m a t o n u n-d e r t h e r e s t r i c t i o n o f l e n g t h a t m o s t(n-1)2.K e y w o r d s s y n c h r o n i z i n g a u t o m a t o n;s y n c h r o n i z i n g a l g o r i t h m;t h e C e r n C o n j e c t u r e;c o m p a t i-b l e p a r t i a l l y o r d e r e d s t r u c t u r e;t r e e-l i k e p a r t i a l l y o r d e r e d a u t o m a t o n1 引 言对于给定的自动机,能将所有状态都转换到同一状态的输入字被称为该自动机的同步字.有同步字的自动机称为同步自动机.从定义上来看,同步自动机似乎是一类非常特殊的自动机,但从统计意义上来说绝大部分自动机是同步的1.多个领域的研究人员曾相互独立地发现了同步自动机:1 9 5 6年,计算机科学家A s h b y首先发现了同步自动机2;1 9 6 4年,控制学家C e r n在研究计算机的重置问题时也发现了同步自动机3;同年,电子学家H e n n i e在研究电子设备的故障检测问题时又发现了同步自动机4;1 9 8 5年,工业自动化专家N a t a r a j a n在考虑流水线上待装配部件的定位问题时再一次发现了同步自动机5-6.几十年来,同步自动机得到了深入的研究,并已被广泛应用于重启装置的设计、系统测试、编码、通信、工业自动化、机器人学以及生物计算等领域7-1 7.V o l k o v对同步自动机的研究及应用进行了详细的介绍1 8.同步自动机研究的基本问题是自动机的同步问题(包括自动机的同步性检测问题和同步自动机的同步字查找问题).对于自动机的同步性检测问题,C e r n和E p p s t e i n先后发现了同步自动机的如下判定方法:一个自动机同步的充分必要条件是它的任意两个不同状态都同步3,1 9.E p p s t e i n根据该判定方法设计了一种时间复杂度和空间复杂度分别为O(m n2)和O(n2)的自动机同步性检测算法1 9,这里的m和n分别表示自动机的输入字母数和状态数(后续类似的情况不再说明).对于同步自动机的同步字查找问题,N a t a r a j a n首先针对一类特殊的循环自动机设计了一种时间复杂度为O(m n4)的同步字查找算法5-6.E p p s t e i n改进了N a t a r a j a n的算法,并针对所有自动机提出了一种同步字查找算法1 9.E p p s t e i n的同步字查找算法以他的上述同步性检测算法为基础.E p p s t e i n的同步性检测算法与他的同步字查找算法连接在一起就是一个能完整解决自动机同步问题的算法,称为E p p s t e i n同步算法.该同步算法是目前最常用的自动机同步算法,其时间复杂度和空间复杂度分别为O(m n2+n3)和O(n2).对同步自动机的应用来说,较短的同步字通常意味着较小的开销.采用E p p s t e i n同步算法找到的同步自动机的同步字一般较长,在一些情况下不能很好地满足应用需求.为计算同步自动机的较短同步字,研 究 者 们 设 计 了 多 种 新 的 同 步 字 查 找 算法2 0-2 3.但一般来说,算法找到的同步字的平均长度越短,则算法的复杂度越高.关于自动机同步算法的研究进展可参考文献2 4.一个同步自动机的最短同步字的长度显然是该自动机所有同步字的长度的下确界,因此最短同步字的研究兼具重要的理论意义和巨大的应用价值,这自然激发了对最短同步字的研究兴趣.E p p s t e i n首先证明了最短同步字的计算是一个N P-完全问题1 9.O l s c h e w s k i等进一步证明了最短同步字的计算是一个F PN P-问题2 5.M a r t y u g i n和V o r e l则分别证明了同步循环自动机和同步欧拉自动机的最短同步字的计算问题是N P-完全的2 6-2 7.2691计 算 机 学 报2 0 2 3年对于同步自动机的最短同步字的长度,C e r n于1 9 6 4年提出了如下猜想3:n-状态同步自动机的最短同步字的长度不超过(n-1)2.C e r n猜想也可以表述为“所有n-状态同步自动机的最短同步字长度的上确界为(n-1)2”,或者“所有n-状态同步自动机都有长度不超过(n-1)2的同步字”.T r a h t-m a n通过穷举证实了C e r n猜想对状态数不超过1 0且输入字母数不超过4的自动机以及状态数为1 1或1 2且 输 入 字 母 数 为2的 自 动 机 成 立2 8.K i s i e l e w i c z等设计了一种具有指数时间复杂度和空间复杂度的最短同步字查找算法,并用该算法计算了数十万个随机生成的状态数不超过3 5 0的同步自动机的最短同步字,没有发现否定C e r n猜想的例子2 9.P i n和S z y k u a先后从理论上证明了任意同步自动机的最短同步字长度均不超过其状态数的立方 3 0-3 1.R y s t s o v等证明了C e r n猜想对于可解自动机、循环自动机、欧拉自动机等若干类特殊自动机成立3 2-3 9.M a r t u g i n等则讨论了一系列最短同步字长度接近或等于C e r n界的自动机4 0-4 5.尽管对C e r n猜想的研究已取得许多进展,但该猜想仍未得到证实或证伪,且已经成为了自动机的组合理论领域存留时间最长的公开问题4 6-5 0.H e n c k e l l和P i n等在研究序幺半群时通过对自动机的状态集赋予一个相容于所有输入字母的偏序关系引入了偏序自动机的概念5 1.每个偏序自动机都具有相互联系的一个自动机结构和一个偏序集结构.同步偏序自动机就是自动机结构是一个同步自动机的偏序自动机.因为任何(同步)自动机关于其 状态集上 的离散序都 能 构 成 一 个(同步)偏序自动机,所以同步自动机的研究从理论上可以归结为同步偏序自动机的研究,且C e r n猜想成立的充分必要条件是它对所有的同步偏序自动机成立.这既为同步偏序自动机的研究提供了理论背景,也为同步自动机和C e r n猜想的研究提供了一条新途径.A n a n i c h e v和V o l k o v率先开展了对同步偏序自动机的研究.他们首先证明了同步单演自动机(即具有一个相容全序结构的同步自动机)的最短同步字长度小于其状态数减1,从而证实了C e r n猜想对单演自动机成立5 2.接下来,他们将同步单演自动机的上述特征完整地扩展到了同步广义单演自动机上5 3.崔振河等则证实了同步单演自动机的上述特征也能完整地扩展到同步有界偏序自动机(即具有一个相容有界偏序结构的同步自动机)上5 4.由A n a n i c h e v和V o l k o v开辟的这一研究路线的核心思想在于:首先针对一些结构较为特殊的偏序自动机证实或证伪C e r n猜想,然后逐步推广至一般结构的偏序自动机的情形,进而寻求C e r n猜想的彻底解决.树形偏序自动机是具有相容树形偏序结构的自动机,从自动机的结构来看,它是比有界偏序自动机更为一般的一类偏序自动机.然而,C e r n猜想对于树形偏序自动机是否成立目前仍然是未知的.参考A n a n i c h e v和V o l k o v的研究思路,本文对树形偏序自动机的同步问题展开讨论,目的是给出树形偏序自动机的同步性检测和同步字查找方法,进而针对树形偏序自动机完全解决C e r n猜想这一公开问题.本文的研究意义在于:关于树形偏序自动机的研究此前主要聚焦于利用其揭示某些逻辑理论的可判定性等5 5-5 6,而对于树形偏序自动机的同步问题的研究基本上还是空白.本文首次对树形偏序自动机的同步问题展开讨论,这不仅能够在一定程度上推动C e r n猜想的研究,也能为后续的关于同步偏序自动机的研究提供借鉴.本文总共分为7节:第2节介绍一些预备知识;第3节定义树形偏序自动机,讨论树形偏序自动机与单演自动机、广义单演自动机、有界偏序自动机之间的关系;第4节提出树形偏序自动机的同步检测方法和同步字查找方法,并证明树形偏序自动机满足C e r n猜想;第5节描述树形偏序自动机的同步算法;第6节将树形偏序自动机的同步算法应用于单演自动机和有界偏序自动机,有力地加强了此前关于同步单演自动机和同步有界偏序自动机的结论;第7节简单总结全文的工作,并提出关于树形偏序自动机的几个有待进一步研究的问题.2 基本概念与记号为提高内容的完整性及避免不必要的误解,本节陈述关于自动机、同步自动机、偏序集和偏序自动机的一些基本概念和结论,并约定一些记号.未说明的术语和记号可参阅文献5 7-5 9.2.1 自动机 任意(完全确定有限)自动机可以形式化地定义为一个形如A=(Q,)的三元组,其中Q为有限状态集,为输入字母表,是一个从集合Q 到集合Q的函数,称为状态转换函数.集合Q 36919期崔振河等:树形偏序自动机的同步问题中的序对(q,a)在状态转移函数下的像(q,a)称为输入字母a在状态q上的作用,通常记作qa.下文只考虑状态集不为空集的自动机.自动机A=(Q,)的输入字母的有限序列称为A的 输 入 字.A的 所 有 输 入 字 的 集 合 记 为*,其中的空字用e表示.A的输入字w的长度记为|w|.A的输入字w,u的连接w u仍是A的输入字,并且有|w u|=|w|+|u|.A的输入字w在状态q上的作用qw归纳定义为qw=qw=e,qu a u*,a,w=u a.A的输入字w在Q的子集P上的作用定义为P w=pw|pP.如果等式pw=q对于A的两个状态p,q以及输入字w成立,则称p能被转换为q,或者称w能将p转换为q.自动机A=(Q,)的状态转换图是一个顶点集为Q的带标签的有向图.A的状态转换图中从顶点p到顶点q且标签为输入字母a的边表示为paq.对于A的状态转换图中的道路p1a1p2a2akq,称输入字a1a2ak为该道路的标签.下文不区分自动机与其状态转换图.下述引理1给出了自动机的一个基本性质.引理15 8.n-状态自动机A的状态p能被转换到状态q当且仅当A中存在从p到q的道路,也当且仅当A中存在从p到q且长度不超过n-1的道路.当A中存在从p到q的道路时,这种道路的标签就是能将p转换到q的输入字.2.2 同步自动机 给定自动机A=(Q,).如果A的状态p和q能被某输入字w转换到同一个状态,即pw=qw,则称p和q是同步的,并称w为p和q的一个同步字.如果A的状态集Q的子集P中所有状态都能被同一个输入字w转换到同一个状态,即|P w|=1,则称P是同步的,并称w为P的一个同步字.如果A的状态集Q是同步的,则称A为一个同步自动机,并称Q的同步字为A的同步字.下面的例子来源于文献1 8,它不仅展示了同步自动机的一个实例,还隐含了同步自动机应用的基本原理.例1.假定要在流水线上为某个设备装配一个不规则部件P.该部件由从左往右运行的传送带送达装配点,在送上传送带时可能朝向方向0,1,2,3中的任意一个,其中只有方向0才适合安装.P的形状和可能朝向的四个方向如图1所示.图1 不规则部件P的形状及所有可能的方向为了使得P在到达装配点时能定位为方向0,可以在传送带右端设置H和L两种障碍物各若干,它们按照如下方案调整P的方向:当传送带右端触碰到障碍物H时,将P顺时针旋转9 0;当传送带右端触碰到障碍物L时,如果P处于方向3,则将其顺时针旋转9 0,否则保持其原方向不变.这种定位方案可以描述为图2中的自动机.该自动机是一个同步自动机,其最短同步字LHHHLHHHL能将任意状态都转换到状态0.因此,只需按LHHHLH-HHL的顺序在传送带右端设置九个障碍物即可解决P的定位问题.图2 不规则部件P的定位方案2.3 偏序关系 集合上的相等关系和泛关系分别记为和.集合上自反的、反对称的、传递的二元关系称为偏序关系或偏序,一般用符号来表示.偏序关系中的序对(x,z)通常表示为xz,特别地,xz表示xz且xz.若在集合上给定一个偏序关系,则称该集合按照偏序关系构成一个偏序集合.集合上的相等关系在看作偏序关系时通常称为离散序.给定集合P上的偏序关系,对于P的元素x和z,如果xz且P的任何元素y都不满足条件xy|Qi|(1 0)Qi-1uiQiT(1 1)由公式(9)和(1 0)可以断定一定存在不超过|Q-T|的正整数l使得Ql-1=Ql.现在令u=u1u2ul,根据公式(1 1)和(8)可以得到Q0u=Q0u1u2u3ul(Q1T)u2u3ulQ1u2u3ulT(Q2T)u3ulTQ2u3ulTQl-1ulT=T.由上述公式(1 1)和公式(8)还可以进一步得到Q u=(Q0T)u=(Q0u)(T u)T.因此,对T的任意同步字w都有|Q u w|=|(Q u)w|Tw|=1,即u w是A的一个同步字.证毕.引理1 4说明了同步树形偏序自动机的最短同步字的长度不超过(n-1)2.引理1 4.如果A是同步的,则它一定有长度不超过(n-1)2的同步字.证明.假定A是同步的,分别用t和s表示T和Q-T中的状态数,则显然有n=t+s(1 2)下面考察引理1 3的证明中构造的A的同步字u w=u1u2ulw(1 3)首先,在引理1 3的证明中已经说明了l|Q-T|=s(1 4)其次,由引理1 2可以知道T中全体极大状态的集合m a x(T)是非空的,且在A中一定存在从最小状态0到m a x(T)的道路.令为从0到m a x(T)的一条最短道路.由0T以及公式(8)可以断定经过的所有状态都在T中,因此的长度不超过t-1.由引理1 2可以知道的标签是T的一个同步字.取公式(1 3)中T的同步字w为的标签,则|w|t-1(1 5)最后,由引理1 3可以知道Q-T中任意状态都可以被转换到T中.这说明,对于Q-T中的任意状态q,在A中一定存在从q到T的道路.显然,A中从q到T的最短道路的长度不超过s,从而Q-T中任意状态都可以被一个长度不超过s的输入字转换到T中.据此,可以选择输入字ui使得|ui|s (i=1,2,l)(1 6)利用等式(1 2)以及不等式(1 4)(1 6)可以得到|u w|=|u|+|w|s2+(t-1)=s+(t-1)2-2s(t-1)-(t-1)2+(t-1)=(n-1)2-2s+(t-1)-1(t-1)=(n-1)2-(n+s-2)(t-1)(n-1)2.因此,A有长度不超过(n-1)2的同步字.证毕.综合引理1 01 4可以得到以下结论.定理1 5.假定A=(Q,)为一个n-状态树形偏序自动机,为A的一个相容树形偏序结构.记A的最小状态为0,定义S=sQ|(w*)s=0w,并令T=tQ|(sS)ts.0791计 算 机 学 报2 0 2 3年则T是Q的一个非空同步子集,且任意能将最小状态0转换为T中一个极大状态的输入字都是T的同步字.A是一个同步树形偏序自动机的充分必要条件是Q-T中所有状态都能被转换到T中.A在同步的情形下,它有长度不超过(n-1)2的同步字.结合上述定理以及C e r n猜想的内容,可得以下的定理1 6.定理1 6.C e r n猜想对所有同步树形偏序自动机都成立.5 树形偏序自动机的同步算法本节介绍关于树形偏序自动机的同步问题的两种同步算法:第一种是通用的自动机E p p s t e i n同步算法;第二种则是根据定理1 5设计的树形偏序自动机的专用同步算法.由这两种算法的复杂度之间的差异可以说明自动机的相容偏序结构对自动机的同步问题的解决是有益的.5.1 自动机的E p p s t e i n同步算法 自动机的E p p s t e i n同步算法包括E p p s t e i n同步性检测算法和E p p s t e i n同步字查找算法.这两个算法均以对自动机的概念为基础.给定自动机A=(Q,),令Q=Q(其中Q 为Q的所有二元子集的集合,是一个不属于Q的符号),再定义从Q 到Q 的函数 如下:(P,a)=P a P,P aQ,o t h e r w i s e.由此构造的自动机A=(Q,)称为A的对自动机1 9-2 0.下述引理1 7给出了对自动机的一个性质.引理1 71 9.自动机A的两个不同状态p,q同步的充分必要条件是在A的对自动机A中存在从状态 p,q到状态的路径.A中从 p,q到的最短路径的标签就是p,q的最短同步字.进一步地,自动机A同步的充分必要条件是它的任意两个不同状态都是同步的.自动机的E p p s t e i n同步性检测算法以引理1 7作为理论基础,其设计思想如下:对于输入自动机A=(Q,),先构造其对自动机A,再在A中以状态为起点执行反向广度优先搜索,如果能搜索到A的所有状态,则A是同步的;否则,A是非同步的.此算法的时间复杂度和空间复杂度分别为O(m n2+n3)和O(n2).自动机的E p p s t e i n同步字查找算法的设计思想如下:对于输入同步自动机A=(Q,),先构造其对自动机A,再在A中以状态为起点执行反向广度优先搜索,并记录每个状态 p,q到状态的最短路径的标签wp,q;从集合Q中任取两个不同状态p和q,将wp,q在Q上的作用Q wp,q作为新的集合Q;重复上述作用过程直到Q为一个单元集,则在此过程中选用的所有输入字wp,q的顺序连接就是A的一个同步字.此算法的时间复杂度和空间复杂度分别为O(m n2+n3)和O(n2)1 9.5.2 树形偏序自动机的专用同步算法 算法1是树形偏序自动机的一个专用同步算法,其中自动机中的路径是指该路径的标签.算法1.树形偏序自动机的专用同步算法输入:自动机A=(Q,)及其相容树形偏序结构的H a s s e图G.输出:A的同步性和A的一个同步字.(1)确定A的最小状态0(2)在A中计算集合S=sQ(w*)s=0w (3)在G中计算集合T=tQ sS ts (4)在G中计算T中所有极大状态的集合m a x(T)(5)在A中查找从0到m a x(T)的最短路径w(6)置u为空字(7)若Q-T=,R E TUR N(T r u e,u w)(8)在A中计算Q-T中各状态q到T的最短路径uq,若存在状态q没有到T的路径,R E TUR N(F a l s e,空字)(9)任取Q-T中的状态q,置u=u uq,Q-T=(Q-T)uq(1 0)若Q-T,转到(9)(1 1)R E TUR N(T r u e,u w)定理1 8.算法1的时间和空间复杂度分别为O(m a x(n2,m n)和O(n2).它不仅能判定任意n-状态树形偏序自动机A的同步性,还能在A同步的情形下找到它的长度不超过(n-1)2的同步字.证明.引理1 3-1 4和定理1 5可以保证算法1的正确性,下面给出算法1的时间复杂度和空间复杂度进行的具体分析:(1)输入自动机A的最小状态0就是有向图G中唯一的入度为0的顶点,因此,在G中以任意顶点为起点进行反向搜索得到的无后续的顶点就是0.这个过程需要时间为O(n),空间为常数.(2)集合S就是在A中最小状态0能到达的所有状态的集合,因此可以通过在A中执行以0为起17919期崔振河等:树形偏序自动机的同步问题点的广度优先搜索来完成,所需时间和空间分别为A的边数O(m n)和顶点数O(n).(3)集合T就是在G中到S有路径的顶点的集合,因此可以通过在G中执行以S为起点的反向广度优先搜索来完成,所需时间和空间分别为G的边数O(n2)和顶点数O(n).(4)由集合T的定义可以知道T中的状态q是T中一个极大状态的充分必要条件为q在G中没有任何覆盖仍在T中,因此,对T做如下处理得到的集合就是m a x(T):对T中的每个状态q,在G中检查以q为起点的边,如果其中一条边的终点仍在T中,则将q从T中删除.这个过程所需时间和空间分别为G的边数O(n2)和顶点数O(n).(5)在A中以状态0为起点,按照到0的距离由近及远地顺序执行广度优先搜索至m a x(T)中的状态即终止,对此期间搜索到的每个状态都只需记录搜索到它的边.这个过程需要的时间和空间分别为A的边数O(m n)和状态数O(n).(8)在A中以T为起始集合,按照到T的距离由近及远地顺序执行反向广度优先搜索,直至找不到新的状态即终止,在此期间记录搜索到的每个状态及搜索到该状态的边.这个过程需要的时间和空间分别为A的边数O(m n)和状态数O(n).(9)和(1 0)这是一个与E p p s t e i n同步字查找算法中的迭代过程类似的迭代过程,这个过程需要的时间和空间都为O(n2).根据上述分析可知算法1的时间复杂度为O(n)+O(m n)+O(n2)+O(n2)+O(m n)+O(m n)+O(n2)=O(m a x(n2,m n,n)=O(m a x(n2,m n),空间复杂度为O(1)+O(n)+O(n)+O(n)+O(n)+O(n)+O(n2)=O(m a x(n2,n,1)=O(n2).证毕.综上所述,树形偏序自动机作为特殊形式的自动机,其同步算法相比于通用的自动机的E p p s t e i n同步算法可以有更少的时间耗损.此外,需要特别说明的是通过算法1找到的同步字并不能保证是最短同步字.单演自动机和有界偏序自动机是树形偏序自动机的两类特殊情形,因此,基于这两类自动机的结构的特殊性,还可以将算法1分别改进为这两类自动机的专用同步算法,下面具体分析.考虑算法1的输入为自动机A及其相容有界偏序结构的H a s s e图:由于有界偏序自动机的一个重要特征是既有最小状态也有最大状态,因此,算法1第1行中不仅需要确定A的最小状态,还需要确定A的最大状态,这一过程需要的时间为O(n);崔振河等5 4指出如果一个字w能够将A的最小状态和最大状态转换到同一个状态,则w就是A的一个同步字,据此,在算法1第8行中,只需要计算最大状态到T的最短路径u,并且算法不再需要进入9-1 0行中的循环;此外,如果算法1中的第8行能够找到最大状态到T的最短路径u,则将u与算法1第5行中的w连接在一起并输出,否则自动机A不同步.最后,根据定理1 8证明中的时间和空间复杂度的分析过程可得基于算法1改进的有界偏序自动机的专用同步算 法的时间和 空 间 复 杂 度 分 别 为O(m a x(n2,m n)和O(n2).此前,崔振河等基于对自动机提出了有界偏序自动机的同步算法(见文献5 4,算法3),主要思想是:首先构造给定有界偏序自动机的对自动机的状态转换图,然后在该图中寻找一条从最大最小状态对到单一状态对的最短路径,该路径的标签即为输入的有界偏序自动机的最短同步字.这一算法的时间和空间复杂度均为O(n2),与此相比,上述基于本文算法1改进的有界偏序自动机的专用同步算法并不具备明显的优势.对于单演自动机,A n a n i c h e v和V o l k o v并未给出其专用的同步算法5 3,但仍然可以通过改进算法1来得到单演自动机的专用同步算法.由于单演自动机是一类特殊的有界偏序自动机,因此,上述基于算法1改进的有界偏序自动机的专用同步算法也同样适用于单演自动机,特别地,由于单演自动机的状态集合关于偏序关系构成一条链,因此,算法1第4行中的集合m a x(T)事实上仅包含一个元素,即最小状态能够到达的所有状态中最大的一个.广义单 演 自 动 机 以 及-单 演 自 动 机 均 采 用E p p s t e i n算法作为其同步算法.考虑到树形偏序自动机与这两类自动机的结构之间的显著差异,这两类自动机的同步算法无法通过简单地改进树形偏序自动机的同步算法而得到,需