没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记149(2006)17-36www.elsevier.com/locate/entcs弱双相似Mojm'rKret'ınsky'1VojtechReh'ak2JanStrejcek3信息学院,马萨里克大学Botanick'a68a,60200布尔诺,捷克共和国{kretinsky,rehak,strejcek}@fi. 我很团结。cz摘要弱双相似性是研究最多的行为等价之一。这种等价性对于下推过程(PDA)、过程代数(PA)和多集自动机(MSA,也称为并行下推过程,PPDA)是不可判定的。它的可判定性是基本进程代数(BPA)和基本并行进程(BPP)的一个公开问题。我们移动这些类的不可判定性边界表明,等价性仍然是不可判定的弱扩展版本的BPA和BPP。事实上,我们证明了弱互模拟等价问题是不可判定的,即使是BPA和BPP的赋范子类扩展有限约束系统。保留字: 弱互模拟,有限状态系统,可判定性1介绍等价性检验是并发系统验证的主要内容之一它旨在证明两个系统之间的语义等价性,其中一个通常被认为是表示规范,另一个是其实现或细化。语义等价被设计为对应于所需抽象级别的系统行为;最突出的是强和弱互模拟。1由捷克共和国赠款机构支助,赠款编号:201/03/1161。2.由“Institut e forThe oretical Computer Science(ITI)“研究所提供支持,项目编号:1M0021620808。3捷克共和国科学院资助,批准号:1ET408050503。1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.11.01418M. Kr Zeretínsket al./理论计算机科学电子笔记149(2006)17当前的软件系统通常表现出一个不断发展的结构和/或操作无限的数据类型。因此,对这类系统的自动验证通常需要将它们建模为有限状态系统。各种规格化形式主义已经开发出各自的优点和局限性。Petri网(PN)、下推进程(PDA)和进程代数(如BPA、BPP或PA)都是用来描述这一点的。在这里,我们使用类由术语重写系统定义的无限状态系统,并称为Mayr[12]引入的过程重写系统(PRS)PRS涵盖了在形式验证背景下研究的各种形式主义(例如,上面提到的所有模型)。PRS的各种子类对于建模和分析程序的相关性如[5]所示;对于自动验证,我们参考调查[2,22]。各种进程类的相对表达能力已经被研究过,特别是关于强互模拟;参见[3,16]和[12],显示了PRS类层次结构的严格性。将有限状态控制单元添加到PRS重写机制导致所谓的状态扩展PRS(sePRS)类,例如参见[8]。我们通过几个PRS类扩展了PRS层次结构,并通过引入两种类型的受限状态扩展来细化这个扩展层次结构:具有弱有限状态控制单元的PRS(wPRS,受弱自动机[17]的启发)[11,10]和具有有限约束系统的(fcPRS)[24]。对过程类的表达能力的研究一直伴随着探索各种验证问题的算法边界本文以弱双相似性为行为等价性的概念,重点研究等价性检验问题现有技术:关于顺序系统,即对于那些没有平行合成的情况,即使对于赋范情况,弱双相似性问题对于PDA也是不可判定的[19]。然而,证明了[13]弱双相似性对于基本进程代数(BPA)是可判定的;最著名的下界是EXPTIME-硬度[13]。考虑到并行系统,即使是强双相似性对于多集自动机(MSA,也称为并行下推过程或状态扩展BPP)[16]使用[6]中引入的技术也是不可判定的。然而,证明了[7]弱双相似性问题对于基本并行过程(BPP)是可判定的;最著名的下界是PSPACE-硬度[20]。对于最简单的系统结合并行和顺序操作,称为PA过程[1],弱双相似性问题是不可判定的[21]。对于赋范PA,这是一个开放性问题;最著名的下限是EXPTIME-硬度[13]。M. Kr Zeretínsket al./理论计算机科学电子笔记149(2006)1719我我22我们的贡献:我们将弱双相似性问题的不可判定边界移向BPA和BPP类,在这些类中问题被证明是可判定的。第三节给出了BPA(wBPA)和BPP(wBPP)的弱扩展问题的不可判定性在第4节中,我们加强了更严格的系统,即赋范fcBPA和赋范fcBPP系统的结果事实上,由于以下原因,这个结果对于wBPA来说并不新鲜:Mayr [13]已经证明,将最小非平凡大小为2的有限状态单元添加到BPA过程中已经使得弱双相似性不可判定。我们对他的证明的检验表明,这个结果对wBPA也是有效的2预赛我们回顾了标记转移系统和弱双相似性的定义。然后,我们定义了进程重写系统的语法,PRS的(弱)有限状态它们的语义是在标记的过渡系统。定义2.1设Act ={a,b,. . }是一组动作,使得Act包含一个特殊的无声动作τ。一个标号跃迁系统是一个对(S,−→),其中S是一组状态,−→ S × Act× S是一个跃迁关系。我们写s−→asinsteadof(s,a, s)∈−→。过渡期的风险1 2 1 2扩展到以标准方式在Act上限定单词。 此外,我们扩展L与语言L的关系是这样的,S1−→S 如果s1-w→sforsomew∈L.此外,我们写s1−→s2而不是s1第二幕−→s2。弱者τ τ∗a τ∗ aτ∗转换关系=S×Act×S定义为==−→和==−→对于所有a/=τ。定义2.2关于标号转移系统的状态的二元关系R是弱互模拟,i ∈(s1,s2)∈R,则对任何a∈Act:• 如果s−→asJthens对于somesJsuchthat(sJ,sJ)∈R,1a12a2 2 1 2• 如果s2−→sj,则s1=sj,对于某个sj,使得(SJ,SJ)∈R。2 1 1 1 2状态s1和s2是弱互模拟的,记为s1<$s2,i <$(s1,s2)∈R,其中R是弱互模拟的。我们在互模拟博弈中使用弱互相似性的特征,参见例如[23]。这是一个攻击者和防御者之间的两人博弈,在一个被认为是标记转移的状态对上进行回合系统在从一对状态(s1,s2)开始的一轮中,攻击者首先选择一i∈ {1, 2},动作a∈Act,状态sJ使得si−→sJ。辩护人20M. Kr Zeretínsket al./理论计算机科学电子笔记149(2006)17一1212111然后必须选择一个状态sJ使得s=asJ. 这是一个很好的例子形式3−i3−i3−i1 2下一轮的两个起始状态一个游戏是一个最大的序列,参与者以给定方式选择的状态对防守者是每一场比赛的赢家。一个有限的游戏是失去了球员谁不能作出任何选择满足给定的条件。可以证明,标记转移系统的两个状态s1,s2不是弱双相似的,当且仅当攻击者具有从这些开始的互模拟博弈的获胜策略。states.令Const={X,. . }是一组过程常数。过程项的集合(范围为t,. . )由抽象语法定义t::= ε|X| t.T|特什特其中ε是空项,X∈Const是过程常数;以及'和'两'分别表示顺序和平行组成。我们总是处理项的等价类,模交换性和结合性的','。’, and neutrality of 我们将过程术语分为四类:1S- 顺序XYZ,G-通用术语-具有任意嵌套的顺序和平行组成的术语,例如(X)。(Y<$Z))定义2.3设α,β是过程项α,β∈ {1,S,P,G}的类,使得α <$β。(α,β)-PRS(process rewrite system)是一个有限的重写规则集,其形式为t1<$→t2,其中t1∈αz {ε},t2∈β是过程项,a∈Act是动作.给定一个PRS重写规则,让Const(Round)和Act(Round)分别是重写规则中所有常量和所有动作一个(α,β)-PRS算子确定一个标号转移系统,其中状态是Const(α)上的过程项t∈β转换关系−→是满足以下推理规则的最小关系(回想一下,''是可交换的一(t1<$→t2)∈t−→att−→att−→attt−→at2tt.t−a→t2.t流程重写系统的形式化可以扩展为包括一个有限状态的控制单元以如下方式。2M. Kr Zeretínsket al./理论计算机科学电子笔记149(2006)1721一定义2.4设M={m,n,. . }是一组控制状态。设α,β是过程项α,β∈{1,S,P , G} 的 类 , 使 得 α<$β. ( α , β ) -sePRS ( state extended processrewrite system,状态扩展进程重写系统)是一组有限的重写规则,form(m,t1)<$→(n,t2),其中t1∈αz {ε},t2∈β,m,n∈M,a∈Act.M(k)表示在k中出现的控制状态的有限集合。一个(α,β)-sePRS算子确定一个标号转移系统,其中状态是形式为(m,t)的对,使得m∈M(n),t∈β是Const(n)上转换关系−→是满足以下推理规则的最小关系一((m,t)(n,t))∈(m,t)−a→(n,t)(m,t)−→a(n,t)1‹→2一1 2 1 2a a(m,t1)−→(n,t2)(m,t1<$t)−→(n,t2<$t)(m,t1.t)−→(n,t2.t)为了缩短记号,我们用mt代替(m,t).定义2.5一个(α,β)-sePRS系统被称为具有弱有限状态控制单元的过程重写系统或只是一个弱扩展的过程重写系统,写为(α,β)-wPRS,如果在M(ε)上存在一个偏序≤,使得每个一规则(m,t1)<$→(n,t2)满足m≤n。最后,我们回顾了在[24]中引入的具有有限约束系统的过程重写系统的扩展这种扩展直接受到并发约束编程(CCP)中使用的约束系统的激励,例如,参见[18]。定义2.6有限约束系统是有界格(C,≥,n,tt,ff),其中C是有限约束集,≥(称为蕴涵)是这个集合上的偏序,n是最小上界运算,tt(真),ff(假)是分别是C的最小和最大元素(ff≥tt和ttff)。例2.7一个由哈斯图给出的约束系统的例子FF、m,n、、TT定义2.8设α,β是过程项的类,α,β∈ {1,S,P,G},使得α<$β。设(C(n),≥,n,tt,ff)为有限约束系统. (α,β)- fcPRS(PRS with afinite constraint system)是一组有限的重写规则一形式为(m,t1)<$→(n,t2),其中t1∈α,t1ε,t2∈β为过程项,a∈Act,m,n∈C(n)是约束.22M. Kr Zeretínsket al./理论计算机科学电子笔记149(2006)17111一个(α,β)-fcPRS算子确定一个标号转移系统,其中状态是形式为(m,t)的对,使得m∈C(ε)z{ff},t∈β是Const(ε)上的一个过程项转换关系−→是满足以下推理规则的最小一((m,t1)<$→(n,t2))∈<$如果o≥m且o≥n/=ff,(o,t)−a→(on,t)2a a(o,t1)−→(p,t2), (o,t1)−→(p,t2).(o,t<$t)−→a(p,t<$t)(o,t. t)−→a (p,t. t)的范围内2 2为了缩短记号,我们用mt代替(m,t).在CCP中,约束系统描述悬挂物的可能行为。状态mt中的约束m表示存储的当前值。第一条推理规则的两个边条件也非常接近原理一用于CCP。第一个(o≥m)确保规则(mt1<$→nt2)∈n = 0仅当存储器0的当前值需要m时才使用(它类似于在CCP中问(m)。第二个条件(onff)保证存储在应用规则后保持一致(类似于一致性在CCP中处理tell(n)时的要求一个重要的观察是,存储的值只能在格中向上移动,因为on总是包含o。直观地说,部分信息只能被添加到存储中,但永远不能收回(存储是单调的)。我们注意到,在状态为o的情况下开始的转换的执行一在存储器上,由规则(mt1<$→nt2)∈ n生成,意味着对于存储p的每个后续值,满足条件p≥m和p≠n/=ff(因此,该规则的使用不能被未来存储第一个条件p≥m来自存储的单调行为第二个条件来自以下两个事实:规则的约束n只能在规则的第一次应用中改变存储;并且pn=p对于存储的任何后续状态p都定义2.9An(α,β)-fcPRS ε在ε的状态m0t0中赋范当且仅当,对于所有满足m0t0−→εmt的状态mt,对于某些o∈C(ε),mt−→εoε某些类别的(α,β)-PRS对应于广为人知的模型,如有限状态系统(FS)、基本进程代数(BPA)、基本并行进程(BPP)、进程代数(PA)、下推进程(PDA,见[4]的证明)和Petri网(PN)。引入了其他(α,β)-PRS类,并命名为M. Kr Zeretínsket al./理论计算机科学电子笔记149(2006)1723、、、、sePRSwPRS、、fcPRS,,,,,,,,,PRS(G,G)-PR,S、、 、、、、sePAD,,, sePAN、、、、、wPAD、、,WPAN、、、、、、fcPAD 、、、,,fcPAN、、、、、垫 ,,,潘(S,G)-PR, S......(P,G)-减贫战略、、、、、、、、SEPA,,,,o,,ooo,,哦哦哦 ,wPA 、、、哦,ooooo, fcPA,、、、、、、{se,w,fc}PDA=PDA=seBPA PA、、、、{se,w,fc} PN=PN(S,S)-PRS(1,G)-PR,S、、、、、(P,P)-PRS、、、、、 、、、、、、、、、、seBPP=MSA、wBPA,wBPP↑不可判定、、......fcBPA,,fcBPP、、,_BPA(1,S)-PRS,,- -- -- -_,BPP(1,P)-PRS、、......、、、、、_,_,,__,,_,_↓可判定、、、、、、{se,w,fc} FS=FS(1, 1)-PRSFig. 1.具有弱双相似可判定边界的层次结构。[12]《明史》:“明者,明也。图1给出了(α,β)-PRS类别与首字母缩略词之间的对应关系。代替(α,β)-sePRS、(α,β)- wPRS和(α,β)-fcPRS,我们使用前缀“se-”、“w-”和“fc-”与对应的(α,β)-PRS类的首字母例如,我们分别使用wBPA和wBPP而不是(1,S)-wPRS和(1,P)-wPRS最后,我们注意到seBPP也被称为多集自动机(MSA)或并行下推过程(PPDA)。图1描述了所考虑的类的表达能力之间的关系一个类的表达能力是通过一组可由该类定义(直到强互模拟等价)的标记转换系统来衡量的两个类之间的实线意味着上层类比下层类更严格地表达。虚线表示上层类至少和下层类一样具有表达性(严格性只是我们的推测)。详情可参见[11,10]。、、、24M. Kr Zeretínsket al./理论计算机科学电子笔记149(2006)17问题:扩展(α,β)-PRS类实例:一个扩展的(α,β)-PRS系统n_n和它的两个状态mt,mJtJ问题:两个状态mt和mJtJ是弱双相似的吗?3弱双相似的不可判定性在本节中,我们证明了弱双相似性对于wBPA和wBPP类是不可判定的更确切地说,我们研究了扩展(α,β)-PRS类的下列问题.3.1wBPA在[13]中,Mayr研究了PDA中需要多少控制状态才能使弱双相似性不可判定的问题。定理3.1([13],定理29)对于只有两个控制状态的下推自动机,弱双相似是不可判定的.证明是通过减少邮政所构造的PDA只有两个控制状态p和q。快速检查结构表明,由此产生的下推自动机实际上是wBPA系统,因为没有将q变为p的转换规则,并且每个规则在左侧只有一个过程常数因此,迈尔定理3.2对于只有两个控制状态的wBPA系统,弱双相似性是不可判定的。3.2wBPP我们证明了Minsky 2-计数器机器的非停机问题可以归结为wBPP的弱双相似性问题。首先,让我们回忆一下明斯基2计数器机器和不停机问题的概念。明斯基2计数器机,或简称机器,是一个有限序列N = 11:11,12:12,.,l n−1:i n−1,l n:halt其中n≥ 1,l1,l2,.,l,n是标签,并且每个i,j是用于以下操作的指令:• increment:ck:= ck+1; gotolr,or• 测试和递减:如果ck>0,则ck:=ck-1;gotolrelse gotols其中k∈ {1, 2}且1≤r,s≤n。M. Kr Zeretínsket al./理论计算机科学电子笔记149(2006)17251J机器N的语义由标记转换系统给出,其状态是形式(lj,v1,v2)的配置,其中lj是要执行的指令的标记,v1,v2是分别表示计数器c1和c2的当前值的非负整数转移关系是满足以下条件的最小关系:如果ij是指令形式Inc• c1:= c1+ 1;转到lr,则(lj,v1,v2)−→(lr,v1+1,v2)对所有v1,v2≥0;Dec• 如果c1>0,则c1:= c1- 1;gotolrelsegotols,则(lj,v1+ 1,v2)−→零(lr,v1,v2)和(lj,0,v2)−→(ls,0,v2)对所有v1,v2≥0;以及操作C2的指令的类似条件。我们说机器N(的计算)停止,如果存在数v1,v2≥0使得(l1,0,0)−→n(ln,v1,v2)。 让我们注意到这个系统是确定性的,即对于每个配置,最多有一个从配置。不停机问题是决定给定的机器N是否不停机。这是一个无法解决的问题[15]。让我们固定一台 机器N = l1:i1,l2:i2,. ,l n−1:i n−1,l n:halt. 我们构造wBPP系统,使得其状态simL1和simLJ是弱双相似当且仅当N不停顿。粗略地说,我们创建一个集合wBPP规则允许我们通过两组独立的项来模拟N的计算如果在N的计算中达到指令停止,则来自一个集合的对应项可以执行动作停止,而来自另一集合的对应项可以执行动作停止J。因此,起始项是弱双相似的,当且仅当机器不停止。我们将要构建的wBPP系统使用五个控制状态,即SIM、校验1、校验J、校验2、校验J。我们将每个标签lj和1 2每个计数器ck具有过程常数Lj,LJ和Xk,Yk。一Xk的x个副本和Y k的y个副本的并行合成,写作Xx<$Yy,K K表示计数器ck的值为x-y。 因此,术语尺寸L=1x1x2y2和simLJ<$Xx1<$Yy1<$Xx2<$Yy2关联11 2 211 2 2机器N的配置(lj,x1−y1,x2−y2)。一些规则包含辅助过程常数。在下文中,β代表以下形式β=Xx1<$Yy1<$Xx2<$Yy2。控制器会显示check,checkJ对于k∈ {1, 2},1 1 2 2kk用于测试计数器Ck的空性。唯一适用于这些控制状态是:检查1X1CHK1<$→检查1ε检查2X2chk2<$→检查2ε检查Jchk1JJchk2J1年1次 <$→检查1ε检查2Y2<$→检查2ε26M. Kr Zeretínsket al./理论计算机科学电子笔记149(2006)17K辛杰n我们可以很容易地确认,当且仅当ck的值用β表示等于零在下文中,我们为机器N的每个指令构造一组wBPP规则。同时,我们认为攻击者获胜的唯一机会是模拟机器而不作弊,因为每一次作弊都可以通过防守者攻击者的策略是当且仅当机器停止时停止:ln:停止Halt指令被翻译成以下两个规则:停止Ln <$→simεsimLn哈尔特J<$→simε显然,状态simL n<$β和sim LJ<$β不是弱双相似的。增量:lj:ck:= ck+1;转到lr对于机器N的每一个这样的指令,我们将以下规则添加到机器N:SIMIncJ公司Lj <$→simLr<$XksimLj <$→simLr<$ Xk显然,从状态simLj<$β并且sim L J<$β最终处于状态sim L r<$X k<$β和sim L J<$X k<$β。JR测试和递减:lj:如果ck>0,则ck:= ck-1;转到lr,否则转到ls对于机器N的任何这样的指令,我们将两组规则添加到Ck,一组用于ck>0的情况,另一组用于ck= 0的情况。wBPP形式主义没有能力重写对应于标签lj的过程常数并同时检查ck是否>0因此,在互模拟博弈中,攻击者必须决定ck>0是否成立,即他会玩一个行动DEC还是一个行动零。我们表明,只要攻击者试图作弊,防守者可以赢得比赛。在这一点上,我们的wBPP规则的构建使用了称为防御者选择的技术的变体在从状态对s1,s2开始的一轮中,攻击者被迫选择一个特定的转换(由波浪形一箭头)。 如果他选择一个不同的跃迁,比如sk−→s,其中一k∈ {1, 2},则存在一个转移s3−k−→s,使防御者达到相同的状态并赢得比赛。这项技术的名称是指事实上,在攻击者选择特定的转换之后,防御者可以选择具有相同标签的任意转换这些过渡是M. Kr Zeretínsket al./理论计算机科学电子笔记149(2006)1727JC,z12月,RJJ布雷尔由实线箭头指示虚线箭头代表辅助转换,迫使攻击者播放特定转换。首先,我们讨论为ck>0情况设计的以下规则DecDecDecsimLj <$→simAk,r sim Ak,r <$→checkkεsim Bk,r <$→simLr<$ YkSIMDec十二月J十二月JLj<$→simBk,rsim Ak,r <$→simLr Yk sim Bk,r <$→simLr YkSIMJdec十二月J十二月JLj<$→simAk,rsim Ak,r <$→checkkεsimBk,r <$→checkkεSIMJdec十二月JLj<$→simBk,rsim Ck,r <$→simLr YkSIMJdec十二月JLj<$→simCk,rsimCk,r <$→checkkε情况可描述如下。simLj β、simLJ βdeccccCccCcC、、、十二月,、、、、DecDec,z12月,z,z,z,zcJcc,o,,zJ,z,zzsimAk,rβsimBk,rβsimCk,rβ布雷尔十二月DecDec布雷尔德雷奇布雷尔DecDecdeccccCc、、、、布雷尔布雷尔布雷尔布雷尔特尔布雷尔布雷尔布雷尔布雷尔布雷尔朱尔CccCcZHZJCC、、、、、、zz, zJcheckkβsim LrYkβsim LjYkβcheckkβ让我们假设在开始于状态simLjβ,simLJβ的一轮中,攻击者决定执行动作dec。基于辩护人原则在这里使用的选择,攻击者必须玩过渡模拟LJβDec−→simCk,r<$β,而防守者可以选择从simLj<$β要么到simAk ,r<$β要么到simBk ,r<$β。因此,该轮将在状态simAk,r β,simCk,rβ或状态simBk,rβ,simCk,rβ中结束。再次使用防守者checkkβ或simLrYkβ,以及simLJYkβ或checkJβ。精确的组合R K由辩护人选择防守方不会选择任何一对状态其中一个控制状态是SIM而另一个不是,因为这样的状态显然不是弱双相似的。因此,互模拟博弈的两轮考虑结束于一对状态,或者simLr<$Yk<$β,simLJ<$Yk<$β,或者checkkβ,、C28M. Kr Zeretínsket al./理论计算机科学电子笔记149(2006)17checkJβ。R K后一对是弱双相似的,如果由β表示的ck的值为零,即攻击者在他决定玩一个动作时作弊。 这意味着如果攻击者作弊,防御者获胜。 如果攻击者正确地玩了动作dec,那么任何一个玩家迫使获胜的唯一机会就是完成这些动作。M. Kr Zeretínsket al./理论计算机科学电子笔记149(2006)1729R、J布雷尔、SJS、、、在状态simL rY kβ、sim LJY kβ中的两轮,对应于具有标签lj的测试和递减指令的正确模拟。现在,我们关注为ck= 0情况设计的以下规则零零零simLj <$→simDk,ssim Dk,s <$→checkkεsim Ek,s <$→simLsSIM零零J零JLj<$→simEk,ssim Dk,s <$→simLssim Ek,s <$→simLsSIMJ零零零Lj<$→simDk,ssim Dk,s <$→simGksim Ek,s <$→simGkSIMJ零零JτLj<$→simEk,ssim Fk,s <$→simLssim Gk <$→simGk<$ YkSIMJ零零τJLj<$→simFk,ssim Fk,s <$→simGksimGk <$→checkkYk情况可描述如下。simLj β、simLJ β零cccCccCc、、、零,、、、零零、零,、、、Ccc、、、、cc,t,zt,zsimDk,sβsimEk,sβsimFk,sβ布雷尔零电压布雷尔布雷尔零零泽rro布雷尔布雷尔布雷尔布雷尔零零0cccccccCc,零、、、、、、布雷尔布雷尔特尔布雷尔布雷尔布雷尔北京赛车pk10、、、zz,z检查kβsim Ls<$βsim LJ<$βsim Gk<$βτmJ检查JYm βK K让我们假设攻击者决定采取零行动。防守者互模拟博弈从状态simLj<$β和simLJ<$β开始。这两轮结束于一对状态simLs<$β,simLJ<$β或一对形式检查kβ,检查JYmβ,其中m≥1;防守者的所有其他选择都领先K K他的损失。与前一种情况一样,后一种可能性旨在双关语-30M. Kr Zeretínsket al./理论计算机科学电子笔记149(2006)171任何可能的攻击者作弊。如果攻击者的动作为零,并且用β表示的c k的值,比如v k,为正值,那么他就是在作弊。4在这种情况下,防守方可以控制两轮比赛以状态结束。[4]我们不必考虑当β表示ck的负值时的情况,因为这种情况在ttimL1中是可查的,因为t imL′仅仅是不受惩罚的查。M. Kr Zeretínsket al./理论计算机科学电子笔记149(2006)1731SS11111checkkβ,checkJYvkβ,其中该值是非常相似的。如果这是个计划-KK正确地,即由β表示的ck的值为零,则防御者必须控制所讨论的两个回合,以状态simLsβ、simLJβ结束,对于任何m≥1,状态checkkβ,checkJYm<$β不是弱双相似的到K K综上所述,攻击方的欺骗行为可以被防守方的胜利所惩罚。如果如果攻击者正确地玩游戏,则两个玩家获胜的唯一机会是在两轮之后结束于对应于正确的模拟所考虑的指令。有人认为,如果两个玩家都想赢,那么两个玩家都会正确地模拟机器N的计算。计算是有限的,当且仅当机器停止。状态simL1和西姆·L·J在这种情况下不是弱双相似如果机器不停止,游戏是无限的,防守者获胜。 因此,这两个国家是弱在这种情况下,bissimilar 换句话说,状态simL1和simLJ的构造的wBPP图是弱双相似的当且仅当Minsky 2-计数器机器N不会停止。因此,我们证明了以下定理。定理3.3 wBPP系统的弱双相似性是不可判定的。4更多限制类在这里,我们加强了前一节的结果。我们将表明,弱双相似性仍然是不可判定的fcBPP和fcBPA系统。此外,这甚至适用于它们各自的赋范版本(即,如果在弱双相似性问题的实例中,给定的fcBPP/fcBPA系统在两个给定的状态下都是赋范的)。因此,弱双相似性对于赋范wBPP和赋范wBPA也是不可判定的。4.1规范fcBPP在本小节中,我们证明了赋范fcBPP系统的弱双相似性是不可判定的设WBPP是在3.2小节中构造的wBPP系统。我们记得,给定任何固定的Minsky机N,我们已经构造了一个wBPP系统:使得其状态simL1和simLJ弱双相似当且仅当N不会停止。基于k,我们现在构造fcBPP k_J及其两个状态simL1k_D和simLJk_D,使得它们满足与前一段中给出的相同条件,并且k_J在两个状态simL1k_D和simLJk_D中均被赋范。32M. Kr Zeretínsket al./理论计算机科学电子笔记149(2006)17、、. .、、11约束系统的定义如下。FF,德尔,,,. . . . . ,,检查,,检查J检查,检查J一,一,二,二,,,.、、、. . 、、SIM卡,TT设 Const ( J ) ={D}Const ( j ) , Act ( J ) ={norm}Act ( j ) , 其 中D/∈Const(j)是一个新的过程常数,norm/∈Act(j)是一个新的动作.该集合包含所有的重写规则和以下规则:(1) ttD规范<$→delD,(2) del(3) delτX<$→一X<$→对于所有的X∈Const(εJ),对于所有的X∈Const(J)和a∈Act(j),有delX。过程常数D使能将存储的值改变为del的范数动作。从状态simL1D或simLjD开始,每个可达状态包括过程常数D或存储器的当前值已经改变为del。当store的值被设置为del时,可以使用类型(2)的规则来使状态赋范。因此,在两个状态simL1D和simLjD中赋范。类型(3)的重写规则已经被引入,这是由于在所考虑的fcBPP系统中,不能禁止任何进一步应用取自于BPP的原始规则的事实利用博弈中的范数作用,得到了弱双相似状态。由于只有攻击者才能决定行动,但这并不改变3.2节中讨论的获胜策略。因此,定理3.3可以被加强如下。定理4.1赋范fcBPP系统的弱双相似性是不可判定的。4.2标准fcBPA在这一小节中,我们证明了这个问题对于赋范fcBPA仍然是不可判定的我们的证明是PDA证明的一个稍微扩展的翻译M. Kr Zeretínsket al./理论计算机科学电子笔记149(2006)1733波斯特对应问题(Post's Correspondence Problem,PCP)实例:一个非一元字母表和两个有序的单词集A ={u1,.,u,n}且B ={v1,.,v n},其中u i,v i∈ n+问题:是否存在无穷多个指数i1,...,i m∈ {1,...,n}suc h thatui1. . . uim=vi1. . . vim?[13]在fcBPA框架下。我们使用[13]的符号使证明具有可比性。证明是基于Post的对应问题的简化,这是已知的不可判定的给定PCP的任何实例,我们现在构造一个赋范fcBPA矩阵及其两个状态pTB,pTJB,使得pTB和pTJB弱双相似当且仅当PCP的实例有解。约束系统包含元素tt、p、check1、check2、del和ff的顺序如下。FF,德尔,、、、检查1, ,pTT、检查2......我们使用过程常数T、TJ、T1、TJ、T2、TJ、Gl、Gr、B和Ui、Vi,1 21≤i≤n。A的作用是a,b,c,τ,norm,1,... ,n和字母n。在接下来,U代表过程常数的连续项{U,|1 ≤i≤n},类似地,V代表过程常数的连续项,{V i|1 ≤ i ≤ n}。现在,我们构造一组重写规则。类型(1)-(10)的规则、34M. Kr Zeretínsket al./理论计算机科学电子笔记149(2006)17J1一2一一pT <$→pT1τpT <$→pGrτpT <$→τpGrpG r<$→ pG r V i对于所有i∈ {1,.,n}一pGr <$→一pTJpT1 <$→pGlpJpG BT1 <$→lpJpTJT1 <$→ 2τpG l<$→ pG l U i 对于所有i∈ {1,.,n}τpGl <$→pT2如果存在PCP实例的解,防御者可以使用这些规则在状态pT2UB和pTJVB中完成互模拟博弈的前两轮(从pTB和pTJB开始),其中U和V形成PCP实例的解。前两轮互模拟博弈如图2所示。我们使用与3.2小节中相同的符号表示箭头。下面的六条规则构成了互模拟博弈的两个后续回合,并允许攻击者决定是否检查索引的相等性或U和V的字的相等性。在第一种情况下,攻击者使用动作b导致约束检查1,而第二种可能性由c标记并在约束检查2中结束。重写规则如下。一(11)ppT(12)pJ一 pTJT2<$→3T2<$→3(13)pbBcheckε(14)pJcheckεT3→1T3→1(15)pcCcheckε(16)pJcheckεT3<$→2T3<$→2现在,我们列出了用于上一段中提到的检查阶段的规则在规则(19)和(20)中,我们使用一个简短的符号,可以建设(一)(二)(三)(四)(五)(六)(七M. Kr Zeretínsket al./理论计算机科学电子笔记149(2006)1735,J,J,Jτ、、、,τ,J,J、、、z一得双曲余切值.,,12,JpTBpTJB,,z,JpGrBτ∗,J, .,Ja、J,J,J......、、,J,J,J,J,J,J,J,tcJpT1B一JJpGrVB一JTJVB,t,t,t,t,t,,z,τpG B<$p G BV B,tl l,t.,t.∗τ∗τ,t,at不,JpGlUBτJ,t,t,t,t,t,t,t,tJ,tpT2UBp TJVB图二、互模拟博弈的前两轮可以用标准规则来表达重写规则如下。我(17)check1 U i<$→ check 1 εfor all i∈ {1,.,n}我(18)检查1 V i<$→检查1 ε,对于所有i∈ {1,.,n}ui(19)检查2 U i<$→检查2 ε ,对于所有i∈ {1,...,n}vi(20) 检查2 V i<$→检查2 ε,对于所有i∈ {1,.,n}最后,我们添加规则,使系统规范。规则(21)和(22)的构造也在[13]的注释30中讨论。类型的规则(21) 使norm动作将store的值更改为del。在任何状态下,只要store的值被设置为del,就可以使用类型(3)的规则来使状态赋范。因此,它在所有状τ∗36M. Kr Zeretínsket al./理论计算机科学电子笔记149(2006)17态下都是赋范的。类型(23)的规则使所有状态由约束del和a
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- WebLogic集群配置与管理实战指南
- AIX5.3上安装Weblogic 9.2详细步骤
- 面向对象编程模拟试题详解与解析
- Flex+FMS2.0中文教程:开发流媒体应用的实践指南
- PID调节深入解析:从入门到精通
- 数字水印技术:保护版权的新防线
- 8位数码管显示24小时制数字电子钟程序设计
- Mhdd免费版详细使用教程:硬盘检测与坏道屏蔽
- 操作系统期末复习指南:进程、线程与系统调用详解
- Cognos8性能优化指南:软件参数与报表设计调优
- Cognos8开发入门:从Transformer到ReportStudio
- Cisco 6509交换机配置全面指南
- C#入门:XML基础教程与实例解析
- Matlab振动分析详解:从单自由度到6自由度模型
- Eclipse JDT中的ASTParser详解与核心类介绍
- Java程序员必备资源网站大全
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功