化学规则到术语重写的图重写关系模拟及其在化学反应机理自动生成中的应用

理论计算机科学电子笔记147（2006）113-134www.elsevier.com/locate/entcs从化学规则到术语重写1Olivier Bournez2莉莉安娜·伊伯内斯库3LORIA-INRIA LORIA-UHP校园科学BP 239F-54506 Vandoeuvre-lès-Nancy Cedex，法国摘要在本文中，基于规则的程序设计领域的化学反应机理的自动生成进行了探索。 我们研究了一类图和一个图的重写关系，保留，仅更改边缘。我们展示了如何用装饰标号树或森林来表示循环标号图，然后如何将树转化为项。 图重写关系被定义，然后由树重写关系模拟，树重写关系又可以由等价项类上的重写关系模拟。因此，这种图重写可以使用项重写来实现。本研究的动机是设计的GasEl系统的动力学反应机制的产生。在GasEl中，化学反应对应于图重写规则，并通过ELAN中的条件重写规则来实现。其应用程序的控制是通过ELAN策略语言完成的。关键词：项与图重写、规则程序设计、策略语言、循环标记图、化学反应机理自动生成。1介绍在工业应用的背景下，我们已经探索了基于规则的系统和策略的使用，用于化学动力学的复杂问题：反应机制的自动生成[22，7]。在称为GasEl的该应用中，化学物质的表示使用分子1我们感谢GasEl项目的所有参与者：PROTHEO团队成员，DCPR、Nancy和标致雪铁龙汽车公司的化学家，他们为该项目提供了资金支持。2 电子邮件：Olivier. loria.fr3电子邮件：Mariana-Liliana. loria.fr4 电子邮件：Helene. loria.fr1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.06.040114O. Bournez等人/理论计算机科学电子笔记147（2006）113图[12]，由在[5]中引入并在[15]中研究的称为GasEl项的项结构编码化学溶液被建模为类似于[13]的多项集。化学反应由分子图上的重写规则表示，由GasEl项上的一组条件重写规则编码[15]。化学反应链的控制很容易使用策略语言来描述[5，6，15]，例如ELAN系统[4，16]所描述的策略语言。在[5]中，我们简要介绍了化学家和工业合作伙伴在其使用的整个背景下生成动力学机制的问题。 我们给化学问题复杂性的描述和计算问题的描述。更多详细信息见[15]，其中广泛描述了实施的原型并分析了化学家进行的定性验证。然而，[15]中没有正式给出将化学规则转化为重写规则的精确描述，既没有化学规则在分子溶液中的详细应用，也没有与项重写的形式对应。从这一点看，本文是文[15]第8章中结果的推广在本文中，我们提出了一类标记图和图重写关系非常适合的应用程序中的顶点集通过变换保持。这也是一种特殊的超边缘重写[10，11，14]。我们精确地展示了如何通过对图结构进行项编码和图重写关系来执行这种图重写通过重写模同余。这分为两个步骤，首先将循环标记图编码为装饰标记树或森林，然后将树转换为项。第一个变换依赖于循环中切割边缘的操作，这导致了隐藏边缘和显示边缘的概念[15]。第二个变换相当于在树中选择一个根，并对每个顶点的直接子图进行排序。我们证明了每个标记图重写步骤是正确模拟的一个项重写步骤模的等价关系的条款，在同一等价类中的所有条款是同一个图的表示（图同构）。这个结果证明了化学重写的GasEl实现[15]，但足够普遍，可以应用于不同的环境。通过项重写实现图重写已经由几个作者探索[3，9，19，21]。通常标记图的公理化方程的方式，图重写成为重写模公理。特别地，在[18，19]中，提出了通过多集重写来实现图重写，其中多集通过其邻接列表来表示图[8]。正如在[19]中所观察到的，这在某些方面类似于Raoult和Voisin[21]的代数公理化。本文中提出的实现基于我们在GasEl项目中所做的工作，在某种意义上说，O. Bournez等人/理论计算机科学电子笔记147（2006）113115HHCCHCHCCCHHCCHC COH简单的CH简单的简单简单芳香族CH简单的C简单H简单H芳香族 C简单简单C C芳族双C芳香族简单 CCH简单芳族C简单O简单H更高级别的实现：图不被实现为邻接列表，而是通过项来编码，以便保留更多的结构。第2节定义了装饰标记图和森林的类别，并展示了如何将标记图转换为装饰标记森林。这些结构上的重写关系在第3节中定义。第四节介绍了如何将树转化为项，以及如何将树上的重写关系转化为项重写。第5节简要说明了如何在GasEl中实施这些概念。2装饰的标记图和森林分子图[12]是一个顶点标记和边标记的图，其中每个顶点用一个原子标记，每个边用键类型标记，如图1所示。H HHHHHFig. 1. 分子图化学反应被表示为分子图重写规则的应用。图3中的化学反应是应用图2中的重写规则的一个例子，该规则打破了两个碳原子之间的简单键。简单的C·simple·C−→C·J·zJC图二. 重写规则：打破一个简单的键我们关心的是描述如何实现标记图重写关系的一个长期重写关系。我们分两步进行：首先，我们将图转化为树，或者更准确地说，转化为森林，主要是通过切割循环和引入隐边（也称为隐藏边）。这种转变在本节中定义。在第二阶段中，我们将通过选择一个根并对每个顶点的直接子树进行排序来将树转换为项。116O. Bournez等人/理论计算机科学电子笔记147（2006）113CH3|CH3|CH3-C-CH3|−→ CH3-C·+·CH3|CH3CH3图三. 化学反应2.1装饰标号图设LV和LE分别是顶点和边的不交标签集。一个修饰的标记图是一个带有特定顶点标签集的标记图：引入新的标签来处理一些圈被切割但仍然存在并通过隐边编码的事实，它们中的每一个都由一组标签LC编号。一个顶点的标号属于集合LJV=LV×P（LC× LE）。定义2.1[装饰标号图]一个在L=上的装饰标号图LV<$LE<$LC是结构G=（V，E，lab），使得(i) （V，E）是一个图：V是顶点集，E<$V×V是边集;(ii) 函数lab：V<$E−→ LJV<$LE给出• 图的每条边的标签：lab（e）∈ LE，e∈E，以及• 图的每个顶点的标号：lab（v）∈ LJV，v∈V。lab（v）的第一个元素来自LV，称为vertex_name。第二个元素是来自LC×LE的一组对，记为Pv，称为implicit_edges.G（L）表示L上的装饰标号图的集合。当V需要显式给出，它表示为GV（L）。例2.2在图1的分子图中，两条边被转换为隐式边：（i）用简单标记的边{6，11}被隐藏，得到图4的表示;（ii）用芳香标记的边{5，6}被隐藏，结果在图5中给出。氢原子未示出。图5中的第二个图是一个修饰的标记图，其中•LV={C，H，N，O，Cl，.. . }的情况下，• LE={simple，double，triple，armatic}，• L C={1，2，.. . }的情况下，O. Bournez等人/理论计算机科学电子笔记147（2006）1131171简单 2简单的 芳族 芳族5简单 C4C3芳族C9双C8C6芳香族CO简单10个C11 （1，简单）（1，简单）（2，芳香族）简单2简单 芳香族的41C3芳族C5 9简单 C芳香双链C8C6芳香族CO简单10个C11 （1，简单）（1，简单）（2，芳香族）C C C4简单2简单 芳香族的C1C3简单 C5 9芳族C8芳香双皮边（{6，11}）C6 10C芳香族7芳香族单体 简单C11图四、隐藏边{6，11}并在顶点6和11上使用标签（1，简单）对其进行编码C C CC Chide−an−edge（{5，6}）图五. 隐藏边{5，6}并在顶点5上用标签（2，aromatic）对其编码 和6设（C，Pv）=（C，{（1，simple），（2，aromatic）}）是图5中给出的第二个装饰标记图中节点v= 6的顶点标记：• v= 6的顶点名为C;• Pv是v=6的隐边的集合，即{（1，简单），（2，芳香）}：· （1，简单）是出现在P6和P11中的对，因此编码顶点6和11之间的隐藏边;· （2，aromatic）是出现在P5和P6中的一对，因此编码顶点5和6之间的隐藏边。图1中给出的标记图可以被认为是空的deco- rated标记图，即没有隐式边的标记的装饰标记图。在下文中，我们不区分标号图和它对应的空装饰标号图。现在正式描述隐藏和显示边缘的操作它们是修饰标号图集合中的内部变换定义2.3 [Hide-an-edge]设G=（V，E，lab）是L上的一个装饰标号图，c是L C的一个新标号，{u，v} ∈E是G的一条边，lab（{u，v}）=lu v. 由y给出了G1=（V，E1，lab1）的解(i)E1=E− {{u，v}}，简单2简单 芳香族的4简单1C3芳族C5C9芳香双链C8C6芳香族CO简单10个C11 （1，简单）（1，简单）CC118O. Bournez等人/理论计算机科学电子笔记147（2006）113(ii) lab1（e）=lab（e），n∈E1，(iii) lab1（w）=lab（w），对w∈V，wu，w/=v，(iv) lab1（w）=（lw，Pw<${（c，lu v）}）如果（w=u或w=v）且lab（w）=（lw，Pw）.通过删除图G的边{u，v}并将该边编码在图的标号中，从G获得边{u，v}隐藏在图G1中.定义2.4 [隐藏边]设G=（V，E，lab）是L上的一个装饰标号图。修饰标号图G的隐藏边的集合H如下：H={{u，v}|<$（c，luv）∈ P u<$Pv}.例2.5在图5中，第一个修饰的标记图中有一条隐藏边，第二个标记图中有两条隐藏边相反，隐藏的边缘可以在必要时显露定义2. 6.设G1=（V，E1，lab1）b是L，u，v∈V上的一个可调整的l-带标号图，使得{u，v} ∈H.修饰标记图G=（V，E，lab）由下式给出：(i)E=E1<${{u，v}}，(ii) lab（{{u，v}}）=luv，(iii) lab（e）=lab1（e），n∈E1，(iv) lab（w）=lab1（w），对w∈V，w/=u，w/=v，(v) lab（u）=（lu，Pu），lab（v）=（lv，Pv），其中lab1（u）=（lu，Pu）{（c，luv）}，并且lab1（v）=（lv，Pv<${（c，luv）}是从G1通过添加边{{u，v}}到图G，并使该边在G1的标记中编码显式获得的。在下文中，我们只考虑通过切割边从（可能是循环的）标记图获得的装饰标记图。这个类使用以下格式良好的概念来描述。定义2.7[良型装饰标号图]如果重复应用reveal-an-edge操作导致空的装饰标号图，则L上的装饰标号图G=（V，E，lab）是良型装饰标号图例2.8图5中给出的装饰标记图是良构的装饰标记图。从现在开始，我们假设所有的装饰标号图都是良构的，除非另有说明。O. Bournez等人/理论计算机科学电子笔记147（2006）113119设G1=（V，E1，lab1）是L上的一个W形的带装饰的带标记图，G=（V，E，lab）是通过反复应用显露边运算而得到的（空装饰的）带标记图. 将一个良构的修饰标记图G1变换成一个标记图G的函数用decoGraph2graph表示：decoGraph2graph（G1）= G.decoGraph2graph函数是满射的，但不是内射的。通过重复应用显示隐藏边和移除空装饰来产生相同的标记图的固定顶点集上的两个deco-rated标记图可以被认为对于以下关系是等价的定义2.9【等价的装饰标号图】设G1和G2是GV（L）的两个装饰标号图。如果decoGraph 2graph（G1）=decoGraph2graph（G2），则G1和G2等价，记为G1 <$G2.我们用[G1]表示G1的等价类.2.2装饰标记森林前面的正式定义的目的是描述如何通过隐藏边和保持相同数量的连通分量来将循环图转换为树或森林。定义2.10[装饰标记森林]L上的装饰标记图G=（V，E，lab）称为装饰标记森林，如果底层图（V，E）是森林，即如果它没有圈。它是一个装饰标记树，如果底层图（V，E）是一棵树，即。它是连接的并且没有循环。例2.11图5所示的装饰标号图是一棵装饰标号树。定义2.12[forest2graph]设F是上的装饰标记森林L.在这种特殊情况下，函数decoGraph2graph（显示所有隐藏的边）表示为forest2graph。如果定义2.3中给出的操作hide-an-edge被重复应用，直到所有的边都被隐藏，我们得到类似于邻接表的东西[8]。作为顶点的多重集，这也对应于[19]中提出的图的表示。在这里，我们不执行此操作，直到所有的边缘都被隐藏，但只有直到没有循环剩余。定义2.13[graph2forest]设G=（V，E，lab）是L上的标号图，H是边的子集。将G变换为解码标记森林F的操作，从集合H∈E隐藏边缘，表示为：120O. Bournez等人/理论计算机科学电子笔记147（2006）113graph2forest：F∈ graph2forest（G，H）.让我们注意到graph2forest是一个关系，但不是一个函数。然而，如果集合H是有序的，如果隐式边的标签集合LC是固定的，并且如果操作hide-an-edge以给定的顺序应用于H，那么graph2forest就变成了一个函数。我们还注意到，F的支撑图，即修饰标记森林，是图G的生成森林。下图总结了不同的转换：选项卡页面上创建森林2图图2森林（空修饰）标号图FJ装饰标记林请注意，一个（连通）图可以用指数数量的装饰标记树或森林来表示：让我们假设（连通）图有m条边，并且不超过κ条边被隐藏，其中κ是圈数（隐藏得到树或森林的最小边数 那么这个图最多对应于m！/（κ！（m − κ）！） 为O（2m）装饰标记树或森林：我们需要选择κ隐藏边在m个边缘之间。 注意，如果我们考虑连通图的圈数κ受某个常数κ 0的限制，那么这个修饰标记树的个数在m中是多项式的（在O（mκ0）中）.hide-an-edge运算给出了修饰标记森林上的偏序：如果F2是通过隐藏一条边从F1得到的，则F1 F2（和H1 <$H2）。<对偶地，F1是从F2通过显示边缘得到的.利用这个关系，我们定义了最小隐藏森林的概念，对应于通过在图G中隐藏最小数量的边而获得的森林F，以便在F中获得与G中相同数量的连通分量（这相当于具有最大数量的暴露边）。定义2.14[Minimally Hidden Forest]设G=（V，E，lab）是一个标号图，F∈graph2forest（G，H）。F是G的极小隐藏森林，如果F是关于修饰标记森林由hide-an-edge操作给出。F不是G的极小隐森林，如果存在一个隐藏边，可以被揭示，以得到一个装饰的标记图，它仍然是一个森林（没有形成圈）：换句话说，<$F1：F11。考虑t1作为修饰项编码T1，其中t1中的根是规则RJ中的t的根，并且具有与t中相同的隐藏边集。我们有terms2forest（ t1+t2+···+tk）=F1，t1+t2+···+tk→v1+v2+···+vp+t2+··+tk使用RJ，terms2forest（v1+v2+··+vp+t2+···+tk）=F2.Q给定t1+t2+··+tk，其中项2forest（t1+t2+··+tk）=F1，人们可能需要找到一个合适的等价视觉 u1+u2+··+uk，规则 RJ可以应用于这给出了下图：，1r：fl→frF、术语2森林t1+t2+ ···+tku1+u2+···+ukRJs1+s2+·· ·+slJ在该变换中，重写规则r由唯一规则RJ实现。然而，要应用规则RJ，必须在AllV（ t1+t2+···+tk）中找到某个 u1+u2+··+uk，它可能包含2个O（m）元素，其中m是F1的边数（如果F1的圈数有界，则是多项式数如果我们有一些关于术语的重写规则，这些规则将森林的任何术语表示映射到它的视图中，表示为codevision，并且一些规则实现森林的术语表示的合并转换，表示为codemerge，我们得到下面的图表：G1gl→grG2，g，，、森林2图、森林2图，f，o，r，est2graph、、、术语2前F1，最小值、术语2森林fl→frF、术语2森林›→合并F2，min、术语2森林t1+···+tk视觉u1+···+ukRJs1+·· ·+slJ►合并w1+···+wn合并操作可以使用经典算法（参见[8]）在多项式时间内实现。此外，从上面的讨论中，可将一个项与2个O（m）项以+的结合性和交换性为模相关联。因此，从t1+···+tk到w1+···+wn的一个模拟步骤可能需要测试规则rJ的左侧与最坏情况下的2个O（m）这必须通过重写图意味着解决图同构问题，其中没有多项式界是已知的。在我们的背景下，从我们在GasEl系统中的经验来看，我们远远没有达到这种最坏情况的分析。这是由于各种事实：132O. Bournez等人/理论计算机科学电子笔记147（2006）113• 关联匹配和交换匹配一般是指数级的，但可以由当前的AC编译器有效地执行。• 此外，由于重写规则rj的结构，重写规则 RJ仅应用于项u1+···+uk之上，这提高了AC匹配问题求解的效率• 根据我们的经验，在我们与化学有关的应用中所涉及的规则仅意味着具有较少周期的分子。因此，在实践中，我们的方法对化学规则相当好• 从某种意义上说，如果涉及的周期数很低，我们就接近项重写。使用邻接列表的实现不会直接受益于此属性。5执行GasEl系统的实现依赖于本文提出的概念。它是用ELAN语言设计的，ELAN语言特别为关联和交换理论提供了一个高效的重写引擎[20]。在文献