没有合适的资源?快使用搜索试试~ 我知道了~
重写关系的非对称传递和拟序
理论计算机科学电子笔记59第四次(2001年)URL:http://www.elsevier.nl/locate/entcs/volume 59. html17页s非对称传递关系Georg Struth1信息化建设Albert-Ludwigs-Univerrsit?tFreiburgGeorges-Ko?hler-Alle e52D-79110 Freiburg i Br.,德国摘要我们将Knuth-Beneficiary完备化方法从方程重写推广到具有非对称传递关系和拟序的重写。主要区别如下:一般非基情形的具体化似乎超出了一阶逻辑。当项是线性的或函数是非单调的时,它就在这个范围内。该程序需要临界对计算,甚至在地面情况下也不需要简化不是不关心不确定性,而是基于搜索。应用程序包括有序的决议和有序的链式计算,基于规则的声明程序和算法的发展,程序和可达性分析(重写逻辑)和传播的不等式约束。1介绍重写通常侧重于等式逻辑和项范式。在这种情况下,它通过规范项重写系统产生了某些自由和有限表示代数中的字问题的解决方案。克努特-贝内特过程从方程的具体化中逐步构造这样的规范系统。等式重写和补全已经成功地集成到自动化的第一和交互式高阶演绎系统中。我们的主要贡献是指定,正确性证明和讨论Knuth-Benzinger完成程序超越方程的非对称传递关系和拟序。这个扩展的一部分只需要对方程的情形作一些微小的修改 但也有重要的分歧。 一般非基情形的具体化似乎超出了一阶逻辑。 它依赖于上下文变量,并涉及上下文统一问题[7,13],其可判定性是开放的。非对称完备化第1struth@informatik.uni-freiburg.de·c2001由ElsevierScienceB提供的用户。 V. 操作访问和C CB Y-NC-ND许可证。的真理2在一阶逻辑中,当项是线性的或函数是非单调的。该程序需要临界对计算,甚至在地面情况下也不需要终止。简化不是非对称重写和完备化不仅作为方程情形的一般化而有趣我们认为,一个主要的应用在于基于规则的规范和声明式编程。完成过程本身可以以基于规则的方式抽象地和声明性地描述[2]。更有趣的是,它们为声明性过程和算法的开发提供了通用元过程。事实上,来自universsal代数的Knuth-Bendixpro-cedure,来自计算机代数的Grobnerbasealgorithms和来自计算逻辑的有序归结过程可以作为一般完备过程的实例或精化而导出[14,6,17]。特别地,归结规则本身是分配格的非对称临界对计算。非对称完备也隐含在传递关系和准序的有序链演算中[3,18]。此外,它是最近一些声明式同余闭包算法的主要成分[10,5]。在所有这些情况下,声明性方法产生简单、统一和可读的规范,因为所有程序都是从关键对计算和简化的一般完成机制开发的此外,由于主要的数据结构隐藏在元过程中,有效的算法以一种相当抽象和直接的方式出现。我们画了一个例子,使用非对称完成的基于规则的动态算法折叠圈的有向图或构造相关的偏序从一个给定的准序。这和一般的非对称完备化,对于状态转移系统的可达性分析是有用的。此外,重写逻辑[12]中的执行序列分析似乎也很有趣。在那里,重写是(并发)计算的模型像非对称重写一样,它超越了连续性或终止性等属性,但不使用语法归约排序提供的任何过程控制案文的其余部分组织如下。第2节包含一些初步定义。第3节概述了重写与非对称传递关系和拟序的基础第四节给出了传递关系的一个基Knuth-Benzinger完备化过程,并证明了它的正确性。第5节进一步讨论了程序。第6节将该过程扩展到拟序。第七节讨论了它对无根据情况的解除.第8节描述了一个简单的应用。第9节是结论。的真理3→|∼∅∪∼∈∼∩2预赛设T(V)是V中的一组具有签名的项和变量。如果V=,我们写T=,也就是说所有项都是基础。 我们用带有节点或位置在幺半群N中的NIV标记树来识别项。n表示根,ni表示节点n的第i个子节点。一个变量在一个项中是线性的(非线性的),如果它恰好标记一个节点(至少两个节点)。替换是一个映射σ:VT(V).我们将它与它对T_∞(V)的同态扩张相联系。对于一个项t和一个替换σ,一个节点是tσ的骨架位置,如果它有一个来自t中的一个标号。它是tσ的一个变量实例位置,如果它的祖先之一在t中有一个来自V的标签。s[t]p含糊地表示用t替换位置p处s的子项sp以及t作为位置p处s的子项的出现。一个集合A上的二元关系是一个拟序,如果它是自反的和传递的,是一个偏序,如果它也是反对称的和一个等价的,如果它是自反的,传递的和对称的。<在我们的上下文中,拟序和偏序之间的区别每一个拟序都自然地导出一个偏序。<关系=<>是等价的而A/上的关系<$定义为[x]<$[y] i <$x y对所有x,y A是一个偏序。当仅为传递性时,可以理解为部分等价。<是一个偏序,它只部分自反。我们特别研究了项集合T_∞(V)及其相关项代数A上的传递关系和拟序。 由n元运算符号f表示的运算f A是单调的(在每个参数中),如果s1t。(I,R,R,S,S)(I,R,S,s,t,s)(I<${s t},R,S),(I,R,R<${s→Rt},S),(I,R,R,S<${s→St}),(I,R,S)(I,R,S)(I,R,S)(SIMPLIFY)的真理8如果s t,则s→Rt或s→St是冗余的。(I{s},,R,S),(DIAGONAL)(I,{s},R,S)的真理9>−→设M是T上有限多重集的集合。 设S=M×T×T。 让在T上有一些约简序,并证明了(严格)子项序3。我们在S中通过一个序环ε ε来构造一个集合,其中ε ε的多集扩张(也用ε表示)的字典序组合用于第一个分量,εε用于第二个分量,εε用于第三个分量。一个证明步骤测度是一个映射μ:T×T→S,定义为证明步骤w=(si−1,si)乘以4({si−1,Si},,),如果si−1→Isi,(表示任意项),µ:w›→({si−1},l,si),如果si−1→R si,通过规则l→r,({si},,),如果si−1→({si},l,si−1), 如果si−1→Ssi,根据规则l→r。证明被度量为证明步骤的多集,采用多集扩展我的天啊。 机器人保持秩序的继承wellfoundednes的从m。 如果不引起混淆,我们将把它们全部用“”表示。现在我们可以用类似于方程的方法证明下面的定理。定理4.1(i)Ct的规则,除了D教育CE听起来很简单关于证明顺序的规则。(ii) 证明序的引入导致了与C t规则相对应的证明转换关系的终止。(iii) Ct是正确的,如果它是公平的。一个成功的非对称完井过程的极限状态是一个正态系统.我们只给出一个草图。完整的证明可以在[16]中找到(ad i)S简化规则是通过定义的简化规则,因为冗余规则被删除。对于ORIENT规则,我们论证如下。考虑不等式s t和ts。那么左手法则可以推导为:(I{s t},,R,S)(I<${s t},R<${s−→Rt},S)(I,R,R<${s−→Rt},S)第一步是演绎推理,因为给一个已经存在的不等式增加一条规则第二步是删除步骤,因为第一个分量是µ(s t)µ(sRt(ad(二) 奥连特和S的含义,这是直接从(一)。为DEDU cE,可以应用类似的论点,也使用临界对引理3在非基的情况下,我们使用(严格的)基序«。s被t包含,如果t的某个子项是s的instance。4 我们也可以滥用记号来写μ(s t)或μ(s→Rt)。的真理10R基本上是衡量的第一个组成部分。因此,所有的推理规则都是反单调的。(ad(三)在运行中的感应如果某个证明不是重写证明,那么它必须包含一个SR证明或一个可约的无序步骤否则,如果某个证明包含一个后来被删除的步骤,那么它可以被一个更小的证明所取代,通过归纳重写证明。 ✷5讨论方程完备性与非对称完备性之间有三个主要区别。首先,即使在基本情况下,DEDU cE也不被SIMPLIFY所包含。其次,S简化规则基于搜索,不能像等式那样被细化为一步规则。第三,即使在有理由的情况下,程序也不必终止。我们现在进一步讨论这三种现象。让我们首先考虑与左侧的等式DEDU cE规则和右侧的CCOLLAPSE规则相关的证明模式(参见图10)。[2])下图中。l1[l2]RR=r1l1[r2]l1[l2]RRr1l1[r2]El1[l2]RR=r1l1[r2]l1[l2]Rr1l1[r2]E崩溃有一个额外的但书,关于赔偿金,这在地面情况下三次举行。然后,方程DEDU cE简化为CCOLLAPSE,成为一个简化步骤。在非接地情况下,这并不成立。以f(f(x))−→a的DEDU cE推论为与自己。它是f(a)a。在这里,不满足最优条件这一步并不是简单的塌陷。在非对称的情况下,对应于DEDU cE和SIMPLIFY的证明模式是l1[r2]SR=l1[r2]S俄.西=s(IRS)+l[l]rl[l]rt t1 2112I1和他们的屁股。第一个转变不能简化为第二个转变。由于缺乏对称性,DEDUcE图中S的箭头与(I<$R<$S)+中的箭头方向相反。这个观察很有趣--作为非对称Knuth-Benchmark特殊化的有序归结分配格的完备化[17]。地面分辨规则是地面分辨规则的一个变体,因此不是简化规则。现在让我们考虑下图中的方程简化规则SIMPLIFY、CCOMPOSE和CCOLLAPSE的真理11一B1BB3b0的s[lσ]s[lσ]l1l1REt=RtRr1[l2σ]=Rr1[l2σ]s[rσ]s[rσ]Er1[r2σ]Rr1[r2σ]Rl1[l2σ]RR=r1l1[r2σ]l1[l2σ]Rr1l1[r2σ]E显然,所有用I、R和S代替E和R的东西都是不可靠的;它们改变了理论。 当然,这是由于缺乏对称性。 因此,在非对称完备化中,搜索冗余证明不能像在等式的情况下那样进一步细化。这是另一个有趣的相似之处有序的决议,其中消除冗余规则是基于搜索。这也是由于分配格的分解和完备化之间的对应关系。现在让我们考虑终止。我们刚才已经看到,DEDU cE规则即使在基本情况下也是不可缺少的以下示例显示了接地非对称完成的非终止。例5.1设b> f> a为常数a、b和元1函数f的优先级,它被扩展为包含子项序的约简序。 关系f(b)b2>b1。迭代这个参数会产生一个无穷序列b1<$b2<$b3<$. 与上界a,它不与n的良好基础相矛盾。一b0的当然,对于非对称重写意义上的简化链,这会发生。根据Kéonig引理,这种情况在一个无限分支的节点上是唯一可能出现这种发散的然而,对于规则项重写系统,在规则的较小项中没有新变量可能出现,没有无限分支,因为重写只能在项中的有限多个位置发生,并且当没有新变量时,实例化的可能性也是有限的。正如上面的例子所示,这种情况可能会出现在临界对计算中。非对称简化工具可以通过允许用仅由与要丢弃的规则属于同一集合的规则组成的finer重排来替换规则 对于规则的非对称项重写系统,Rr可以被精化,如果存在一个证明l+r长度2. S的定义是对偶的。 细化规则的证明被称为细化或细化证明。这可以通过删除规则(I,R,S),(I,R,S(I,R,S)(I,R,S)如果s→Rt或s→St,则可以分别定义。重写规则的改进不会减少证明测度,但也会破坏完成过程的终止性然而,他们保持正确性,因为这个属性只取决于消除关键对。在一个仅由临界对计算组成的完备过程中,没有精化的临界对比有精化的临界对多。的真理13≺≺另一方面,一个R规则(或S规则)可以通过一个精化来删除那么同样的简化在细化之后就不可能了。在示例5.1中,对于例如,规则f(b)→Rb最终可以在存在额外规则的情况下被简化,并且该过程可以终止。 如果初始R-规则简化的证明是精炼的,这种简化可以被阻止,规则f(b)→Rb可能持续存在,过程可能发散。重新定义规则应为了谨慎使用,也可以使用可以简化的规则目的,但不用于临界对计算。6拟序的基完备化当是一个拟序时,非对称基补的过程必须适应,因为在存在反射性的情况下,对角线不需要<重写的理论也略有不同,如第3节所示。这里,我们只是指出了非对称传递关系完备化的一些困难见[16]更正式的治疗。完成过程的状态现在是三重的(I,R,S),因为不需要对角线。 ADELETE规则(I{ss},R,S)(I,R,S)抛弃了关系的相关部分,取代了对角规则。其余的状态转换规则和概念类似于传递关系,但对三元组进行操作。我们用Cq表示转移规则集。传递关系的完备化过程和拟序的完备化过程之间的差别是如此之小,以至于定理4.1仅需微小的修改就成立额外的DELETE步骤不是障碍。复杂性度量甚至比传递关系的复杂性度量稍微简单科. 给定一个归约排序,证明排序现在定义如下。我们将一个度量({si−1,Si},,),ifsi−1→Isi,µ:w→Rsi({si−1},l,si),ifsi−1→Rsi,byrulel→r,({si},l,si−1),如果si−1→Ssi,根据规则l → r。有一个证明步骤(si−1,si)我们比较元组-除了证明步骤-就像传递关系一样。我们通过与定理4.1的类比得到下面的陈述.定理6.1(i)Cq的规则,除了D教育CE听起来很简单关于证明顺序的规则。的真理14→→(ii) 排序的结果导致了与Cq规则相对应的证明转换关系的终止。(iii) Cq是正确的,如果它是公平的。一个公平、无故障的非对称完井过程的极限状态是一个正常系统。证明主要遵循定理4.1。7非接地 非对称完备化第三节说明了地面完成程序的解除对非地面情况有严重的障碍。二阶上下文变量已经被引入来表示非线性变量产生的变量临界对。有三种情况值得关注。首先是非相容的情况(没有函数是单调的),其次是线性的情况,第三是一般情况。非相容的情况作为传递关系和拟序的有序链演算的基础是有趣的[3,18]。线性情况的完成过程是显而易见的。线性是过程的不变量。转换规则是等式非基和非对称基情况的组合例如,DEDU cE规则具有以下形式l2→Sr2l1[r2]p→Rr1,l2→Sr2[l1]pl1→Rr1。l1σ[l2σ]p→ → →→或X(11)。因此,带有上下文变量的项被引入到该过程中,并且骨架关键对的D教育规则也取决于上下文统一。这是有问题的,特别是对于使用约简排序。对于通常的一阶非基项,我们定义所有基实例的stisσtσ人们可以对上下文术语使用类似的定义然而,这一标准在实践中是否有效值得怀疑也可以将上下文项编码为二阶项,但不编码为高阶模式。那么,这是值得怀疑的,是否减少排序仍然存在这种编码。与非线性变量相关的问题的部分解决方案是检测重叠结构中的重叠,即手动猜测上下文。在[16]中讨论了一个简单的例子-也使用R仿射规则-在半格方面。目前还没有一个完全令人满意的解决非地面非对称完井的方法。8一个简单的应用程序现在,我们使用非对称完成开发一个基于规则的声明性算法,用于有向图中的循环消除或用于从给定的拟序构造偏序唯一的区别是对反射部分的处理。为了简单起见,我们忽略了它。这对于状态转换系统的可达性分析是很有趣的,因为分解出循环压缩了状态空间。为了将一个圈折叠成一个有向图的单个节点,我们必须能够找到(部分)等价类的唯一表示因此,我们扩展我们的完成过程的状态,包括一组E的无序等式和一组T的等式重写规则。这里我们只对这个算法进行了验证。一个单独的文件将致力于讨论克努特-Benziran完成与平等和不平等,包括进一步的应用。例8.1给定优先级cicji ij,我们考虑下图左侧Rc1Rc0c2Sc3RRc1Rc0SS c2Sc3R请注意,在每个循环的表示中,必须至少有一个R-和一个S-步骤(如果循环可以排序)。关键对c3c1(来自
下载后可阅读完整内容,剩余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直接复制
信息提交成功