没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记124(2005)29-49www.elsevier.com/locate/entcsAutowrte:一个词重写系统和树自动机Ir`eneDurand1LaBRIUniversit'eBordeaux1Talence,法国摘要Autowrte是一个实验性的软件工具,用Common Lisp Oriented System(CLOS)编写,术语重写系统和自下而上的树自动机。使用McCLIM(CLIM规范的免费实现)编写的图形界面使用户无需任 何 Lisp 知 识 。 软 件 和 文 档 可 以 在 www.example.com 上 找 到 http://dept-info.labri.u-bordeaux.fr/~idurand/autowrite。自动写入是最初设计用于检查术语重写系统的按需调用属性。为此,它实现了[11,4,6,14]中使用的树自动机构造和许多有用的术语操作,术语重写系统和树自动机。关键词:树自动机,项重写1介绍HuetandL′evy[10]表明,对于正交重写系统(TRS)的类,每个非正规形式的项都包含一个所需的redex(即,在每个规范化重写序列中收缩的redex),并且所需redex的重复收缩导致规范形式(如果它存在的话)。然而,需要一般是不可判定的。为了得到可判定的近似不确定性,Hue和L′ev引入了长序TRS的子类。1电子邮件:idurand@labri.fr1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2004.11.01930I. Durand/Electronic Notes in Theoretical Computer Science 124(2005)29在强序贯TRS中,每个可约化单元中的至少一个所需的赎回可以是可预测的。此外,Hue和L′ev还指出,强序列性是正交TRS的一个可判定性质。强序列性是基于近似TRS的思想,通过用一个新的变量替换每个规则的每个右侧(这称为强近似)。这总是给出一个非常粗略的TRS近似值。一些作者[2,4,11,13,14,15,16]提出了强序列TRS类的可判定扩展。自从Comon [ 2 ]和Jacquemard [ 11 ]的工作以来在[4]中描述了用于研究按需调用(顺序性)的统一框架,其中术语重写系统的类别通过近似映射进行参数化。现在,最著名的近似(很容易定义)是[14]中研究的增长近似,它可以判定按需调用。没有TRS是强的(等于它的强近似),因为要求规则右边的每个作为回报,一些TRS已经在增长(等于它们的增长近似值)。对于这些TRS,按需呼叫是可判定的,这使得成长的案例非常有价值。Autowrte最初设计用于检查[ 7 ]中大多数示例的按需调用属性。大多数情况下,没有其他的证据它实现了按需调用理论中的树自动机构造以及对术语、术语重写系统和树自动机的许多操作。在Autowrte的第一个版本[5]中,只有按需调用属性和其他一些简单的属性可以从图形界面中获得 这个新版本的自动写入包括许多新功能。有一些新的功能与TRS相关,但最有趣的新功能是直接处理(加载,保存,与布尔操作组合)自底向上树自动机的可能性。此外,我们还增加了在线计时信息。自第一个版本以来,由于更好地选择了数据结构,运行时间得到了相当大的新功能允许测试[8]中提出的许多例子的性质,没有简单的证明可以写。2预赛我们假设读者熟悉术语重写[12]和树自动机[3]的基础知识。熟悉按需呼叫理论[10,15,11,4] [6,2,7,14]是有帮助的。I. Durand/Electronic Notes in Theoretical Computer Science 124(2005)2931一R有限签名F上的项重写系统(简称TRS)R由T(F,V)thatatsatisfyl∈/V和V(r)<$V(l)中项之间的重写规则l → r组成. 这里V是一个对变量进行赋值的数字。如果第二个条件没有被强加,我们发现说话是有用的。扩展的TRS(eTRS)。当我们近似TRS时,这种TRS自然会出现,如2.2节所解释的。基项不包含变量。线性项不包含同一变量的多次出现。Redex是重写规则左侧的一个实例. 标准形式是一个没有赎回的术语。 一个TRSR的所有基正规形的集合记为NF(R)。 eTRS是左线性(右线性,线性),如果左手边(右手边,都左侧和右侧)是线性项。如果重写规则的右侧(左侧和右侧)是基础项,则eTRS是右基础(基础)没有临界对的左线性TRS是正交的。正交TRS具有每个项至多有一个范式的性质。在本节的其余部分,我们回顾一些关于树自动机的基本定义更多的信息可以在[3]中找到。一个(有限自下而上)树自动机是一个四元组A=(F,Q,Qf,F),由一个有限签名F,状态的有限集合Q,与F不相交,最终状态和一组转换规则。 每个转移规则的形式为f(q1,.,qn)→q,其中f∈F且q1,.,qn,q∈Q或q→qj,其中q,QJ∈Q.后一种规则被称为“过渡”。因此,树自动机A=(F,Q,Qf,f)仅仅是签名F<$Q上的有限基TRS <$其重写规则具有特殊的形状,以及Q的子集Qf。设T(F)是基项的集合。一项t∈ T(F)被接受为:A若t→+q,其中q∈Qf. 所有这些项的集合表示为:L(A). 如果存在树自动机,则称子集L∈ T(F)是正则的A=(F,Q,Qf,F)使得L=L(A).构造一个识别T(F)的自动机是很容易的2.1按需呼叫设R·是扩展签名F·=F{·}上的eTRSR {· → ·}。我们说C[k]∈T(F)中的redex k是R-需要的,如果不存在项t∈NF(R)使得C[·]→t.最后,我们说R在CBN(按需调用)中,如果每个T(F)中的可约项含有R-需要的redex。定理2.1 [10]设R是一个正交TRS。(i) 每个可约项都包含一个所需的redex。(ii) 重复收缩所需的赎回导致一个正常的形式,无论何时32I. Durand/Electronic Notes in Theoretical Computer Science 124(2005)29RS⎪⎪⎪⎪所考虑的术语具有标准形式。Q因此,对于正交TRS,总是选择所需的redex进行收缩的策略是归一化的和最优的。不幸的是,所需的赎回一般是不可计算的。因此,为了获得可计算的最优策略,我们需要找到(1)可判定的需要性近似和(2)重写系统的(可判定的)类,这些重写系统确保每个可约项都有一个由(1)标识的需要的redex。2.2逼近映射设R和S是相同签名上的eTRS我们说S近似于Rif→⊆→∗ 且NF(R)=NF(S)。 近似映射是一种映射从TRS到eTRS的α具有α(R)逼近R的性质,对于每个TRSR. 给定一个TRSR,我们说R在CBNα(α-序贯)中,如果α(R)在CBN中。接下来我们定义逼近映射s、r和gr。设R是一个TRS。强近似[10] s(R)是通过将每个重写规则的右侧替换为对应左侧不出现的变量而从R获得的。非变量近似[15]通过将重写规则右侧的变量替换为不会出现在相应左侧的成对不同变量,从R增长近似[11,14] gr(R)是通过对出现在右侧的变量进行重命名而从R在相应的左手边的深度大于1。 给定TRSR和α∈ {s, n, gr},则α(R)是否在CBN中是可判定的.然而,决策过程是非常复杂的(对于s是指数的,双指数的对于R1和gr [6]),因此通常不可能用手示出特定的TRS在CBN中,即使对于非常小的TRS也是如此。然而,显示TRS不在CBN中可以更容易地通过显示不需要redex的项来完成。例2.2下面的例子取自[13]。⎧f(g(a,x),b)→xf(g(x,a),c)→xR1=f(d,x)→xn(e,e)→eI. Durand/Electronic Notes in Theoretical Computer Science 124(2005)2933⎪对于R1,我们得到以下近似的TRS:⎧f(g(a,x),b)→y⎪f(g(x,a),c)→ys(R1)=f(d,x)→y⎪g(e,e)→y⎧f(g(x,a),b)→y⎪f(g(a,x),c)→ygr(R1)=f(d,x)→x⎪g(e,e)→eR1=⎧f(g(x,a),b)→y⎪f(g(a,x),c)→yf(d,x)→y⎪g(e,e)→e例2.3下一个例子(R2)来自[15]。⎧f(g(a,x),a) →c⎪⎪f(g(x,a),b)→c⎨R2=f(k(a),x)→c⎪g(b,b)→h(b)⎪k(x)→k(x)⎧f(g(a,x),a) →c⎪⎪f(g(x,a),b)→c⎨R2=⎪⎪f(k(a),x)→cgr(R2)=R2g(b,b)→h(b)⎪k(x)→k(y)例2.4最后一个例子(R3)是Berry例子[ 1 ]的推广⎪⎪⎪⎪34I. Durand/Electronic Notes in Theoretical Computer Science 124(2005)29⎪⎪α(R)gr⎧f(x,a,b)→h(x)⎪⎪f(b,x,a) →h(x)⎪⎪f(a,b,x)→h(x)⎨R3=h(k(x))→g(x,x)⎪g(a,a)→g(a,a)⎪A(a,b)→A⎪n(b,a)→b⎧f(x,a,b)→h(x)⎪⎪f(b,x,a) →h(x)⎪⎪f(a,b,x)→h(x)⎨gr(R3)=h(k(x))→g(y,y)⎪⎪g(a,a)→g(a,a)⎪⎪A(a,b)→A⎪n(b,a) →b自动写入计算{s, n, gr}中任何近似α的α(R)。定理2.5逼近映射s,m,gr保持可逼近性.Q换句话说,给定一个可识别的树语言L,集合(→)[L]的项,α(R)-重写为L中的项是可识别的。Nagaya和Toyama [14]证明了上述增长近似的结果;识别(→R)[L]的树自动机被定义为有限饱和过程的极限。这种饱和过程与定义在Comon [2]和Jacquemard [11]中,但是通过专门使用确定性树自动机,可以处理非右线性重写规则。3Autowrte解决的实际问题3.1使某人相信对于给定的R,通过展示一个不需要R的redex的术语,很容易说服某人TRS不在CBN中。然而,说服某人TRS在CBN中并不是一件容易的事情;任何尝试通常都会以冗长乏味的证明结束,此外,这只适用于特定的TRS con。侧着身子。通常,在关于按需调用(或顺序性)的论文中,作者总是证明某些R/∈ CBN,但从未证明某些R ∈ CBN。通常,他们只是猜测或说他们认为TRS在CBN中。对于合理大小的TRS,我们可以使用Autowrice来安慰读者,因为他的直觉是TRS在CBN中。此外,在CBN中搜索具有特定属性的TRS时,我们经常惊讶地从Autowrice中了解到,与我们的直觉相反,候选TRS不在CBN中。对于Autowrte暴露的不需要R的redex,我们将立即⎪⎪⎪I. Durand/Electronic Notes in Theoretical Computer Science 124(2005)2935相信我们的错误。以Oyamaguchi 为 例, 他 在[15]中 证明 了TRSR2是 nv- 序 贯的 。 使用Autowrte可以很容易地检查R2∈ CBN。 这并不意味着R2和CBN一样是nv序贯的适当地包括类的NV顺序TRS,但存在一个最佳的和可计算的策略R2。3.2与签名扩展名相关的属性设R是左线性增长的eTRS。在文献[7,8]中,我们研究了在增加新的函数符号后,R ∈ CBN的性质是否保持对于这个问题,我们需要在我们的符号中指定底层签名。我们写(R,G)而不仅仅是R来表示使用哪个签名。我们写NF(R,F)为eTRSR在签名F上的基正规形的集合。我们用WN(R,F)表示T(F)中的所有基项的集合,这些基项在R中重写为NF(R,F)中的范式。令F∈ G。我们用WN(R,G,F)表示T(F)中具有标准形式关于(R,G)。 我们将WN(R·,G·,F·)写成WN·(下面的命题(其证明可以在附录中找到)指出,对于(R,F)∈ CBN,如果(R,{F@})∈ CBN(对于某个新的常数@),则(R,G)∈ CBN对于任何G使得F<$G。命题3.1设α是一个任意逼近映射。 设(R,F)是一个TRS,使得R∈ CBN α.让G F。 设@为新的常量符号(不在G中)。设F@= F{@}。若(R,G)/∈CBN α,则(R,F@)∈ CBN α.这就是为什么自动写入提供了测试(R,G)是否∈ CBN的可能性,其中G=F {@}。一个范式是外部的,如果它不是R中重写规则的左手边的真不可变子项的实例。所有地面的集合TRSR的外正规形记为ENF(R)。ENF(R)是一个R∈ CBN在签名扩张下保持不变的充分条件当ENF(R)= 0时,在我们所得到的所有充分条件下,正交性都是必需的.如果r∈V,重写规则l→r是崩溃的,因此包含崩溃规则的eTRS也是如此。对于正交的CBN,R是坍缩的且WN(R,G,F)=WN(R,F)的条件对于通过签名扩展保持R∈ CBN是足够的。Autowrte帮助我们找到了一些例子,表明这两个限制都是必不可少的。下面的示例显示了折叠条件的必要性:36I. Durand/Electronic Notes in Theoretical Computer Science 124(2005)29例3.2设R4为以下正交TRS:f(x,a,b(y,z))→c(i)f(c(x),c(y),z)→if(x,a,c(y))→ig(x)→b(x,i)f(a,a,a)→i h(a)→if(a,b(x,y),z)→a h(b(a,x))→af(a,c(x),y)→i h(b(b(x,y),z))→b(i,i)f(b(x,y),z,a)→a h(b(c(x),y))→if(b(x,y),b(z,u),b(v,w))→i h(c(x))→if(b(x,y),b(z,u),c(v))→i j(a,a)→if(b(x,y),c(z),b(u,v))→i j(a,b(x,y))→if(b(x,y),c(z),c(u))→i j(a,c(x))→if(c(x),a,a)→i j(b(x,y),z)→if(c(x),b(y,z),a)→ij(c(x),y)→af(c(x),b(y,z),c(u))→i i →if(c(x),b(y,z),b(u,v))→i在由重写规则中出现的所有符号组成的签名F上,令G=F {@}。自动写入能够检查• ENF(R4)=0,• (R4,F)∈ CBN<$,• (R4,G)/∈ CBNθ,如项所示,不需要(θ(R4),G)的redexj(f(k, k, k),@),其中k =h(g(@)),• WN(R4),G,F)= WN(R4),F).我们可以很容易地证明j(f(R,R, G),@)没有R(R4),G)-所需的redex:=h(g(@))→b(i,i)j(f(·,a,b(i,i)),@)→f_j(f(·,a,b(i,i)),@)→f_j(c(i),@)→f_a∈NF(R,G)j(f(i,·,a),@)→f_j(f(b(i,i),·,a),@)→f_j(a,@)∈NF(R,G)j(f(a,b(i,i),·), @)→f_j(f(a,b(i,i),·),@)→f_j(a,@)∈NF(R,G)本节中的下一个示例显示了限制的必要性,α∈ {s, n}。I. Durand/Electronic Notes in Theoretical Computer Science 124(2005)2937例3.3设R5为以下正交eTRS:f(x,a,b(y),z)→g(z)g(a)→if(b(x),y,a,z)→g(z)g(b(x))→if(a,b(x),y,z)→g(z)h(a)→if(a,a,a,x)→i h(b(x))→j(i,x)f(b(x),b(y),b(z),u)→i j(x,a)→ai→i j(x,b(y))→b(a)在由重写规则中出现的所有符号组成的签名F注意,增长近似只将规则h(b(x))→j(i,x)修改为h(b(x))→j(i,y)。设G=F {@}。自动写入能够检查• ENF(R5)=0,• (R5,F)∈ CBNg,• (R5,G)∈CBNg作为h(j(@))由i次gr(R5)-neededdredexf(n,n,n,@)的项表示,其中n =h(j(@)),• WN(gr(R5),F)= WN(gr(R5),G,F).注意,R并没有崩溃。这不是必要的,因为将单个折叠规则k(x)→x添加到R并不影响上述任何性质。对于一个ESTRSR,我们有一个很好的属性,WN(R,G,F)=WN(R,F)WN·(R,G,F)=WN·(R,F)Autowrist帮助我们证明了对xm的限制对于这一含义是必不可少的例3.4设R6为以下正交TRS:f(x,a)→a h(x,a,a)→if(a,b(x))→i h(x,a,b(y))→if(b(x),b(y))→i h(x,b(y),a)→ig(a,a)→i h(x,b(y),b(z))→b(g(y,f(x,z)g(b(x),a)→i i →b(i)g(x,b(y))→a在由重写规则中出现的所有符号组成的签名F上,令G=F {@}。自动写入能够检查38I. Durand/Electronic Notes in Theoretical Computer Science 124(2005)29• ENF(R6)=0,• WN(gr(R6),G,F)= WN(gr(R6),F),• WN·(gr(R6),G,F)WN·(gr(R6),F)如项t= h(·,i,i)所示。4Autowrte的内部Autowrte中最重要的对象是树自动机。自Autowrte的第一个版本[5]以来,人们一直致力于改进自动机的表示。因此,性能得到了改善显著。自动机的每个状态都由一个唯一的Common Lisp对象表示。比较两个状态是非常便宜的:我们只需要比较状态的引用。 一个自动机由它的签名(一系列符号),一系列对它的状态和规则的引用来表示。TRS由其签名和规则表示。(自动机或TRS的)规则集由散列表表示,给定与规则左侧相关联的键,该散列表给出相应的右侧(或者如果自动机不是确定性的,则给出相应的右侧列表给予左侧f(q1,. ,qn),相应的密钥由包含根符号f的列表组成,该根符号f之后是状态q1,...,qn.在构造自动机期间(例如,在构造识别重写为由A识别的项的项集合的CR,A期间),自动机的规则可以表示为简单的规则列表。但一旦建筑完成,规则清单是转换成如上所述的哈希表。一般来说,我们尽可能多地使用在可能的情况下,我们使用备忘录技术,以避免重复计算几次相同的调用。后者可以解释当以不同的顺序执行相同的操作时的定时的不同。5Autowrte的外部5.1自动写入规范自动写入处理一组可以交互加载的规范。一个规范由一个签名组成,可能是一组变量,后面是一个Autowrte对象列表。自动写入对象是TRS、自动机、术语集和单个术语。图5.1显示了这样一种规范的一个例子该规范定义了一种签名,其中整数和算术表示-I. Durand/Electronic Notes in Theoretical Computer Science 124(2005)2939可以表示使用+和* 的解,可以用于简化算术表达式的名为R的TRS,识别偶数集合的名为EVEN的自动机,两组名为RS(用于根稳定)和T(F)的项,以及四个基础项。操作0:0 s:1 +:2 *:2变量x yTRS R;加法+(0,x)-> x+(s(x),y)-> s(+(x,y))产品中心* (0,x)-> 0* (s(x),y)->+(*(x,y),y)自动机EVEN状态奇数偶数最终状态偶数转换0 -> even s(偶数)-> odd s(奇数)->even术语集RS0 s(x)术语集“T(F)”x项 *(*(0,s(0)),+(0,s(0)项 *(o,+(0,s(0)Term *(*(0,s(0)),o)术语% s(% s(% s(0)Fig. 1. 自动写入规范示例5.2自动写入执行的自动操作5.2.1检查自动机的属性以下是关于自动机的不同决策问题,可以用Autowrte解决。• 给定一个自动机A:判断L(A)是否为空。• 给定两个自动机A和B:判断L(A)是否等于L(B)。40I. Durand/Electronic Notes in Theoretical Computer Science 124(2005)29• 给定两个自动机A和B:判断是否L(A)=L(B)。• 给定两个自动机A和B:判断L(A)是否为空。对于后一种操作,不计算交集自动机,而是递增地计算其可访问状态,并在找到最终状态时立即停止。当某个属性不满足时,Autowrte会显示一个接地项,暴露故障。图5.2.1的屏幕截图显示了在加载图5.1所示的规范后执行的关于当前项和当前自动机的操作。 首先计算识别NF(R然后,我们检查当前项是否未被当前au识别tomaton(因为它不是标准形式)。接下来,我们计算当前自动机的补码(它识别可约项),并检查当前项是否被补码自动机识别。最后,我们检查补自动机是否不识别空语言。5.2.2构建新的自动机以下是由自动写入。• 给定一个自动机A:computeDet(A),A的确定版本。• 给定一个自动机A:计算Ac,认识到L(A)c是L(A)在整个基项集合中。• 给定一个自动机A:compute Red(A),A的简化版本,即这样每个状态都可以访问。• 给定两个自动机A和B:计算A → B。• 给定两个自动机A和B:计算A → B。• 给定一组线性项L:计算自动机AL,使得L(A L)={σ(t)|t∈L,σ是一个基替换。图5.2.2的屏幕截图显示了如何使用Autowrte执行布尔运算。我们计算了识别范式的自动机与其补集的交集我们检查所得到的自动机识别空语言。5.3与左线性eTRS相关的构造自动机设R是左线性eTRS。Autowrte可以构建以下自动机:• 构造一个自动机ANF(R),使得L(ANF(R))=NF(R)。I. Durand/Electronic Notes in Theoretical Computer Science 124(2005)2941图二.当前项和当前自动机• 构造一个自动机AENF(R),使得L(AENF(R))=ENF(R)。以下两个自动机只有在R也增长时才能构造• 给定一个树自动机A:建立一个确定性(Toyama和Nagaya∗(as在[14]中描述的),使得L(CR,A)=(→)[L(A)]。• 构造一个自动机DR,使得L(DR)=R等价于R∈ CBN[6]。42I. Durand/Electronic Notes in Theoretical Computer Science 124(2005)29图三. 自动机上的布尔运算对于CR,A,无论是Jacquemard的算法的线性增长的TRS和富山和Nagaya的左线性增长的TRS已经实现。对于DR,我们实现了[6]中提出的算法。实际上,这三个算法-为了直接计算仅具有可访问状态的自动机,已经修改了算法。这使代码复杂化,但大大减少了结构的大小。I. Durand/Electronic Notes in Theoretical Computer Science 124(2005)2943RR主要思想是递增地计算自动机。我们开始建立规则,有一个恒定的左手边。这给出了第一组可访问状态。然后,我们计算的规则,其左手边包含当前的可访问的状态,可能会给新的可访问的状态。当没有创建新的可访问状态时,我们停止。5.4eTRS的一般特性这些都是简单的属性,但可能对检查大的TRS有用• 检查TRS是否为左线性。• 检查TRS是否重叠。• 检查TRS是否正交。• 检查TRS是否崩溃。5.5左线性eTRS设R是左线性eTRS。第一组性质只涉及R的左边.• 判断范式集合是否为空。• 判断外部范式集是否为空。我们在3.2节中已经看到,ENF(R)的非空性是当签名被扩展时保持R∈CBN的当我们考虑左线性时,不断增长的电子储税券:• 给定一个树自动机A和一个项t,判断t是否∈(→n)[L(A)]。这是通过计算CR,A(见5.3节)并检查CR,A是否识别t来完成的。注意,这解决了可访问性问题(给定两个项t,s,doest→ts)作为一个单独的术语s形成了一个可由树识别的正则语言自动机• 判断R是否∈ CBN。该方法包括建立自动机DR(见5.3节),然后检查L(DR)是否= L。 如果是,则Autowrte得出R∈ CBN的结论,否则它展示了L(DR)的基项,这是一个不需要R的redex的项。 注意,为了构建DR,Autowrte必须预先计算CR,ANF(R)。• 判断R是否任意,即是否存在基项44I. Durand/Electronic Notes in Theoretical Computer Science 124(2005)29R、FRt∈T(F)使得t→∞减少到任何其他术语)。• (这意味着存在一个术语,后一个性质与签名扩展问题有关(见3.2节)。关于检查R ∈ CBN,我们不能希望对大的TRS使用Autowrte,因为构造的自动机D的大小是O(22 <$R),如[6]所示。图5.5的屏幕截图显示了使用Autowrte来决定CBNα类的权限我们证明了当前的TRS(R,F)不属于CBNs,它属于CBNε,但它的扩张(R,F@)不属于CBN ε.见图4。按需查询I. Durand/Electronic Notes in Theoretical Computer Science 124(2005)29456实验结果在表1(第17页)中,我们展示了在测试上述TRS与CBNα类的隶属关系时获得的结果,其中CBNα类具有各种近似值α。 本文给出了判定R∈ CBN α的自动机Cα(R·)和Dα(R)的状态数(st)和规则数(rl). 如果TRS不在CBNα中,则我们给出Autowrte没有找到α(R)需要的redex的见证项。表1按需呼叫结果RαCα(R·)ToyammaDα(R)(R,F)∈ CBNαStRL时间StRL时间R1、FS1758421s327270.12sf(g(f(d,a),f(d,a)),f(d,a))NV2188841s4540550s76是的gr2916883m101746055748s是的R2、FS1654813s3168713sf(g(g(b,b),g(b,b)),g(b,b))NV112684s176150.08s是的R3、FS740913s111620.03sf(f(a,a,b),f(a,a,b),f(a,a,b))NV983150年代205940.09f(f(a,a,b),f(a,a,b),f(a,a,b))gr62674s1752380.7s是的R4、FS1431814m35s12240.11sf(i,i,i)NV18653731米36秒856288327米46秒是的R4、GNV26190104小时59分钟1153530135m27sj(f(h(g(@)),h(g(@)),h(g(i),@)R5、FS566812s8280.04sf(i,i,i,a)NV566830s1913074132s是的R5、GNV613542m41s251604633m24sf(h(b(@)),h(b(@)),h(b(@)),@)R6,FS51831s86500.15是的表2(第18页)给出了用Jacquemard算法计算非确定性自变数Cα(R·)最后三列显示给出通过这个自动机的确定性,以获得一个自动机类似的确定性的一个由富山和Nagaya的算法。“NA”表示该方法不适用(因为Jacquemard的构造仅适用于线性TRS)。在表3(第18页)中,我们报告了WN(R,G,F)型试验的结果。= WN(R,F)和WN·(R,G,F)= WN·(R,F)。这些计算所需的时间可能取决于自动机Cα(R)是否由先前的计算计算出。46I. Durand/Electronic Notes in Theoretical Computer Science 124(2005)29表2Jacquemard自动机与Toyama-Nagaya自动机的比较RαCα(R·)JacquemardDet(Cα(R·))StRL时间StRL时间R1、FS1234320.84s175840.36sNV1233319.09s218880.54sgr122015.14s2916881.14sR2、FS1138111.44s165480.27sNV111802.26s112680.76sR3、FS62140.22s74091.34sNV61633.69s98310.32sgrNANANANANANAR4、FS1113301分51秒1431814.26sNV112505.93s18653734m35sR5、FS428712.95s56680.33sNV4951.0s56680.19sR6,FS41261.52s51830.67s表3利用签名扩展保持可规范化项RαWN(R,G,F)= WN(R,F)WN·(R,G,F)=WN·(R,F)时间R5gr是的是的2米33R6NV是的是的21.7sgr是的h(·, i, i)6.6s7与其他系统的我们知道另外两个实现树自动机的分布式工具:Timbuk [9]和RX [17]。Timbuk需要安装ocaml,RX需要安装ghc,而Autowrte是独立的。我们能够使用Timbuk(比RX更容易安装最初,郑明训是...I. Durand/Electronic Notes in Theoretical Computer Science 124(2005)2947RR符号,用于计算正则语言L和TRSR的后代集合(→R)[L]的过近似,然后使用它来证明不可达性。Autowrte可以用来检查可达性,也就是说,Autowrte是否∈(→L)[L],但仅适用于左线性增长的TRS。 廷巴克可以处理一些非生长或非线性情况。然而,考虑到树自动机操作的效率,Autowrte似乎快得多:我们已经尝试了由Jacquemard算法计算的自动机Cnv(R5)的确定性,该算法在0.16中运行48I. Durand/Electronic Notes in Theoretical Computer Science 124(2005)29使用Autowrte只需几秒钟,使用Timbuk需要大约3个小时。Autowrte的最新版本能够加载Timbuk规范定义TRS,术语集和自动机。8实用信息和观点Autowrte项目有一个网页,可以在URL:www.example.com上找到http://dept-info.labri.u-bordeaux.fr/~idurand/autowrite。从该页面可以下载Autowrte的图形版本。这个文件相当大,因为它包含了Common Lisp和McCLIM的很大一部分。但优点是Autowrte是独立的,不需要其他软件。Autowrte源代码包含大约6500行Common Lisp(包括图形界面)。在网页上可以找到安装指令、在线用户指南和有用的链接。自动写入会话的示例代码仍然可以改进,表演我们计划增加最小化树自动机的可能性,并将系统扩展到其他类别的自动机。引用[1] G.贝瑞 稳定的型Aldada-calculii模型。 载于1978年第5届ICALP会议论文集[2] H.来吧序贯性、一元二阶逻辑与树自动机。信息与计算,157:25[3] H.拜托,M.多谢,R.吉隆,D.卢吉斯,S.提森,和M.托马西树自动机技术与应用,1998。草案,可从www.example.com获得http://www.grappa.univ-lille3.fr/tata/。[4] I. Durand和A.米德尔多普在术语重写中通过需要计算的可判定调用(扩展抽象)。在Proc.14thCADE,LNAI的第1249卷,第4-18页[5] 我是杜兰。自动书写:一种用于重新书写系统的检查方法。在Proceedings of the 13thInternational Conference on Rewriting Techniques and Applications,卷2378 of LectureNotes in Computer Science,第371-375页,Copenhagen,2002中。史普林格出版社[6] 我是杜兰和阿达尔特·米德·多尔普。 关于通过电子邮件发送的电子邮件的复杂性。Technical报告1196[7] 我是杜兰和阿达尔特·米德·多尔普。在一个模块中,您可以通过以下方式进行识别。软件科学和计算结构的基础,计算机科学讲义第2030卷,第199-213页,Genova,2001年。史普林格出版社[8] 我是杜兰和阿达尔特·米德·多尔普。通过重新编写中的必要的内容输入来进行数据处理。出现在信息和计算,2004年。[9] ThomasGenettandVal'erieVietTriemTon g. 在廷巴克,REACHABILITYYANALY Y是一个很好的解决方案 在proc 第8次LPAI,LNAI的第2250卷,第691-702页。Springer-Verlag,2001.[10] G. 你好。-J. 我爱你。计算机在所有的系统中都是重写的,我和我。在计算逻辑中,纪念艾伦·罗宾逊的论文,第396-443页。MIT Press,1991.原始版本:第359号报告,Inria,1979年。
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功