没有合适的资源?快使用搜索试试~ 我知道了~
ICAR程序:重写系统分析与复杂性界限的隐式分析方法
网址:http://www.elsevier.nl/locate/entcs/volume59.html页系统介绍:重写系统复杂性J. - Y. 中1洛丽亚,Calligrame项目,B.P. 239,54506 Vand uvre-l es-Nancy Cedex,France摘要本文介绍了ICAR程序,它分析了一阶函数程序。 ICAR是在Ptime和Pspace的两个特征的基础上,通过项重写、终止序和多项式有界的拟解释给出的。1分析师ICAR我们认为,长期重写系统建立在三个不同的集:函数符号(定义的符号),构造函数和变量。函数符号和构造函数按优先级F排序,构造函数被认为是优先级的最小元素。程序是一组重写规则。ICAR(Implicit Complexity AnalyseR)首先检查给定重写系统的终止性,然后试图找到其复杂性的界限。本文的工作是基于[5,7,2]的复杂性分析。通过记忆化的程序转换是基于Jones的工作[4]。使用终止排序(多集路径排序或词典路径排序)检查终止。然后,可以通过结合使用的终止或排序和准解释来确定复杂性。ICAR可能能够告诉计算的函数是在Ptime或Pspace中。我们的方法的主要利益之一是,这种分析给出了一个上限的复杂性计算的功能,而不是在程序的复杂性。这种复杂性分析被称为隐式分析。因此ICAR也给出了一种有效地达到这一界限的方法(即一种新的操作语义)。1 电子邮件:moyen@loria.frc 2001年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。2!然后可以使用不同的操作语义运行程序,并通过实验验证先前获得的理论界。ICAR是用Objective Caml编写的。可以从http://caml.inria.fr下载Objective Caml,从http://www.loria.fr/下载ICAR。2程序和语义2.1重写系统定义2.1术语、模式和函数规则的集合按以下方式定义(构造项)T(C)3 u::=cjc(u 1;;u n)(基项)T(C;F)3s::=cj c(s1;;sn)j f(s1;;sn)(项)T(C;F;X)3t::=cj xj c(t1;;tn)j f(t1;;tn)(模式)P3p::=cjx jc(p 1;;;p n)(规则)D3d::=f(p1;;pn)!不其中x 2 X,f2 F,c 2 C 2.项t的大小jtj是t中符号的数量。定义2.2程序是D-规则的集合E,使得对于每个规则f(p1;;pn)!E,e的t在t中也以某种模式pi变化。2.2语义签名C[F]和规则集E构成了一个重写系统,它给我们带来了操作语义。简要回忆改写理论的一些词汇。关于进一步的细节,人们可以参考德肖维茨和茹阿诺的调查[3],我们从那里得到了符号。重写关系!由程序main引起的定义如下:如果s是从t得到的,应用E.关系!是自递的关闭!. 最后一次!s的意思是t!s和s是正规形式,即 不得适用其他规则。我们现在给出并发程序的语义,即相关重写系统是并发的程序。解释域是构造代数T(C)。定义2.3设main是一个并发程序,main2F是一个函数符号. 由 main计算的函数是部分函数J main K:T(C)n!其中n是主的元数,其定义如下。为2 函数符号使用打字机字体,构造函数使用粗体字体。3MPOS姆波蒂Smpof(:;ti;:)f 2 FSCSImpog(t1;; t n)fF gf(s 1;;s m)mpog(t1;;tn)g2名F;f 2名F、S、Cfs1;;sngmft1;;tn gfFgf;g2Fg(s1;;sn)mpof(t1;;tn)所有uFig. 1. 多集路径排序2T(C);JmainK(u; u)=vimain(u; u)!!v = 2 T(C)。我1n1n请注意,由于规则的形式,构造函数项是一种范式;由于程序是连续的,所以它是唯一定义的。否则,即如果不存在这样的范式,则J_main K(u_1; u_n)是under ned的。3终止顺序和准解释3.1终止令定义3.1设是项上的一个序。的多集扩展m定义如下:M=fm1;;mkgmfn1;;nk g=N当且仅当 M6=N且存在置换使得:存在j使得m jn(j)为了所有的我,我n(i)定义3.2多集路径排序(MPO)在图1的规则中定义。MPO程序是这样的程序,使得对于每个规则l! 雷莫波湖定义3.3让是一种对条件的命令。词典学扩展l的递归定义如下:(t1;; tn)l(s1;; sm)当且仅当t1 s1或t1 = s1且(t2;:; tn)l(s2;:; sm).4定义3.4字典式路径排序(LPO)在图2的规则中定义。一个LPO程序是这样一个程序,对于每个规则l! 利波湖5LPOSlpotislpof(: ;ti; :)silpof(t1;;tn)gFfg(s1;;sm)lpof(t1;;tn)(第1条;;sn)l(t1;;tn)fFgsjlpof(t1;;tn)g(s1;;sn)lpof(t1;;tn)图二. 词典路径排序3.2准解释定义3.5元数为n的符号f的准解释是函数LfM:Nn7!因此:LfM是有界的LfM(非严格)递增LfM(X1;X n)Xi,对所有in.LcM(X1;; X)=PnX +对于所有构造函数c,其中> 0是一个n常数i=1i拟 解 释 递 归 地 扩 展 到 通 常 的 项 : Lf ( t1;;tn ) M=LfM(Lt1M; :;LtnM)一个程序允许一个准i n解释,如果对于每个ch规则l! r,LrMLlM.拟解释不足以证明程序终止。实际上是一个单规则程序f(x)! f(x)允许多项式拟解释,但不终止。注3.6如果用严格不等式代替前面定义中的所有不等式,就得到多项式解释的定义。解释被广泛地用于证明程序的终止性.最近,Bonfante,Cichon,Marion和Touzet在[1]中指出,多项式解释本身也可以给出程序复杂性的一个界但是解释比准解释更有限制性,有些程序实际上承认准解释,但不承认解释。3.3定理定理3.7允许准解释的MPO程序可计算的函数集恰好是Ptime,即多项式时间内可计算的函数集6证据 参见[7]。2定理3.8可由允许准解释的LPO程序计算的函数集恰好是P空间,即在多项式空间中可计算的函数集。证据 参见[2]24执行有两件事要执行。首先,确定程序是否由MPO或LPO终止,然后确定它是否允许准解释。使用排序的终止是一个众所周知的问题。如果给定优先级,则它是Ptime可计算的;如果必须找到优先级,则它是NP完全的。幸运的是,ICAR使用了通常顺序的限制:构造函数的优先级总是小于任何函数符号。权利要求4.1在这个限制条件下,可以在关于程序大小的二次时间中找到优先级。因此,MPO或LPO的终止可以在时间2ck中检查,其中k是函数符号的最大值,c是常数。证据见第5.1和2节主要难点在于第二部分。事实上,不知道准解释是否是可判定的。严格不等式的类似问题(即,结束多项式解释)似乎是不可判定的。幸运的是,准解释很容易找到,因为程序表示的上界是一个很好的候选者。所以,即使对计算机来说写一个是一项艰巨的任务,对程序员来说也是一项容易的工作。这个想法是提供一个潜在的准解释与重写规则,程序只需要检查它。当然,存在能够处理符号计算的程序。因此,检查准解释的明显方法是将这项工作委托给这样一个程序。目前,ICAR使用Maple作为准解释检查器。Maple可能无法检查某些不等式(特别是那些使用大量max的不等式)。据我所知,没有任何软件能够正确对待他们,但一个正在开发的法布里斯鲁耶在LIP6(巴黎),并应可在今年年底在当前的实现中,ICAR返回Maple无法解决的准解释,并希望用户不会那么笨拙。7实施例4.2(i) 下面的程序计算两个一元数的加法和乘法。add(0)! yadd(S(x); y)!S(add(x; y))mut(0; y)!0multt(S(x); y)!add(y; mut(x; y))它以MPO或LPO终止,并允许一个准整数解:LaddM(X;Y)=X+Y,LmultM(X;Y)=XY,L0M=1,LSM(X)=X+1. 让我们验证最后一条规则的准解释Lmult(S(x);y)M=L multM(LS(x)M; Y)=(X+1)YLadd(y;mult(x;y))M=Y+Lmult(x;y)M=Y+XY(ii) 可以计算两个字符串的最长公共子序列的长度如下:max(n; 0) nmax(0; m) Mmax(S(n); S(m))!S(最大值(n; m))lcs(x;)!0lcs(; y)!0lcs(a(x); a(y))!S(lcs(x; y))lcs(b(x); b(y))!S(lcs(x; y))lcs(a(x); b(y))! max(lcs(x; b(y)); lcs(a(x); y))lcs(b(x); a(y))! max(lcs(x; a(y)); lcs(b(x); y))通过设置最大Flcs,这是一个MPO程序。它有一个准独立的解释 : L0M=LM=1 , LSM ( X ) = LaM (X ) =LbM (X ) =X+1,LmaxM(X;Y)=LlcsM(X;Y)=max(X;Y).所以程序计算Ptime中的函数。请注意,程序的显式复杂度是指数级的。多项式界是通过memoization获得的:操作语义被修改,如图3所示每次计算函数调用时,其结果都存储在缓存中,如果下次需要相同的调用,则将直接重用8ICAR能够使用或不使用缓存它记录了计算所用的时间和空间9按值调用记忆时间空间时空41763219771277510169417489716424935215101726375012222220123456n(x)= vE;`hC; Xi!hC; vic2 CE;`hC i1;t i i! hC i; v iiE;`hC 0; c(t 1;; t n)i!hCn; c(v 1;; v n)if2FE;`hCi1;tii! hCi;vii(f(v 1;;vn);v)2CnE;`hC0;f(t1;;tn)i!hCn;viE;` hC;ti!hC ;vi f(p)!r 2 Ep0 =vE ;0`hC;ri!hC;vii1 i i i伊因E;`hC0;f(t1;;tn)i!hC[(f(v1;;vn);v);vi图三. 带缓存的(即:缩减步骤的数目以及高速缓存和环境的最大大小计算lcs(an();bn())的结果是:时间度量是达到范式所需的归约步骤的数量,空间度量是环境和缓存的大小,即存储到环境中的对象数量加上存储在缓存中的对象数量。这些测量不是非常准确,因为执行缩减步骤所需的实时时间和项的大小取决于项。但在这两种情况下,增量在项的大小上都是多项式,因此多项式边界没有被打破,并且测量结果给出了一个关于发生了什么的不那么糟糕的想法目前,每次计算函数调用时,其结果都存储在缓存。所以,缓存中有很多未使用的东西,10有些计算只做一次,但仍然存储:这部分缓存不会被使用。但是重写系统是按MPO排序的,这提供了很多关于它的信息。所以,知道它,实际上有一种方法可以最小化缓存,如[6]所述5更多关于执行5.1在多项式时间引理5.1设t=f(u1;un)和s=g(v 1;vn)是两项。 如果gFf蕴涵s mpot,则gFf蕴涵s mpot。证据 如果t和s在gFf时是有序的,则对于所有i; 1 i n,存在一个j; 1Jn使得vimpouj(根据MPO的定义)。所以对于所有i,vimpo t,所以这两项是有序的,如果gF f.2引理5.2设t=f(u1;un)和s=g(v 1;vn)是两项。 如果gFf蕴涵s lpo t,则gFf蕴涵s lpot。证据 通过对LPO的定义,该假说隐含着一种潜在的危险。2引理5.3设t=f(u1;un)和s=g(v 1;vn)是两项。 如果s mpo t或s lpo t,则s中的任何符号(函数或构造函数)的优先级都不能大于t中最大的符号。证据显而易见,因为具有最大优先级的符号将导致最大的术语。2引理5.4设l!R是重写规则,使得Rmpol或Rlpo1。r中的任何符号的优先级都不能大于l的头符号是的。 由于l是重写规则的左手边,l=f(p1;;pn)其中p i是模式,即仅在变量和构造函数上构建的项。由于构造函数的优先级小于任何函数符号,因此f的优先级最高。所以根据前面的引理,它也必须具有r的最大优先级。2推论5.5求优先级是在多项式时间内完成的。证据 通过检查重写规则和引理5.4,我们得到一组形式为fFg的约束。然后,任意两个符号之间的图可达性决定了fFg是否成立。如果既有fFg又有gFf,那么一定有fFg。 如果只有gFf,则引理5.1和5.2告诉我们选择g不会损失任何东西F F. 所以优先级是在polynomial time中找到2因此,这导致了以下用于nding优先级的算法:11(i) F或each函数symbolf,创建三个空集Af、Bf和Cf。(ii) F或each规则f(p1;;pn)!r,并且对于每个ch函数symbo l g2r,在Af中添加g。(iii) 对于每个函数符号f,执行:(a) 把f加到Cf上。(b) Bf Af(iv) 而9f使得9g2Bf(a) 把g加到Cf上。(b) BfBfS Agn g.(v) 如果f2Cg和g2Cf,那么fFg. 如果f2Cg和g2=Cf,则fFg. 该算法的第一步扫描规则,并建立一个第一组的控制,形式fFg的应变。这是在时间上线性的程序的大小该循环构建了先前通过图可达性获得的约束的传递-响应闭包。它是在函数符号数量的二次时间内完成的。集合A f包含f的近邻。 B f包含从f可读取但尚未处理的节点,Cf包含从f可读取且已处理的节点。5.2排序和准解释一旦找到了优先级,检查任何一种顺序的终止都是很容易的。人们只需要比较这两个术语的头部符号,并遵循图1和图2的定义。如前所述,确定多项式拟解释可能是一个不可判定的问题。但是,函数的语义似乎是一个很好的候选者(例如,函数add,计算两个数字的加法,允许加法作为准解释)。当然,自动地确定语义也是不可判定的。但是当一个人写一个程序时,他应该知道程序将计算什么,所以他可以给ICAR一些很可能是准解释的东西。6一个简单的会议首先,加载一个程序并打印它。>加载多个>printadd(Z,x0)-> x0add(S(x0),x1)-> S(add(x0,x1))mult(Z,x0)->Zmultt(S(x0),x1)-> add(x1,mult(x0,x1))[S](x0)=(x0)+(1)12[Z]()=1个[mult](x0,x1)=(x0)*(x1)[add](x0,x1)=(x0)+(x1)该程序包含重写规则和准解释。然后ICAR可以检查其复杂性。>检查该程序由MPO终止。准解释是OK的。该函数是Ptime可计算的。人们可以加载一个新程序,检查其复杂性,并使用不同的操作语义计算一个术语的值。>load lcs>printmaxi(Z,x0)->x0 maxi(x0,Z)-> x0maxi(S(x0),S(x1))-> S(maxi(x0,x1))lcs(E,x0)-> Zlcs(x0,E)-> Zlcs(A(x0),A(x1))-> S(lcs(x0,x1))lcs(B(x0),B(x1))-> S(lcs(x0,x1))lcs(A(x0),B(x1))->maxi(lcs(A(x0),x1),lcs(x0,B(x1)lcs(B(x0),A(x1))->maxi(lcs(B(x0),x1),lcs(x0,A(x1)[B](x0)=(x0)+(1)[A](x0)=(x0)+(1)[E]()=1 [S](x0)=(x0)+(1)[Z]()=1[lcs](x0,x1)=max(x1,x0)[max](x0,x1)=max(x1,x0)>检查该程序由MPO终止。准解释是OK的。该函数是Ptime可计算的。13>setcbv公司简介传值>eval lcs(A(A(E))),B(B(B(E))))使用时间: 219空间使用:2结果:Z14联系我们>getsemMemoization>eval lcs(A(A(E))),B(B(B(E))))使用时间: 97空间使用:17结果:Zsetcbv和setcbv切换按值调用语义或存储器。getsem返回当前语义。时间和空间度量是所需的约简步骤的数量,以及存储在环境和缓存中的术语的数量>load exp>print d(Z)->Zd(S(x0))-> S(S(d(x0)exp(Z)->S(Z)exp(S(x0))-> d(exp(x0))[S](x0)=(x0)+(1)[Z]()=1[exp](x0)=x0[d](x0)=(2)*(x0)>检查该程序由MPO终止。对于准解释,方程3不是递减的。函数是PrimitiveRecursive。>load add_error>printadd(Z,x0)-> x0add(S(x0),x1)-> S(add(x0,x1))[S](x0)=(x0)+(1)[Z]()=115[add](x0,x1)=max(x1,x0)>检查该程序由MPO终止。无法检查等式2:((max((x1)+(1),x 0))-(max(x 0,x1)-(1)。函数是Primitive Recursive。16Maple可能会发现准解释的一些麻烦。目前,没有采取任何措施来纠正它,用户必须找到另一个准解释,然后重试。返回的结果要么是相对于准解释严格增加的第一个方程(即左手边的解释严格小于右手边的解释),要么是符号Maple无法发现的多项式(在这种情况下,因为符号不是常数)。>load qbf>print或(TRUE,x 0)->TRUE或(TRUE,x 0)-> x 0并且(TRUE,x 0)-> x 0并且(x 0,x 0)-> xeq(Z,Z)-> TRUEeq(S(x0),S(x1))-> eq(x0,x1)eq(Z,x0)-> Eq(x0,Z)-> Eq(x0,NIL)->Eq(x 0,CONS(x1,x2))->或(eq(x 0,x1),qbf(OR(x0,x1),x2)->或(qbf(x0,x2),qbf(x1,x2))qbf(AND(x0,x1),x2)->和(qbf(x 0,x2),qbf(x1,x2))qbf(EXISTS(x0,x1),x2)-> or(qbf(x1,x2),qbf(x1,CONS(x0,x2)qbf(FORALL(x0,x1),x2)-> and(qbf(x1,x2),qbf(x1,CONS(x0,x2)[FORALL](x0,x1)=((x0)+(x1))+(1)[存在](x0,x1)=((x0)+(x1))+(1)[AND](x0,x1)=((x0)+(x1))+(1)[OR](x0,x1)=((x0)+(x1))+(1)[VAR](x0)=(x0)+(1)[CONS](x0,x1)=((x0)+(x1))+(1)[NIL]()=1[S](x0)=(x0)+(1)[Z]()=1()=1[TRUE]()=1[qbf](x0,x1)=(x0)+(x1)17[X](x0,x1)=max(x1,x0)[eq](x0,x1)=max(x1,x0)[and](x0,x1)=max(x1,x0)[或](x0,x1)=max(x1,x0)>检查18该程序不会因MPO而终止。程序通过LPO终止。无法检查公式10:(max(x1)+(x2))+(1),x0))-(max(x0,max(x2,x1)。函数是多重递归的。在一些更棘手的例子中,Maple可能无法找到一个或多个多项式的符号,即使它是常数。这可能可以通过比当前实现的更聪明地使用Maple来7ICAR的未来我们的想法是将ICAR插入到ELAN3中,ELAN 3是Loria开发的一个相当大的系统,用于处理术语重写系统。对一些系统的复杂性有一个界限对ELAN的人来说是非常有用的。在2001年春季和夏季,Mitch Harris在TOM中重写了ICAR,这是ELAN术语的(未来)解析器。引用[1] Bonfante,G., 西雄,一、玛丽恩J. -是的,和图泽,H. 具有多项 式 解 释 终 止 证 明 的 算 法 。 Journal of Functional Programming 11(2000).[2] Bonfante,G.,Marion,J.-是的,和Moyen,J. - Y. 空间有界的字典序终止序。在PSI(2001年7月),计算机科学讲义,Springer。[3] Dershowitz , N. , 和 Jouannaud , J. - 理 论 计 算 机 科 学 手 册 B 卷。 ElsevierScience Publishers B. V. ( NorthHolland ) , 1990 , ch. Rewritesystems,pp. 243{320.[4] 琼斯,N。高阶类型的表达能力,或者没有缺点的生活。函数编程杂志11,1(2000),55{94。[5] Marion,J.- Y. 分析程序的隐含复杂性。信息与计算(2000)。出现。[6] Marion,J.-Y. 计算的复杂性和隐含性,实用理论,2000年。受阻。[7] Marion,J.-是的,和Moyen,J. - Y. 具有时间限制证明的高效一阶函数程序 解 释 器 。 在 LPAR ( 2000 年 11 月 ) , 计 算 机 科 学 的 第 1955 卷 ,Springer,第100页。25{42.193 http://www.loria.fr/equipes/protheo/SOFTWARES/ELAN/
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 京瓷TASKalfa系列维修手册:安全与操作指南
- 小波变换在视频压缩中的应用
- Microsoft OfficeXP详解:WordXP、ExcelXP和PowerPointXP
- 雀巢在线媒介投放策划:门户网站与广告效果分析
- 用友NC-V56供应链功能升级详解(84页)
- 计算机病毒与防御策略探索
- 企业网NAT技术实践:2022年部署互联网出口策略
- 软件测试面试必备:概念、原则与常见问题解析
- 2022年Windows IIS服务器内外网配置详解与Serv-U FTP服务器安装
- 中国联通:企业级ICT转型与创新实践
- C#图形图像编程深入解析:GDI+与多媒体应用
- Xilinx AXI Interconnect v2.1用户指南
- DIY编程电缆全攻略:接口类型与自制指南
- 电脑维护与硬盘数据恢复指南
- 计算机网络技术专业剖析:人才培养与改革
- 量化多因子指数增强策略:微观视角的实证分析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功