同步(或重置)是计算系统的一个重要概念，它意味着系统的所有部分关于当前状态是一致的．有限自动机是计算系统中的一种基本模型，如果有限自动机A存在字w，那么它的动作可以重置A，即应用w后将把A带到一个特定的状态而不论自动机当前处于什么状态，此时称自动机可同步．当不知道设备的当前状况而须要恢复对设备的控制时，自然会考虑同步，其实用意义显而易见．自动机的同步常用在文本处理、编译器和计算机网络等许多领域，具体包括反应式系统的基于模型的测试[1]、生物信息[2]、机器人[3-4]和同步哈夫曼编码[5]．目前许多应用领域使用的是非确定的有限自动机，相比确定的有限自动机，其在表达上有更少的状态．对于其同步问题，近年来的研究结论主要有：判定非确定的有限自动机是否为Di-可同步的(i=1，2，3)是PSPACE-完全的[6]．而对于求解非确定有限自动机的同步字的算法、工具和统计规律有待进一步研究，这对于研究同步非确定有限自动机的平均复杂性、寻找缓慢同步非确定有限自动机的结构特征有积极意义．本研究证明了从p-D1W出发到SAT(Boolean satisfiability)的归约是固定参数易解的(fixed-parameterized tractable reduction，FPT)，同时证明了p-D1W和shortest-p-D1W分别属于para-NP和para-DP；给出了计算最短D1-同步字的二分搜索算法；采用均匀分布随机产生大量的非确定有限自动机进行实验．此外还完善了文献[7-8]的不足．1 基础知识有关参数化复杂性理论、FPT-算法及FPT-归约可参考文献[9-12]．非确定有限自动机(nondeterministic finite automata，NFA)是三元组A=(Q,Σ,δ)，其中：Q为状态的非空有限集；字母表Σ为输入符号的非空有限集；映射δ:Q×Σ→2Q为变迁函数，描述了Q中的状态以Σ中的符号为输入时的动作，其中2Q为Q的幂集．约定用n表示NFA的状态个数．对每个q∈Q和每个a∈Σ，定义状态关于输入符号的前驱集Ia(q):={p∈Q|q∈δ(p,a)}，对每个a∈Σ，定义状态q的后继集大小的最大值(上界)为hmax:=max{δ(q,a)||q∈Q,a∈Σ}．字w为Σ中符号的有限序列．Σ上所有字(包括空字ε)的集合用Σ*表示．变迁函数δ可扩展为δ:Q×Σ*→2Q，定义如下∀q∈Q，δ(q,ε):=q；δ(q,a∙w):=∪q'∈δ(q,a)δ(q',w)，式中：a∈Σ；ε为空字；w∈Σ*．对于集合S⊆Q，w∈Σ*可定义δ(S,w):=∪q∈Sδ(q,w)．如果NFA A=(Q,Σ,δ)分别满足以下3个条件：a. (D1-同步条件)∀q∈Q，δ(q,w)≠∅且|δ(q，w)|=|δ(Q,w)|=1；b. (D2-同步条件)∀q∈Q，δ(q,w)≠∅且δ(q，w)=δ(Q,w)，注意略微不同于文献[13]，这里定义的D2-同步字要求在每个状态上都有定义；c. (D3-同步条件)∩q∈Qδ(q,w)≠∅．那么字w为A的Di-同步字(i=1，2，3)．如果A具有相应的Di-同步字，那么称A为Di-可同步的(i=1，2，3)．可以看出NFA的初始状态和终止状态集与同步性质无关，故仅将NFA定义为三元组．本研究将重点关注NFA的D1-同步字．2 p-D1W问题FPT-归约到SAT2.1　D1W和p-D1W问题定义为方便讨论，设Σ为{0,1}，Q={q0,q1,⋯，qn-1}．实际上多字母的自动机可以转化为2-字母表(字母表大小为2)的自动机，新自动机的大小将增长某个多项式因子(因为大小为|Σ|的字母表采用二进制编码，所以每个字母的长度为log2|Σ|+1)．定义判定问题D1W及其参数化版本和最优版本的问题如下．问题1 D1W输入 2-字母表的NFAA询问 A是否是D1-可同步的？问题2 p-D1W输入 2-字母表的NFAA和正整数l询问 A是否具有一个长度为l的D1-同步字？问题3 shortest-p-D1W输入 2-字母表的NFAA和正整数l询问 如果A是D1-可同步的，那么它的最短D1-同步字的长度是否为l？类似地，可定义判定问题p-D2W，p-D3W，shortest-p-D2W和shortest-p-D3W及对应的搜索(计算)问题．2.2　将p-D1W问题编码为SAT本研究的编码参考了Shabana的D2W和D3W的编码方法[7-8]并做了修改．给定任意的p-D1W问题的实例(A,l)，其中A=(Q,Σ,δ)为NFA，以下将产生一个SAT的实例(V,C)，使得(A,l)的回答为“是”，当且仅当(V,C)的回答为“是”．首先定义布尔变量集V．V包括字母变量和符号变量．字母变量为x1,x2,⋯,xl，对每个xt，其中1≤t≤l，输入字w=a1a2⋯al，xt的值取1当且仅当符号at取字母1．符号变量为yijt，其中0≤i,j≤n-1和0≤t≤l．然后定义子句集C．C为三个不相交的集合的并，它们分别为初始子句的集合C0、变迁子句的集合Ct(1≤t≤l)和同步子句的集合S．C0,C1,⋯Ct中子句的构造与文献[7-8]中的构造相同，但S中的子句与之不同，须反映D1-可同步的本质．C0由单文字子句y000,y110,⋯,yn-1n-10和形如¬yij0的单文字子句组成，其中i≠j，i,j=0,1,⋯,n-1．接着定义Ct，其中t=1,2,⋯,l．对于每个Ct，由以下子句构成¬yijt∨¬xt∨∨qk∈I1(qj)yikt-1；¬yijt∨xt∨∨qh∈I0(qj)yiht-1，其中：对每个qk∈I1(qj)，有子句yijt∨¬xt∨yikt-1；对每个qh∈I0(qj)，有子句yijt∨xt∨yiht-1，这里h,i,j,k=0,1,⋯,n-1．最后讨论同步子句集S，包括以下形式子句¬yijl∨y((i+1)modn)jl，其中：i,j=0,1,⋯,n-1；mod为模(求余)运算．由于要求同步字w=a1a2⋯al在每个状态都有定义且|δ(Q,w)|=1，因此还须向S中加入子句∨0≤j≤n-1y0jl，并且对每个j,k=0,1,⋯,n-1,j≠k，须加入子句¬y0jl∨¬y0kl．以下分析转化的SAT的实例(V,C)的大小．集合V包含(n2+1)l+n2个布尔变量，集合C0包含n2个单文字的子句．对于集合Ct，容易得到对每个t=1,2,⋯,l，有|Ct|≤mn+2n2≤2n2(n+1)．集合S包含3n2/2-n/2+1个子句．于是C=S⋃∪t=0lCt的大小不超过2n2(n+1)l+5n2/2-n/2+1．注意，转化的实例(V,C)是属于(n+2)-SAT的．2.3　p-D1W问题的参数化复杂性引理1 NFA A=(Q,Σ,δ)具有长度为l的D1-同步字当且仅当2.2节中构造的SAT实例(V,C)是可满足的，其中构造过程所消耗的时间是关于NFA A的大小和l的多项式，而且字w=a1a2⋯al是A的D1-同步字当且仅当映射xt↦at可以扩展为(V,C)的一个可满足赋值，其中a1,a2,⋯,al∈{0，1}，t=1,2,⋯,l．引理1的证明可参考文献[8]，引理1澄清了D1-同步字和SAT公式的可满足赋值间的对应关系．定理1 问题p-D1W属于para-NP，问题shortest-p-D1W属于para-DP．定理1说明：如果参数在合理的范围内，那么p-D1W可以有效求解，首先将其转化为SAT公式，然后在调用SAT求解器即可．为了证明这个结论，须要证明到SAT或UNSAT的归约是FPT-归约．证明 在2.2节给出一种编码，它将实例(A,l)转化为一个SAT实例(V,C)，可用合取范式表示．容易看出转化过程所需的时间为O(n2l)．O(n2l)符合FPT-时间要求，因为在上界O(f(k)∙|I|c)形式中，取参数k=l，函数f(l)=l，实例大小|I|=n，常数c=2即可．根据FPT-归约的定义[11-12]，归约满足在FPT-时间内可计算的条件．引理1可以确保实例(A,l)和(V,C)对各自判定问题的回答一致，即对于“是”的回答二者等价．至于对归约后的问题实例大小的要求，可做以下分析：归约产生的SAT实例包含|V|=(n2+1)l+n2个布尔变量和|C|个子句，其中|C|≤2n2(n+1)l+5n2/2-n/2+1，不妨设l≥n，有|V|≤2l3和|C|≤3l4，于是转化的SAT实例大小是满足FPT-归约定义的，因为可令定义中的约束函数g(⋅)为关于l的四次函数，所以这个归约必是FPT-归约．由于SAT是NP-完全的，同时归约是FPT-归约，因此p-D1W问题属于para-NP．类似地，由于SAT⋂SAT¯是DP-完全的，因此可证shortest-p-D1W问题属于para-DP．对于D2-和D3-可同步，有推论1成立，只是转化的SAT公式大小比D1-可同步性转化出的公式要小，包含的变量数和子句数的具体分析见文献[7-8]．推论1 问题p-D2W和p-D3W属于para-NP，问题shortest-p-D2W和shortest-p-D3W属于para-DP．推论1的证明类似于定理1的证明．以下的定理2将说明算法可靠但不完备．定理2 对于问题p-D1W，存在算法将其转换为SAT进行求解，转化的SAT公式编码了带参数l的NFA实例A．这个算法是可靠但不完备的．这里只给出定理2的解释．引理1确保了可靠性．如果SAT求解器返回“不可满足”，那么这只能说明NFA A在不超过l的长度内没有合适的D1-同步字．此时有两种可能：a. A不是D1-可同步的；b. A是D1-可同步的，但D1-同步字可能非常长而算法中参数l设置过小．如果将参数l的长度设置为NFA的最短D1-同步字的最小上界[6](这个界限是n的指数函数)，那么得到的算法是完备的，但实际情况下时间和空间等计算资源有限，不宜将参数l设置过大．3 shortest-p-D1W搜索算法和实验3.1　基于SAT的二分搜索算法本研究给出基于SAT求解器的二分搜索算法BinSearch4ShD1W，这是一个判定版的算法，由引理1可知能够将其扩展到搜索版的算法．算法描述中的z用于保存结果，即最短D1-同步字长．g和h分别表示二分搜索过程中迭代的下界和上界．算法描述中有两处将p-D1W的实例编码到SAT．算法调用求解器Minisat的次数不超过log2l+1．同定理2，这个算法也是可靠但不完备的．算法 BinSearch4ShD1W输入 两个逆临接表a[n]，b[n]和整数l输出 最短同步字的长度或不可同步int g=1，h=l，m=（g+h）/2，z=h；输入a[n]，b[n]和l，产生SAT公式存于in.txt文件；调用Minisat，输入in.txt，输出out.txt文件；如果Minisat返回“不可满足”，那么返回“不可同步”；否则当条件gh满足时，执行以下循环：输入a[n]，b[n]和m，产生新的SAT公式；调用Minisat，输入in.txt，输出out.txt文件；如果Minisat返回“可满足”，那么h=m；z=m；如果Minisat返回“不可满足”，那么g=m+1；循环结束；返回z．3.2　实验实验的主机为双路Intel Xeon E5-2650v2 2.6 GHz处理器，配有32 GiB的DDR3内存．程序采用C++实现，编译器为GCC7.4.0，调用Minisat2.20求解器(Minisat的主页http://minisat.se/)．由于缺乏公开的标准测试集，因此实验采用文献[7-8，14]中的NFA例子和基于均匀分布模型随机生成的NFA．实验中Minisat运行时间大于2 h设为超时，即设置“-cpu-lim=7 200”，将超时情况看成不满足．在https://github.com/zhukaiscau/D1-Synchronizing可找到本研究的程序源码和数据．3.2.1　缓慢同步的NFA上的实验实验1 这个实验证实文献[14]报告的一类“缓慢同步的”自动机，同时验证了3.1节算法的正确性．实验检查了状态数分别为n=3,4,⋯,9的情况，结果见表1，表中：|w|为最短同步字长；“—”为超时．实验得到的最短同步字长与文献[14]一致．作为对比，文献[7]报告当n=11时其算法的时间消耗为4 303 s，这里的实验n=9就已超时无法计算(当不设置超时参数时，Minisat第一次返回就消耗了大约55.54 h的时间)．除限制CPU的计算时间外，这里所产生的SAT公式的大小要大于文献[7]所产生的对D2-可同步性检查的公式．10.13245/j.hust.210210.T001表1最短同步字长和算法消耗的时间n3456789|w|271526395573时间/s0.0070.0100.0241.3233.294 187.13—3.2.2　随机生成的NFA上的实验随机产生NFA的方法为：对于每个状态q∈Q和每个输入符号a∈{0,1}，首先随机选择数字k∈{0,1,⋯,n}，k值表示|δ(q,a)|，每个k被选中的概率为1/(n+1)；然后均匀地随机选择δ(q,a)，从Q的所有nk个子集中随机选择，当有hmax的限制时，上述k从{0,1,⋯,hmax}中等概率地选择．实验2 分别取n=10,20,30,40，设l=4n，对于每个不同的n产生的500个NFA，计算所消耗的时间从n=10时的214.12 s上升至n=40时的1.158 086 3×105 s(约32.17 h)．在生成的这些NFA中没有发现D1-可同步的NFA，表明随机产生的NFA是D1-可同步的概率非常小．实验3 取hmax=2，考虑该因素对不同大小的NFA的影响．实验中n的取值范围为{2,4,6,8，10,12,14,16,18,20,22,24,32,48}，设l=2n．为每个n采用均匀分布模型随机地产生1 000个NFA，如图1所示，图中y为D1-可同步的NFA数量．图1展示了随着n的增长，趋向呈逐渐下降的趋势，当n=18时D1-可同步的NFA的数量降至0(n=20时曲线出现的扰动可忽略)，这说明随着n增加，虽然随机的NFA的总体快速增加，但是仍抽样产生1 000个NFA，且出现D1-可同步的NFA的个数还是快速地下降，甚至下降至0．10.13245/j.hust.210210.F001图1对每种n产生1 000个NFA中可同步NFA数量实验4 对NFA的每个状态q∈Q和每个输入符号a∈{0,1}，将|δ(q,a)|值固定取为2，其他设置与实验2相同．对每个n随机产生1 000个NFA，再次运行算法，发现没有出现D1-可同步的NFA，说明随机产生这类D1-可同步的NFA概率非常小．实验3和4表明D1-同步条件是非常强的约束．实验5 将n的取值范围设置为{5,10,15}，设l=n2．对n=5，hmax的取值范围为{1,2,3,4，5}；对n=10，hmax的取值范围为{1,2,3,4,5,6,7，8,9,10}；对n=15，hmax的取值范围为{1,2,3，4,5,6,7,8,9,10,12,15}．对n和hmax的每种组合分别随机产生1 000个NFA，如图2所示．图2展示了每条曲线在hmax=2时达到峰值，然后随hmax的增加而快速下降．从三条曲线中可看出：随着n和hmax的不断增加，出现D1-可同步的NFA的概率下降非常快．10.13245/j.hust.210210.F002图2当hmax取不同值时D1-可同步的NFA数量当hmax=1时，NFA实际上退化为部分规约的确定的有限自动机．综合实验2～4可知：当hmax=1时，样本中的NFA是D1-可同步的数量较少；当hmax=2时，样本中D1-可同步的NFA数量相对多一些，达到峰值；当hmax取值越来越大时，是D1-可同步的可能性不断被稀释．三条曲线均反映了先上升后下降的趋势．由实验3可得出结论：当样本总数一定时，n值越大，样本中是D1-可同步NFA的数量越少，当n=5时在1 000个样本中D1-可同步的NFA数量会多于n=10和n=15时的，所以n=5时的曲线在最上方．综合考虑，n=5时的曲线会先上升后下降，比另外两条曲线要陡．虽然n=6，7，8的情况没有进行实验，但是不难得出三者的曲线会依次位于n=5，10的两条曲线之间，比n=10时陡但比n=5时平缓．分析参数l的取值对结果的影响．对于实验5，当n=5,l=25,hmax=2时，1 000个随机产生的NFA中有78个是D1-可同步的．最短的D1-同步字长分布的直方图如图3所示，图中w为最短D1-同步字长．图3中最短D1-同步字长主要位于区间[2,10]，于是当hmax取2时，绝大多数最短D1-同步字长不超过2n．10.13245/j.hust.210210.F003图3当n=5时最短D1-同步字长的分布实验6 n分别取5，10，15和20，设hmax=2和l=n2，对每个n随机产生1×104个NFA，实验6的结果如表2所示．最短同步字w的长度不超过2n的NFA占全部D1-可同步的NFA的比例，当n=10时出现最小值，约为96.6%，随着n的不断增加，这个比例趋近于100%．10.13245/j.hust.210210.T002表2D1-可同步的NFA和|w|≤2n的数量及计算时间nD1-可同步的NFA数量D1-同步字长满足|w|≤2n的NFA数量计算时间/s5784763336.316101461413 343.61115181857 229.6672011144 051.6954 分析与讨论文献[15]最早采用SAT结合二分搜索策略的算法框架求解了完全确定的自动机的最短同步字，本研究与之相比有以下不同：a. 由于判断完全确定的自动机是否可同步存在O(|Σ|n2)时间的算法[3]，因此文献[15]可先判断是否可同步，然后再常数次调用SAT求解器二分搜索；b. 由于完全确定的自动机的最短同步字上界为(n3-n)/6，因此文献[15]将参数设置为l=n3来产生SAT公式，力求得到完备算法；c. 由于完全确定的自动机的最短同步字判定问题是NP-难的，因此文献[15]中到SAT的归约是多项式归约，未引起复杂性类坍塌．至于NFA的同步字的研究，文献[7-8]研究了计算最短D2-和D3-同步字的问题，也归约到SAT然后调用求解器．本研究与之相比有如下特点．a. 利用参数化复杂性理论．在文献[11-12]的框架下建立了p-D1W到SAT的FPT-归约，证明p-D1W属于para-NP．文献[7-8]认为参数l采用一进制形式表示会存在到SAT的多项式归约，实际上如果存在p-D2W和p-D3W到SAT的多项式归约，那么PSPACE会坍塌到NP(即PSPACE=NP)．其实人们更相信NP⊆PSPACE，而且D1W属于PSPACE与参数化版本的p-D1W属于para-NP并不矛盾．推论1完善了文献[7-8]的不足．b. 指出一般情况下基于SAT和二分搜索求解最短D1-同步字的算法是不完备的．尽管如此，在平均情况下(或大多数情况下)，如果n不太大，那么选取合适的参数l可以有效且高效计算最短同步字．文献[7-8]其实也支持这个观点，但未明确指出．c. 针对D1-可同步性．由于一般情况下将某个字应用于NFA，结果状态将不止1个，因此D1-同步条件的过分严格导致了NFA是D1-可同步的概率非常小．当hmax=2时出现D1-可同步的NFA，当样本数固定时，随着n的不断增长其出现的概率几乎是0．如果把该现象与难解问题中常见的相变联系起来，那么hmax=2可看成是导致随机产生的NFA的D1-可同步性发生相变的控制条件．而文献[7-8]给出对绝大多数D3-可同步的NFA，其最短同步字的长度为2，对D2-可同步的NFA，有60%的概率其最短同步字长为3，这些均不依赖于n的取值．5 结语本研究分析了NFA的最短D1-同步字的计算问题，证明了参数化问题p-D1W到SAT存在FPT-归约和p-D1W属于para-NP，提出了基于SAT和二分搜索的最短同步字算法．研究表明：随机产生的NFA一般很少有D1-可同步的，当hmax=2时出现少量D1-可同步的NFA，此时绝大多数最短同步字长不超过2n．