没有合适的资源?快使用搜索试试~ 我知道了~
2381111《理论计算机科学电子札记》65卷第6期(2002)网址:http://www.elsevier.nl/locate/entcs/volume65.html16页时间自动机类与普适性Arnaldo V.P.1,2和 Guilherme A.Pinto平托3,4计算研究所,坎皮纳斯大学,C. P. 6176,13083-970,坎皮纳斯,SP,巴西摘要确定性时间自动机的普适性是PSPACE完备的,但当允许无限制的非确定性时,它的普适性是高度不可判定的。更准确地说,非确定性TA的普适性是困难的,它是2001年完成的。值得注意的是,整个算术层次都包含在决定论和非决定论之间的可计算性差距中。在本文中,我们考虑三种类型的句法限制不确定TA,这可能有助于更好地理解TA的普遍性问题。对于前两种类型,这是独立的利益,普遍性问题被证明是101-完全的。 对于第三个,普遍性是100-完全的,1 1这就等于说互补问题在递归可重复类中是完全的。 我们还证明了所有的限制定义了由非确定性TA定义的时间语言类的真子类;并建立了类之间的关系。1介绍在文献[1]中,确定性时间自动机和非确定性时间自动机的普适性问题分别被证明是PSPACE-完全的和PSPACE1-困难的。作者还报告说[1,p.217],后一个问题拒绝被证明是101-完成的。在本文中,我们考虑限制从而产生非确定性TA类,其普遍性问题位于层次结构中的较低位置,同时仍然保持不可判定性。除了[1],我们不知道以前关于TA普适性不可判定性程度的工作。在文献[2,3,10]中研究了TA的推广和混合系统的可达性问题的不确定性程度1电子邮件:arnaldo@ic.unicamp.br2 由FAPESP基金资助,98/05999-43电子邮件:guialbu@ic.unicamp.br4份由F和CPqD/FUNTTEL-MCT合并的补充品·c 2002PublishedbyElsevierScienceB. V. 操作访问根据C CB Y-NC-N D许可证进行。莫拉和平托23921∃11112∀ ∃12非确定性TA的普适性A具有1定义,与形式 ρ r[(A,ρ,r)],其中函数变量ρ和r被解释,分别作为时间词和A在时间词上的运行,正如在普遍性问题的自然定义中一样。谓词(A,ρ,r)断言算术(即,(注:只有在数变量上才有量化器),在这种方法中,普遍性是否是完全的问题可以被看作是我们是否可以得到摆脱量化器 r,并断言算术在ρ“上运行A的r我们考虑无穷自动机的一般性质,对于它们,所需的算术断言更自然地遵循其中三个列在下面。给定TAA和计时词ρ:(i) 如果A在ρ上的游程r是可接受的,那么它只产生有限个不确定的转移;(ii) 如果q是A在ρ上的某个接受游程r中无限频繁出现的最终位置,则A在ρ上的任何以q结尾的有限游程都是A在ρ上的某个(接受)游程的前缀,q无限频繁地重复;(iii) 如果A在ρ上有游程r,则r是可接受的。这些属性可以通过语法限制来强制执行,并且仍然不会导致普适性的可判定性在第3节和第4节中,我们分别定义了几乎确定性TA和步调标记TA,它们对应于(i)(二)分别。 我们表明,这些类型的TA的普遍性是101-完全的。在第5节中,我们考虑性质(iii)和定义TA。这一性质实际上导致了最终TA的一个100定义和普适性被证明是100-完全的。最后一个结果特别表明,非确定性TA的普遍性的高度不可判定性并不完全是由于自动机的在第6节中,我们建立了由确定性、最终、几乎确定性和节奏标记TA定义的时间语言类之间的关系。 我们为这些类的每个可能的交集提出了一个时间语言,并证明了所有三个类都是由非确定性TA定义的时间语言类的适当子类。从表达性的角度来看因此,它将以某种方式令人惊讶的是,如果非确定性TA的普适性也是完全的。另一方面,如果这个问题被证明是完全的,那就更令人惊讶了,因为这是非确定性ω-图灵机[4]和递归无限状态ω-自动机[15]的普遍性问题的不可判定性程度,它们在直觉上也更具表达性。 这个问题也可能不是在2001年,而不是完整的为1001。莫拉和平托240∈···中文(简体)···∈T BA≤|≥ |¬ |∧∈2预赛为了完整起见,我们回顾TA的定义以及算术和分析层次。一个赋时字ρ,在一个有限的符号集上,是一对(σ,τ),其中σ=σ1σ2···是一个符号序列,τ=τ1τ2是一个严格递增的时间值序列τiR>0,其中对于所有i,有j>i使得τj> i。设t表示n上所有时间词的集合。给定一个有限的时钟变量集合X,X上的时钟约束δ归纳定义为δ:=x c x cδ1δ2,其中xX和c是正有理数常数。X上的所有时钟约束的集合由Φ(X)表示。X的时钟解释ν是从X到R≥0的函数。 对于tR,我们写ν + t作为时钟解释,它将每个时钟x映射到ν(x)+t。当每个时钟x在δ中被ν(x)替换时,如果δ的值为真,则X的时钟解释ν满足X上的时钟约束δ。时间布奇自动机(TBA)是一个元组A=A,Q,Q0,X,T, F,其中:A是符号的有限字母表; Q是位置的有限集合;Q0Q是开始位置的集合;FQ是接受位置的集合; X是时钟的有限集合; TQ ×Q× Q×Φ(X)×2 X是转换的集合。A的状态序列r是一对(q,ν),其中q = q0q1q2···是Q中的位置序列,ν= ν0ν1ν2是X的时钟解释序列。A的一个状态序列r =(q,ν)是A在一个时间字ρ =(σ,τ)上的一个游程,如果:q0∈ Q0,且ν0(x)= 0,对所有x ∈ X;且对所有i ≥ 1,存在一个变迁e=<$qi−1,qi,σi,δ,λi∈T,使得(νi−1+τi−τi−1)是一个定义sδ,且如果x ∈ λ,则dνi(x)=0,否则νi(x)=νi−1(x)+ τi−τi−1(根据定义,τ0= 0)。给定在一个时间词ρ上的游程r=(q,ν),设inf(r)是在r中无限频繁出现的位置的集合。如果inf(r)F=,则运行r是可接受的。被A接受的语言L(A)是所有时间词ρ的集合,使得A有一个接受超越ρ。 最后,用一些TBA接受的所有语言的类表示给定一个TBA A= A,Q,Q0,X,T,Fn,如果给定一个nyt两个不同的转移<$q,q1J,a,δ1,λ1 <$j和<$q,q2J,a,δ2,λ2 <$inT,δ1<$δ2是不满足的,则位置q ∈ Q是确定的。TBA A是确定性的(DTBA),如果|Q0| =1,并且Q中的所有位置都是确定性的。A TBA A= λ 1,Q,Q0,X,T,Fλ 1称为完备的,如果给定任意q∈Q,a∈ λ 1和时钟解释ν,存在一个变迁λ1,q1J,a,δ1,λ 1 λ1∈T使得ν满足δ1。2.1分段和连接我们给自然的定义段和连接的时间的话,这将需要在证明。给定一个时间词ρ,它的前缀长度为i,i≥1,记为ρi。给定ρ=(σ,τ),ρ[i]表示时间字,其是ρ从第i个位置开始的子集,其中时间值被调整。形式上,ρ[i]=(σJ,τJ),其中莫拉和平托2411⟨ ⟩ ⟨ ⟩ ∈11112| ∀∃ ∀}B B11112σlJ =σl+i−1,τlJ=τl+i−1−τi−1,ρ≥1。 给定ρ=(σ,τ)且j,k >0,ρ[j,k]表示有限时间字,它是ρ从位置j到位置k,包括在内。形式上,ρ[j,k]= ρJk−j+1,其中ρJ= ρ[j)。如果kj,则ρ[j,k]是空的定时字。给定一个长度为i的有限时间词ρ和一个时间词ρJ,ρJJ=ρ·ρJ表示它们的连接,即ρJiJ= ρ和ρJ[Ji+1)= ρJ。类似的定义适用于有限状态序列、段和连接。状态序列的连接。2.2算术和分析的层次结构我们只记得几个定义。对不可判定性层次的全面介绍可以在[13]中找到一个关系H<$N2是递归的,如果存在一个图灵机,对于任何给定的x1,x2作为输入,它停止并接受i <$x1,x2H。 算术层次的第一个存在层次与递归可递归集一致,即S∈N0i,存在递归关系H使得S ={x∈N| <$nH(n,x)},其中H(n,x)表示<$n,x <$∈H.第一个普遍水平是,那么,其中S∈N0 i <$S∈N0。等价地,集合S属于存在递归关系H使得S ={x ∈ N |{n(n,x)}.设F表示从N到N的函数的集合。一个关系H <$F j×N2是递归的,如果存在一个带有j个预言机的图灵机,对于给定的任何nx1,x2n,它停止并接受,使用预言机f1,f2,..., fj,i ∈f1,f2,., fj,x1,x2∈H。分析层次结构的第一个层次是:其中S∈S1 i存在递归关系H使得S ={x ∈ N |{f,n,x},其中f是一个函数变量,n是一个数字变量;1={S<$N|S ∈存在一个递归关系H使得S={x∈{1}};且S∈ {1}i∈{Nfg nH(f,g,n,x),其中f和g是函数变量,n是a数字变量给定两个集合A,B<$N,A可以约化为B,记为A≤mB,如果存在递归f:N→N,使得x∈Ai <$f(x)∈B。 设C ∈2N. 一个集合S<$N是C-硬的,如果对所有R∈ C,R≤mS;S是C-完备的,如果S是C-硬的且S∈ C。2.3T BA的普遍性我们现在证明TA的普适性有一个定义。设0,1,. 对所有传统BA进行有效索引。普适性问题被定义为所有索引z的集合UTBA,使得对于所有定时词ρ,存在Bz在ρ上的可接受游程r。 首先,我们注意到,它表面上只考虑理性计时词。 设rt={(σ,τ)∈t|τi是有理数}。下面的引理意味着UTBA是所有指数z的集合,使得对于所有有理定时词ρ,存在Bz在ρ上的可接受游程r。莫拉和平托242∈→→2B∈22引理2.1设A是TBA。给定(σ,τ)∈ λ t,存在(σJ,τJ)∈ λ rt使得(σ,τ)∈L(A)i <$(σJ,τJ)∈L(A).证据所要的时间词(σJ,τJ)可以归纳地定义,如[1]中定理3.17的证明,也见[12]。✷现在我们可以将函数映射到计时单词和运行。 设a ={a0,a1,.,ak−1}。 我们可以把σ1=af (0)(modk),σ2=af (3)(modk),等等;τ1=(f(1)+1)/(f(2)+1),τ2=(f(4)+1)/(f(5)+1),等等.因此,我们可以取两个函数d1:Fω和d2:F Qω,使得d1(f)= σ和d2(f)= τ,定义如上。很明显,对任意ρ =(σ,τ),我们有一个fF使得d1(f)= σ和d2(f)= τ.对于给定的TBA,令d3和d4是位置序列和时钟解释序列的类似函数。定理2.2UTBA∈ φ1。证据考虑一台带有一个预言机的图灵机MH1MH1接受一个给定的对<$i,j<$$> ∈N2i <$τj> i , 其 中τj 是 根据 d2 通 过咨 询 预言 机 获得 的 。 设H1<$F×N2是关系,使得<$f,i,j<$∈H1i <$MH1,对于预言机f,接受对<$i,j<$.考虑另一台图灵机3MH2有两个预言机f和g,给定元组i,j,z∈N,执行以下顺序:(i) 如果j≤i,则拒绝;(ii) 查询甲骨文f,根据d1和d2,得到有限时间字ρ=(σ,τ)j;(iii) 查询神谕g,根据d3和d4,得到有限状态序列r=(q,v)j;(iv) 结构Bz= Z,Q,Q0,X,T,F;(v) 如果r是z在ρ上的有限游程,且qjF,则接受;否则拒绝。取H2<$F2×N3为关系式,使得H2(f,g,i,j,z)i <$MH接受元 组 i , j , i , j 我 们 有 UTBA={z| <$f<$g[ ( <$i<$jH1 ( f , i , j ) )<$(<$i<$jH2(f,g,i,j,z))]}.根据规范形定理[13],UTBA ∈ φ1.✷3几乎确定性TBA几乎确定性被认为是以前的布吕克希ω-自动机[6,14]作为一种手段,实现更好的复杂性界的概率验证问题。从表达性的角度来看,几乎确定性和非确定性的Bu¨chiω-自动机定义了同一类语言。TBA的情况更有趣在第6节中,我们证明了由几乎确定性TBA定义的时间语言类正确地位于莫拉和平托2431T BA DT BA∈∈ ≤ ⟨⟩11A A11和. 在这一节中,我们证明几乎决定论导致普遍性的完全性给定TBA A= N,Q,Q0,X,T,F和集合SQ,令Reach(S)Q是存在序列s1,s2,.的位置集合s,sk,k≥1,使得s1S,sk= s,对于每1i< k有si,si+1,a,δ,λ于T. TBAA是几乎确定性TBA(ADTBA),如果所有位置在到达(F)是确定性的。设A为ADTBA。给定一个函数f的预言,f编码一个有理时间词ρ,如果存在A在ρ上的可接受游程r=(q,ν),那么,如果我们给定r的一个有限前缀,(q,ν)i,使得qiF,那么,由于Reach(F)是确定性的,r的余数由ρ唯一确定,并且可以通过咨询预言来构造由于我们可以将有限状态序列编码为自然数,因此我们可以获得普适性问题的一个定义。对于ADTBA,UADTBA。定理3.1UADTBA∈ φ1。证据 设0, 1,. 是所有ADTBA的有效索引。设d5是一个将数映射到有限状态序列的函数。考虑一个图灵4具有一个预言机的机器MH3,给定一个元组p,i,j,z<$∈N,其行为为如下所示:(i) 如果j≤i,则拒绝;(ii) 根据d5对p进行解码,得到r=(q,v)k;(iii) 构造Az= Z,Q,Q0,X,T,F;(iv) 查询甲骨文,根据d1和d2,得到有限时间字ρ=(σ,τ)k;(v) 若r不是Az在ρ上的游程,或qk/∈F,则拒绝;(vi) 再求一次神谕,根据d1和d2,得到有限时间dw或dρJ=(σJ,τ J)k+j。观察到ρ是ρJ的前缀;(vii) 构造在e r ρ j上的A z的唯一游程rJ=(qJ,νJ)k+j,其中vingr是一个前缀(假设,w.l.o.g.,z是完备的);(viii) IfqkJ+j/∈F,则拒绝,否则接受。然后,UADTBA ={z |<$f [(<$i <$j H1(f,i,j))<$(<$p <$i<$j H3(f,p,i,j,z))]}.✷在[7]中,证明了决定一个非确定性图灵机是否在无限次访问其起始状态的空磁带上具有无限次计算的问题是101-完全的。 文[1]将这个问题的补约化为UTBA,证明了UTBA是1-困难的. 硬度为0.01的 1 1UADTBA是这个结果的必然结果,因为所有的时间语言都需要实际上,减少可以被ADTBA接受在第5节中,我们将修改这种归约,以表明最终TBA的普适性是困难的。为了比较,我们回顾[1]的简化一个不确定的2-计数器机器M由一个k的序列组成,莫拉和平托244∈-∈结构和两个计数器C和D。有6种类型的指令:(a)递增C并非确定性地跳转到指令x或y;(b)递减C并非确定性地跳转到指令x或y;(c)如果C= 0跳转到指令x,否则跳转到指令y;(d),(e)和(f)与上述相同,交换D和C。M的配置是元组(i,c,d),其中c和d是当前计数器值,i是要执行的指令M的计算是从(1,0,0)开始的相关配置的序列。计算是循环的,如果指令1以-10的无限次执行在字母表{b1,b2,..上定义时间语言L,bk,a1,a2}这样(σ,τ)∈Li <$:(i) σ= biac1ad1biac2ad2... ,其中(i1,c1,d1)(i2,c2,d2). 是一个反复出现11 221 2计算M;(ii) 对于所有j≥1:(a) bij发生在时间j;(b) 如果cj+1=cj,则对于时间t(j,j +1)处的所有a1,在j+1)处存在a1。t+ 1;(c) 如果cj+1=cj+ 1,则对于所有a1在时间t∈(j+ 1,j + 2),存在一个在时间t-1时a为1,除了最后一个;(d) 如果cj+1=cj 1,则对于在时间t(j,j+ 1)的所有a 1,在时间t+ 1存在a1,除了最后一个;(e) 与(b)、(c)和(d)中相同的条件,交换a2和a1,以及交换d和c。互补语言L可以被定义为几个简单时间语言的有限析取所有这些ADTBA的不交并是普适的,并且没有递归计算[12]。这些语言的一个例子如下。假设指令6是类型(d)。那么,L必须包含语言G1={(σ,τ)|i<k,存在j > i使得γ[1,j]·ρ[j+1)∈L(A).5最终TBA注意,给定一个TBAA = A,Q,Q0,X,T,F,如果某个语法限制暗示了引言的性质(iii),即任何游程都是可接受的,那么很明显,TBAB = A,Q,Q0,X,T,Q有L(B)=L(A)。也就是说,A中的接受条件实际上对于区分游程是无用的我们说,一个TBAA = A,Q,Q0,X,T,F是一个最终的TBA(FTBA),如果F=Q。让我们注意到,本文中考虑的所有三个句法限制都不是“时间”性质的特别地,最终TBA正是[9,8]中研究的时间安全自动机,它们是没有接受条件的TA虽然在[9,8]中,人们的兴趣是时间安全自动机的表达能力,但在这里,我们关注的是普适性问题,在本节中,我们证明了FTBA的普适性是100-完全的。一方面,这表明时间安全自动机的普适性仍然是不可判定的;另一方面,非确定性TBA的普适性的高度不可判定性并不来自于莫拉和平托24711A A11∈11“timed” part of the automata with unrestricted nondeterminism, but to acombination of them with acceptance显示2000年UFTBA的遏制我们只需要注意到,给定一个FTBAA,如果时间字ρ/∈L(A),则存在i使得没有游程A在ρ[1,i]上。这是因为A在ρ上的游程采用有限个有限分支树的形式。因此,如果对于所有i,存在A在ρ[1,i]上的游程,那么一定存在A在ρ上的无限游程,这一定是可接受的,因为A是FTBA。定理5.1UFTBA∈φ0。证据设0,1,. 成为所有FTBA的有效索引。设d6是一个将数字映射到有限时间单词的函数。考虑一台图灵机MH5 其中,给定元组i,z∈N2,表现如下:(i) 根据d6对i进行解码,得到ρ=(σ,τ)k;(ii) 构造Az=Z,Q,Q0,X,T,Q0;(iii) 在ρ上模拟Az。如果Az在ρ上运行,则接受;否则,拒绝。则UFTBA ={z| {i H5(i,z)}.✷非正式地说,我们可以说UTBA、UADTBA和UPMTBA的101-硬度是由于这些自动机可以识别任何不代表2计数器机器的无限计算的当然,FTBA不能做到这一点,因为UFTBA是0。然而,FTBA可以识别任何不代表2计数器机器的停止计算的定时字定理5.2UFTBA是100-困难的。证据对任意C∈ H ∈0,存在一个递归HC使得C ={x∈N| nHC(n,x)}。给定x∈N,我们构造一个FTBA Ax,使得Ax是泛函数i <$x/∈ C。设Mx是一个图灵机(不一定是非确定的),它在空磁带上停止,i<$x∈C。这台机器只需要模拟MHCoverni,xn i的增加值,如果MHC接受某个i,则停止。机器Mx可以用第3节中描述的2计数器图灵机来模拟,增加了一种类型的指令:(g)halt。这台机器的停止计算是一系列相关的配置,以指令停止的配置结束。假设w.l.o.g.只有k个指令的序列的最后一个指令可以是类型(g)。在字母表{b1,b2,..上定义时间语言L,bk,a1,a2},使得(σ,τ)∈Li:(i) σ = biac1ad1biac2ad2... biacnadn. ,以及(i1,c1,d1)(i2,c2,d2).(in,cn,11 2212n1 2dn)是Mx的停止计算(因此,in=k);(ii) 对于所有j≤n,如第3节中的条件(a)至(d)成立。莫拉和平托248ADT BA PMT BA FT BAPMT BA PRAFT BA\ ADTBA{}} ∈∈T BA(TBA)1121FT BA(完成)01ADT BA(完成)11DT BA(PSPACE-完整)PMT BA(完成)11可以证明,语言L可以被定义为有限析取这些语言都可以被FTBA接受。作为一个例子,在第3节中,语言G1的类似物是G2={(σ,τ)|i< i,qj= q}.我们将证明,对于下面的ADTBA A= A,Q,Q01,X1,T,F1,我们有L(A)= L。其中Q =Q1<${qf}(不交并); F ={qf};且T={<$q,qJ,a,δ,λ<$|[<$q,QJ,a,δ,λ<$∈T1]<$[QJ=qf<$λ=X1<$δ=真<$q∈Gqf].通过构造A,我们可以看到,如果ρ L(A1),则ρ L(A). 我们转向另一个方向。请注意,A的任何接受游程必须至少通过G中的一个位置一次。因此,如果ρ∈L(A),我们可以找到A在ρ上的游程r=(q,ν),使得存在一个m,其中qm∈G。但请注意,r[0,m]是A1在ρ[1,m]上的有限游程。莫拉和平托249√由于qm∈G,存在ρJ∈L(A1),且存在A1在上的游程RJ=(QJ,νjρJ,使得i<$j,j> i,qjJ=qm。 设mJ是最小的自然数,qmJJ=qm。NowletρJ,J=ρ[1,m]·ρJ[m, J).SinceA1具有游程rJJ=r[0,m]·r[JmJ)在ρJJ上,有ρJJ∈L(A1).我们现在称ρ∈L(A1). 为了避免矛盾,假设ρ/∈L(A1)。由于L(A1)= L(A2),且A2是一个FTBA,根据引理5.3,存在k,使得对于所有γ∈λt,ρ[1,k]·γ/∈L(A1).如果k≤m,则我们已经有了一个临界点,因为ρJ=ρ[1,k]·ρ[k+1,m]·ρJ[mJ).如果k > m,则由于ρ[1,m]=ρJ[j1,m],根据引理4.2,存在ρ > k,使得ρJJJ=ρ[1,l]·ρJ[jl+1)∈L(A1).由于ρJJ=ρ[1,k]·ρ[k+1,l]·ρJ[Jl+1),故又是一个悖论。✷6.1语言目录下面的列表给出了图2中类的每个非空交集的定时语言下面的表1用““标记准确地指出了对于每一种语言,证明它不包含在某个类中,当在表中指出时,可以通过下面给出的定理6.2,6.3和6.4的证明思想对于每一种语言,当在表中指出时,人们可以毫不费力地找到某个类别的TA。图3给出了四个例子,其中L(Ai)=Li,Li如列表中所示。• L1=t(通用语言);• L2={(aω,τ)|{i∈j,j> i,τj= τi+1}•L3={(aω,τ)|{k<$i<$j,j> i> k,τj= τi+1};•L4={(σ∈(b+a)ω,τ)|<$i[(τi∈N惠σi=a)<$(<$j,τj=i)<$(<$j<$k,2i<τj<2 i + 1,τk= τj+ 1)]};•L5={(aω,τ)|{i,i= i};•L6={(σ ∈(a + b)ω,τ)|<$i<$j,j> i <$σj= b};•L7={(σ∈(b+a)ω,τ)|<$i[(τi∈N惠σi=a)<$(<$j,τj=i)<$(<$j<$k,k>j > i,τk= τj+ 1,σj= σk= b)]};• L8={(σ,τ)|{i,j> i,σj= a};•L9={(aω,τ)|i [τi+1− τi≥ 1•L10={(aω,τ)|{i∈j,τj= τi+1,τj<2};•L11={(aω,τ)|[ij,τj= τi+ 1,τj<2]<$[i((τi= 2)<$(j,j≥i <$τj+1=(1)};定理6.2 L3/∈ ADT BA.证据我们从矛盾出发。假设B= A,Q,Q0,X,T,F是 ADTBA,L(B)=L3.我们首先选择一个特殊的时间词ρ2∈L3,取B在ρ2上的任意可接受游程r2=(q2,ν2),然后根据r2对ρ2进行遍历,得到ρ3,并证明B在ρ 2上有游程r3=(q3,ν3莫拉和平托250∈我∈c=mε。L1L2L3L4L5L6L7L8L9L10L11FTBA√√√√√PMTBA√√√√√DTBA√√√√ADTBA√√√√√√√√表1时间语言目录一个3x>1,{x}x=1,{x}A9{x}x=1,{x}x>1,{x}A11一个7X1X2x=2,{x}图三. 时间自动机ρ3,使得q3=q2。当我们注意到,ρ3/∈L3.假设n =|达到(F)|和k = |X|.设CB是自然常数,使得CB>1且CB> c,对于所有cConst(T),其中Const(T)是出现在T中的某个时钟约束中的所有常数的集合。设ε1是一个有理常数,使得对于所有c∈ {Const(T)<${1}},存在某个自然的m,其中为了构造ρ2,我们定义了两个有限时间词。 设p0由(nk + 1)个a的序列组成,a在CB和CB + ε之间均匀分布,即p0 =(ank +1,τ 0)nk +1,其中τ 0 = CB + μi,μ = ε/(nk + 2). 图的上部 4表示p0。 给定位置ρReach(F)和时钟解释ν,由于Reach(F)是确定性的,因此在p 0上至多存在B的一个有限游程(q,ν)nk+1,使得q0=ρ且ν0= ν;并且,由于存在k个时钟,因此在该游程中至少((n-1)k +1)个跃迁使得没有x1,{y}x2y = 1a,x=1,{x}a,x=1,{x}b,x1,{y}b,x1y = 1b,x<1b,x<1a,x=1,{x}b,x1<{x}{x}x= 1{x}莫拉和平托251≤ ≤∈J我我J0F∈≥∈B我B我K我我我我我我我我时钟被重置为最后一次。此外,由于当第一个a出现时,任何时钟的值都大于CB,所以当ρ固定时,任何ν都将采取完全相同的跃迁序列因此,有一个固定的索引j,1 J(nk + 1),使得对于所有ρ 到达(F),对于所有ν,没有时钟最后一次在p0上运行的第j次转换时重置,从ρ和ν开始。p1均p00CBCB+εCB+1τ0+ 1CB+1 +ε时间ρ2:p1p1p1图四、构建计时词ρ2现在,设p1=(ank+2,τ1)nk+2,其中τ1=τ0对于1≤i≤(nk+ 1),并且1nk+2 = τ0+ 1。 那么,ρ2=(aω,τ2)是p1的无限级联,如图4所示形式上,对于任何i>0,设id和im(nk+2)为<自然数,使得i=id(nk+ 2)+im。 因此,τ2=idτ1+τ1。德费恩ink+2imτ1= 0。 显然,ρ2∈L3。 设r2=(q2,ν2)是B在ρ 2上的可接受游程.必须存在至少一个这样的运行,因为我们假设L()=L3。设f是满足fm=0和q2Reach(F)的最小自然数. 注意,r2从第f次跃迁开始是确定性的。此外,对于每个自然i,如果if和im= 0,则对于每个时钟x,x在r 2的第(i + j)次跃迁中不被复位,或者x在r 2的第(i + jJ)次跃迁中被复位,对于某个jJ,j f且im= 0。我们现在通过扰动ρ2得到ρ3。设ρ3=(aω,τ3)定义为τ3=τ2−µ/2,如果i> f且im= 0,否则τ3= τ2。因此,ρ3/∈L3。我们假设不失一般性,B是完整的。 设r3=(q3,ν3)是B在ρ3上的游程,使得q3=q2,ν3= ν2,对每一个i,0 ≤ i ≤ f。请注意,只有一次这样的运行,因为ρ3等于ρ2直到第f个符号,是完全的,r3从第f个跃迁开始必须是确定的,我们声称r3和r2遵循完全相同的跃迁序列,这意味着q3=q2[12]。✷定理6.3L9/∈ PMT BA.证据 我们从矛盾出发。假设B=Q,Q,Q0,X,T,F是一个PMTBA,并且L(B)=L9.考虑定时字ρ2=(αω,τ2),其中τ1,τ2= i。显然,ρ2∈ L9。 设r2=(q2,ν2)是B在ρ2,设k是任意自然数,使得q2=q,q∈F,且q重复通常在R2中。τ莫拉和平托252我现在,设ρ3=(aω,τ3),其中τ3=τ2+ 1/ 2,如果i=q+ 1;且τ3=τ2,3i i−13 i i否则,请执行以下操作。 则ρ/∈L9,但根据引理4.2,ρ ∈ L(B).✷定理6.4 L9/∈ FT BA.证据再次是矛盾。假设B= F,Q,Q0,X,T,F是一个FTBA,L(B)=L9.考虑定时字ρ2=(aω,τ2),其中τ2= 2 i. 因此,ρ2/∈ L9。将引理5.3应用于B和ρ2,则存在k,使得对于所有γ∈k,2[1,k] ·γ/∈ L(B)。但取任意ρ∈L9。通过构造ρ2,我们有·ρ∈L9。✷引用[1] 巴尔河和D.Dill,时间自动机理论,理论计算机科学126(1994),pp. 183-235[2] Asarin,E.和O.马勒、阿喀琉斯和爬上算术等级的乌龟,J。 的Comp. 和Sys.Sci. 57(1998),pp.389-398.[3] Bournez , O. , Achilles and the tortoise climbing up the hyper-arithmeticalhierarchy,Theoretical Computer Science210(1999),pp.21比71[4] Castro , J. 和 F. Cucker , Nondeterministic ω-computations and theanalyticalhierarchy , Zeitschr.F. 数 学 Logik und Grundlagen d. 数 学 35(1989),pp.333- 342.[5] Choueka,Y.,ω-tape上的自动机理论:一种简化的方法,计算机与系统科学杂志8(1974),pp。117-141[6] 库尔库贝蒂斯角和M. Yannakakis,概率验证的复杂性,ACM杂志42(1995),pp. 857-907[7] 哈 雷 尔 , D. , A. Pnueli 和 J.Stavi , 非 正 则 程 序 的 命 题 动 态 逻 辑 ,J.Comput。系统科学26(1983),pp. 222-243[8] Henzinger,T.,P. Kopke和H.Wong-Toi,时钟的表现力,在:ICALP 1995,1995,pp.417[9] Henzinger , T. , X. Nicollin , J. Sifakis 和 S. Yovin
下载后可阅读完整内容,剩余1页未读,立即下载
![.pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![.pdf](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- VMP技术解析:Handle块优化与壳模板初始化
- C++ Primer 第四版更新:现代编程风格与标准库
- 计算机系统基础实验:缓冲区溢出攻击(Lab3)
- 中国结算网上业务平台:证券登记操作详解与常见问题
- FPGA驱动的五子棋博弈系统:加速与创新娱乐体验
- 多旋翼飞行器定点位置控制器设计实验
- 基于流量预测与潮汐效应的动态载频优化策略
- SQL练习:查询分析与高级操作
- 海底数据中心散热优化:从MATLAB到动态模拟
- 移动应用作业:MyDiaryBook - Google Material Design 日记APP
- Linux提权技术详解:从内核漏洞到Sudo配置错误
- 93分钟快速入门 LaTeX:从入门到实践
- 5G测试新挑战与罗德与施瓦茨解决方案
- EAS系统性能优化与故障诊断指南
- Java并发编程:JUC核心概念解析与应用
- 数据结构实验报告:基于不同存储结构的线性表和树实现
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)