用图变换解方程的完备性和效率提高，基于术语图缩窄的方程解法

网址：http://www.elsevier.nl/locate/entcs/volume51.html12页用图变换解方程Angret Habel1法赫贝里奇信息大学在OldenburgPostfach 2503，D-26111 Oldenburg，GermanyDetlef丰满2约克大学计算机科学系Heslington，York YO10 5DD，英国摘要我们回顾了术语图窄化的概念，作为一种方法来解决方程的术语图上的变换。术语图缩窄结合了术语图重写和一阶术语union。 这个机制对于所有的术语重写系统都是完备的，术语图重写在这些系统上是规范化的和一致的。uent。这尤其包括所有收敛项重写系统。完备性是指对于给定方程的每一个解，项图缩窄都能找到等价的或更一般的解。使用术语图而不是术语的一般动机是为了提高效率：共享公共子术语可以节省空间并避免重复计算。1引言缩窄是在定理证明领域中，针对方程理论由收敛项重写系统表示的情况而设计的一种方程求解方法。[7]第一个证明了narrowing的完整性。为了减少缩小过程的搜索空间，Hullot[13]考虑了一种称为基本缩小的策略，并表明它仍然完成.后来，窄化作为函数式和逻辑编程相结合的计算范式变得流行起来。 此后？研究部分由TMR网络GETGRATS和ESPRIT工作组APPLIGRAPH支持。1 电子邮件地址：habel@informatik.uni-oldenburg.de2 电子邮件地址：det@cs.york.ac.ukc2002年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。2G一直是许多研究活动，提高效率的缩小和放宽要求的完整性（见调查哈纳斯[11]）。为了有效地实现缩窄，建议用类似于图的数据结构来表示术语。这是因为项的简单树表示强制在重写步骤中复制子项，因此导致评估工作的倍增。我们提出的术语图缩小作为一种方法来解决方程的术语图上的变换。术语图收缩对于所有术语重写系统是完全的，术语图重写是规范化的和并发的。这尤其包括所有收敛项重写系统。完备性意味着如果一个方程由一个项图表示，那么对于这个方程的每个解，都有一个从这个图开始的缩小推导，它计算一个等价的或更一般的解。换句话说，给定方程的每个解等效于通过缩小生成的解决方案的实例。术语图窄化结合了术语图重写和一阶术语union（参见[19]关于术语图重写的概述和[22]该领域的论文集）。我们使用[18，19]中研究的项图重写模型。除了重写规则的应用之外，它还允许在术语图上折叠步骤以增加共享程度这个模型对于等式推理来说是文[9]给出的项图收缩的完备性证明利用了项图重写与项重写之间关于终止性、连续性和相关性质的关系的现有结果。第二节简要回顾了项图重写的研究，详细内容参见文献[19，20]第三节介绍了基于术语图重写和术语图替换的术语在第4节中，我们讨论了两种限制形式的术语图收缩的完备性，称为最小折叠和最大折叠收缩。最后，在第5节中，我们概述了基本术语图缩小的概念，并参考了一些相关的工作。我们的介绍基于[10，9]。2项图重写设和X分别是函数符号和变量的不相交集合，其中每个函数符号f都有一个自然数arity（f）0，变量的arity为0。元数为0的函数符号称为常数。环[X]上的超图是由两个顶点集VG和EG组成的系统G = hVG;EG; labG;attGi，它是一个标号函数labG：EG ！ [X]，以及附加函数att G：EG ！V其中分配一串节点到超边e，使得attG（e）的长度为1 + arity（labG（e））。从现在起，超图和超边被简称为图和边。设G是一个图，G的一条边e满足G（e）=vv1：vn，其中v是e的结果n，v1; ：vn是e的正则n. Theresultnodev3LH表示为res（e）。对于每个节点v，G[v]是由从v可达的所有节点和将这些节点作为结果节点的所有边组成的子图。定义2.1（项图）一个图G是项图，如果存在一个节点根G，每个节点从该节点根G是可达的，G是非循环的，并且每个节点是唯一边的结果节点。在图片中，我们用标签来表示边，并省略节点（因为边和节点之间存在一一对应关系）。箭头指向函数符号的参数，其中参数之间的顺序由离开符号的箭头从左到右的顺序定义2.2（项表示）项图G中的节点v表示项termG（v）=1abG（e）（termG（v1）; ：termG（vn）），其中e是具有res（e）=v的唯一边，并且其中eattG（e）=vv1：vn。 我们把项G（根G）简写为项（G）.图态射f：G！ 两个图G和H之间的H由两个函数fV组成：VG！VH和FE：EG！这是一个很好的例子，到节点，即labf= lab和attf=fHEGHEVG映射字符串v ：：vn至fV （v1）：：fV（vn））. 态射f是单射的（surjctive）iffVfE是.如果f是内射和满射，则它是同构.在这种情况下，G和H是同构的，记为G= H。定义2.3（坍缩）给定两个项图G和H，如果存在图态射G，则G坍缩为H！把根G映射到根H。这表示为G H，或者，如果态射是非内射的，则表示为G H。后一一个项图G是完全折叠的，如果没有H与GH，而G是一棵树，如果没有H与H G。很容易看出，塌陷态射是项图之间的满射，并且GH蕴涵项（G）=项（H）。一个术语重写规则l！r由两项l和r组成，和X，使得l不是变量，并且r中的所有变量也出现在l中。术语重写规则的集合R是术语重写系统。在下文中，设R表示任意项重写系统。 与R相关的术语重写关系表示为！和它的自反对称传递闭包$（见[2]的介绍项重写）。给定一个项t，用t表示一个项图，它表示t，使得只有变量是共享的。由t在去除所有用变量标记的边之后产生的图由t表示。定义2.4（Redex）设G是一个项图，v是G中的一个节点，l！r是R中的规则。一对儿！ri是一个redex，如果存在一个图态射红： ！G，称为redex态射，使得red（root l）= v。V14LRRl r2G定义2.5（项图重写）设G和H是项图，hv;l！ ri是G中的redex，具有redex态射red： ！G. 然后有一个建议重写步骤G）v;l！rH，如果H是由G构造的：（1）G1是由G去掉唯一边而得到的图，其结果结点为v. （2）G2是由不交并G1+通过对v进行归并而得到的代数其中r为0，并且将u 的图像与u0 合 并，对于ll中的u和r 中 的 u0，使得term（u）=term（u0）2X。（3）H=G[rroot]是从G2得到的项 通过移除从根G（“垃圾收集”）不可获取的节点和边缘。我们通过添加适当的折叠步骤来定义术语图重写关系）coll：G）collHifGHorG）v;l！rHfor someredexhv;l！ 里岛3术语图缩窄我们将需要替换项图中的变量。由变量x和项图G组成的对x=G是替换对。它被应用于项图H中的x标记边e，通过移除e，添加（不相交）G，并将res（e）与根G标识。定义3.1（项图替换）项图替换是替换对的 集合=fx1=G1; ：;xn=Gng， 使得x1; ：;xn是两两不同的，并且x i 6= term（G i），其中i=1;：;n。给定项graph H，将x1=G1; ：;xn=Gn同时应用于以x1; ：;xn标记的所有边缘，产生项graph H。的定义域是集合Dom（）=fx1; ：;xng，并且具有项图替换的组合定义=fx=Gjx =G2和x6=term（G）g [fy=H2jy62Do m（）g，对每个项图H满足H（）=（H）.一个项图代换引入了术语替代项映射xi到项（Gi），其中i = 1;：;n，并且每个其他变量到其自身。给定一个术语替换和一个项t，我们用t代替 （t）。 我们可以代表by集合fx1=t1; ：;xn=tng如果xi=ti fori=1; ：; n且x=x foreach变量x。术语重写规则l的变体！ r是l形式的规则！ r，其中是将变量映射到变量的单射替换。一组项ft1; ：;tn g是可单的，如果存在替换，如that1=t2=：=t n。在这种情况下，可以选择作为一个最一般的单位，这意味着对于每一个具有t1=t2=： ： ：=tn的替换，都存在一个替换使得=t n（例如参见[2]）。定义3.2（项图窄化）设G和H是项图，U是G中的一组不可变节点，l！r是R中规则的一个变体，以及一个术语g r aph替换。 这是一个很窄的台阶！r;H，如果项为5？Collf项G（u）j u 2 U g[u]的最一般单位，以及GG0=）Hv; l！R因为一些错误的错误！ G0使得U=fvjc（v）= vg.我们也用G H表示这样的一步一个项图窄化推导是形式G=G11的序列G22 ： ：n1 Gn=H。这是一个ybe由G所H在哪里=12 ：：：n1如果n2和=;如果n = 1。从现在开始，我们假设R包含规则x=？x的！ tru e，其中二进制sy mbo l =？ 而常数为真在其他任何规则中都不会发生。一个g oal是一个项的形式s=？ 难道s和t不包含=？也是真的这个目标的一个解决方案是满足s $ t的替换。例3.3设R由以下规则组成：0 + x！ Xs（x）+y！ s（x + y）0x的！0s（x）y！（xy）+yx=x！ 真正假设我们要解出g oal（zz） +（zz）=？ s（z）。 Figur e1显示了从表示此目标的完全折叠的术语图开始的术语图收缩派生。图2给出了应用的重写规则和涉及的术语替换。在每一步中，定义3.2的集合U都是单例。 注意，步骤（c）、（d）和（e）仅仅是步骤，并且步骤（f ）由步骤（d）之后的连续步骤组成 。 推 导 计 算 项 替 换 fx=0;x0=s （ 0 ） ;y=s（0）;z=s（0）g。 将这种替换限制到gal的变量，得到解fz=s（0）g。通过基于术语的缩小来解决相同的目标需要九个步骤，这表明术语图缩小可以加快解决方案的计算速度。定理3.4（窄化的合理性和完备性）设G是一个 项 graph ，使得项（G）是一个g oals=？ t.(1) 如果GM真3，那么长期是一个解决方案s=？ t.(2) 如果）是正规化的和c上的uent，那么对于每一个解决方案s=？不存在一个窄化导子GMtrue这样的术语R6[Var（G）]在下文中，我们将把陈述（2）的结论称为项图窄化的完全性。3 我们用M真表示真的项图。4 给定替换和，和VX，我们写=R [V ]，如果x$x对于每个x2 V，和R [V ]，如果有一个替换使得=R[V ]。 出现在项图G中的变量集合用Var（G）表示，即Var（G）= labG（EG）\X。7你说呢？+SS你说呢？SS+S你说呢？SSS你说呢？+s（一）(b)+0秒0（c）第（1）款0（d）其他事项（五）0（f）真实0Fig. 1. 一个术语图的缩窄推导步骤 重写规则取代（一）s（x）y！（x）y）+ yfy=s（x）;z=s（x）g（b）第（1）款0x 0！0fx=0;x0=s（0）g（c）第（1）款0 + x！ Xfx=s（0）g（ds（x）+y！ s（x fx=0;y=s（0）g你说呢？+Sz你说呢？+S+SX8）其他事项+ y）（五）（f）第（1）款0 + x！ Xx=？x的！真正fx=s（0）gfx=s（s（0））g图二.重写图1中4最小和最大塌陷缩窄在本节中，我们考虑两种限制形式的术语图收缩的完备性，其中所有步骤分别包含最小或最大折叠。定义4.1（最小塌缩）一个塌缩的GM是最小的，它依赖于一个索引hv;l！ 如 果 对 于 M0中 的 每 一项GM0M和V的 每 一 个 P外像V0，P空气hV0;l！ Ri不是索引。特别地，如果G等于M，则GM是最小的，因为没有M0 GM0M存在。一个恰当的坍缩GM是极小的，仅当l！ r不是左线性的，不能应用于G中v的任何原像。9v;l！Rv;l！R？定义4.2（最小折叠缩小）项图缩小推导是最小折叠的，如果对于每个缩小步骤G 7！ GG0 ）的方式H，COLlapsingGG0是最小的，与re peccttothere dex hv;l！RI.例如，图1的推导是最低限度的崩溃。注意，在最小程度的折叠步骤GU;1！r;H，则集合U必须是单例的。结果证明，定理3.4可以通过用最小折叠窄化替换无限制项图窄化来加强。定理4.3（极小坍缩缩缩的完备性）极小坍缩缩的完备性，只要是正规化的且连续的.我们现在转向最大收缩窄化，也就是说，我们考虑窄化导子，其中所有涉及的收缩步骤产生完全收缩的项图。定义4.4（最大收缩缩小）项图缩小推导最大收缩，如果对于每个缩小步骤G 7！ GG0）H，项graph G0完全闭合。例4.5考虑规则int（0）（0）int x（x）{exp（x）+exp（x）指定函数exp：n 7！2自然数图3演示了最大程度地折叠缩小可以解决表单的目标exp（x）=s（0）+：+s（0）|2n-t{izmes}在n +2步中，如果目标被适当地表示。（替换仅由影响图中变量的部分表示。）相比之下，基于树的收缩和最小折叠收缩都需要n的指数级步骤来解决这样的目标。虽然当项图重写被归一化并且同时时，最小折叠窄化是完成的，但是反例（参见[10]，示例30）示出了对于最大折叠窄化不是这种情况然而，通过加强对终止的规范化，可以确保最大程度的收缩收缩的完整性定理4.6（最大坍缩收缩的完备性）当收敛时，最大坍缩收缩是完备的。特别是，最大折叠窄化对于所有收敛项重写系统都 是 完 全 的 ，因为）coll是针对那些系统的。10你说呢？++expexp +X1+你说呢？++++expexp +.X2.+S+S<+你说呢？实验8>+x >+n-t倍>+ ..>x=s（ x1）.x1=s（x2）.x2=s（ x3）* *xn=0：>s0 0 0真正..+S+S0 0图三. 一个最大坍缩窄化推导5书目说明和结束语在[8]中，[21]中引入的图替换的概念被应用于项图，产生了项图的统一，重写和缩小的统一框架替代的概念允许这些概念的定义接近于术语世界中的相应定义在文献[9]中，引入了项图窄化作为通过项图上的变换来求解方程的方法缩小步骤由三个部分组成：替换步骤、折叠步骤和适当的重写步骤。在应用替换步骤之后的折叠对于使缩窄完成是必要的。[5]的主要结果是：对于所有项图重写是规范化的和并发的项重写系统，这种机制是完整性证明基于重写推导到最小塌陷推导的变换（[9]，定理4.8）和用于最小塌陷重写推导的提升引理（[9]，引理6.4），其允许将最小塌陷重写推导提升到（最小塌陷）窄化推导。5文[8 ]中关于项图窄化的定义在这方面是不够的。你说呢？++++++11在[10]中，研究了关于完备性的几种术语图缩小策略。完备性证明基于任意重写推导的提升引理（[10]，引理15），其将重写推导提升为缩窄推导，使得适当重写步骤的数量和缩窄步骤的数量一致。为了获得这种关系，在[9]（定义5.1）中的术语图窄化的定义，在下文中称为基本窄化，被扩展到同时术语图窄化，[10] (De第7点）：代替单个不可变节点，可以选择非变量节点的非空集U，计算项G（u）（对于U中的u）和重写规则的左手侧的最一般的unier，至少折叠U中的节点，并且将重写规则应用于U的图像。我们推测，每个同时的窄化步骤GH可以转换成一个基本的叙述性的衍生物GH0 苏志浩存在一个项图替换为H0H且=[Var（G）]. 这应该允许将完备性结果从同时缩窄转移到基本缩窄。基本术语图窄化，类似于基于基本术语的窄化[13]，在[15，10]中进行了研究。粗略地说，该策略禁止在由先前步骤的替换所创建的节点处缩小步骤。文[10]证明了基本项图窄化对于最内规范化和同时图重写是完全的。此外，考虑了基本收缩与两种共享控制策略的结合，得到了最小折叠和最大折叠基本收缩。前者被证明是完整的存在下，最内层的规范化和conuence，后者的存在下，终止和conuence。最大坍缩收缩有时会极大地加速收缩推导。[10]中关于（最小塌陷）基本窄化的结果纠正了Krishna Rao [15]基于项图窄化的不完整版本的分析主张。那篇论文中关于缩小的定义的问题|借用[8]|它不允许在单元的应用和重写步骤之间的折叠。因此，对于非左线性系统如keff（x;x），窄化是不完全的！ a g（b延伸到由[15 ]的主要结果解决的所有三类重写系统）。 目标函数f（x;y）=？例如，a是不能用那里给出的那种narr owing来解决的。在[4]中考虑了使用条件重写规则在丛林上缩小。狭窄的步骤是基于丛林的推力，导致一种最小的崩溃缩小。[4]中的结果旨在证明条件窄化的具体实现的正确性。Echahed和Janodet[5，6，14]在函数逻辑语言中引入了循环项图作为基本数据结构：他们将程序视为循环项图重写系统，并研究了它们诱导的重写和收缩关系。他们刻画了一类循环项图，即所谓的容许图12图的重写，并证明了容许图重写是连续的.他们进一步证明，缩小是健全的和完整的可接受的图重写，并显示某些策略的最优性的标准取决于所考虑的图重写系统我们总结了以下两个方面关于术语图收缩策略的完备性的结果图4中的条目意味着，只要术语图重写满足所提到的要求，术语图缩小策略就完成了;图5中的条目意味着存在一个反例，证明缩小策略对于具有所提到的要求的术语重写系统通常是不完整的。战略要求参考任意）collnormalizingconuent[9]，Thm.5.7基本）coll最内层范数。 &骗局[10]，Thm.22Rright-linearand）coll 正态&分布[10]，Thm.28分钟崩溃）collnormalizing[113conuent0]，Thm.26最小收集量基本）coll最内层范数。 &骗局[10]，Thm.27Rright-linearand）coll 正态&分布[10]，Thm.28最大崩溃）coll终止连接[10]，Thm.31最大 Coll. 基本）coll终止连接[10]14，Thm.31见图4。 术语图缩小策略战略要求参考任意R归一化条件[10]， 介绍基本）collnormalizingconuent[10]， 示例23最大崩溃Rright-linearand）coll正态&分布[10]， 示例30最大 Coll. 基本）collnormalizingconuent[10]， 示例3015图五. 完备性的反例未来工作的一个主题是研究最小和最大塌陷窄化与已知基本（术语）窄化的组合，如LSE窄化[3]。通过采用对重写规则的限制，如非模糊性、左线性等，也可以采取诸如需要16和懒惰收缩[1，17，16，12]，并考虑其完整性时，结合各种共享策略。引用[1] Antoy ， S. ， R. Echahed 和 M.Hanus ， A needed narrowing strategy ，Journal of the ACM47（2000），pp.776{822.[2] Baader ， F. 和 T. Nipkow ， \Term Rewriting and All That ， ”CambridgeUniversity Press，Cambridge，1998.[3] Bockmayr ， A. ， S. Krischer 和 A. Werner ， Narrowing strategies forarbitrarycanonicalrewritesystems ， FundamentaInformaticae24（1995），pp.125{155.[4] Corradini，A.和D.Wolz，Jungle rewriting：an abstract description of alazy narrowing machine ， in ： Graph Transformations in ComputerScience，Lecture Notes in Computer Science776（1994），pp.119{137.[5] 埃查赫德河和J。- C. Janodet，Admissible graph rewriting and narrowing，in ： Proc. of Joint International Conference and Symposium on LogicProgramming（JICSLP'98），pp. 325{342.[6] 埃查赫德河和J。- C.杨诺代，可容许图收缩的完备性，在：H。Ehrig和G. Taentzer，editors，Proc. Joint APPLIGRAPH/GETGRATS Workshop onGraphTransformationSystems ， TechnischeUniversitatBerlin ，Forschungsbericht2000-2（2000），pp.123{132.[7] Fay ， M. J. ， 方 程理 论中 的 一阶 unication ， 在 ： Proc. 4th Workshop onAutomated Deduction，Academic Press，Austin，Texas，1979 pp。161{167.[8] Habel，A.和D.丰满，统一，重写，并缩小术语图，在：Proc.JointRIGHGRAPH/SEMAGRAPHWorkshoponGraphRewritingandComputation （ SEGRAGRA 95 ） ， Electronic Notes in TheoreticalComputer Science2（1995），pp.35{42.[9] Habel，A.和D. Plump，Term graph narrowing，Mathematical Structuresin Computer Science6（1996）。649{676.[10] Habel，A.和D. Plump，Complete strategies for term graph narrowing，in：Recent Trends in Algebras Development Techniques，Selected Papers，LectureNotes in Computer Science1589（1999），pp. 152{167.[11] Hanus，M.，The integration of functions into logic programming：Fromtheory to practice，The Journal of Logic Programming19 20 （ 1994），pp.583.[12] Hanus ， M. ， Lazy narrowing with simpli cation ， Journal of ComputerLanguages23（1997），pp.61{85.17[13] Hullot，J.- M.，规范形式和unionical阳离子，在：Proc.5th自动演绎会议，计算机科学讲义87（1980），页。318{ 334.18[14] Janodet，J.- C.的方法，函数逻辑程序设计语言中的数据类型：可允许的图重写和缩小，博士。 论文，格勒诺布尔（2000年），法文。[15] Krishna Rao，M. R.，非复制实现中基本缩窄的完整性结果，见：逻辑编程联合国际会议和研讨会（JICSP'96）（1996），第100页。393{407.[16] Middeldorp ， A. 和 S.Okui ， A deterministic lazy narrowing calculus ，Journal of Symbolic Computation25（1999），pp.733{757.[17] Middeldorp，A.，S. Okui和T.Ida，Lazy Narrowing：Strong CompletenessandEagerVariableElimination ， TheoreticalComputerScience167（1996）.95{ 130.[18] Plump，D.，用超图重写法评价函数表达式，论文，不来梅大学（1993年）。[19] Plump，D.，项图重写，在：图文法手册和图变换计算，2：应用程序，语言和工具，世界科学，1999年页。3{61.[20] Plump，D.，术语图重写精要，2001年。在这本书里。[21] Plump，D.和A.张文龙，图的统一与匹配，《图的语法及其在计算机科学中的应用》，计算机科学讲义1073（1996），页。75{89.[22] 睡吧，R R. Plasmeijer和M. v. Eekelen，editors，\Term Graph Rewriting.《理论与实践》，约翰·威利，奇切斯特，1993年。