树自动机的非确定性规模缩减方法

理论计算机科学电子笔记251（2009）27-48www.elsevier.com/locate/entcs一种基于统一（双）模拟的树自动机帕罗什河阿卜杜拉一世乌普萨拉大学信息技术系瑞典乌普萨拉Luka'sHol'sH5，2捷克布尔诺理工大学信息技术学院Lisa Kaati3乌普萨拉大学信息技术系瑞典乌普萨拉Tom'avisVojnar5，4捷克布尔诺理工大学信息技术学院摘要在本文中，我们解决的问题，减少非确定性（自下而上）树自动机的大小。 我们提出了一个统一的框架，允许结合各种向上和向下互模拟和模拟关系，以获得一个语言保持组合关系适合于减少树自动机，而不需要确定它们。该框架概括和扩展了几个以前的作品，并提供了广泛的不同关系，产生了一个精细的选择之间的可能性减少的数量和计算需求。此外，我们还提供了一种显著改进的计算各种组合（双）模拟关系的方法。我们从理论上以及通过一系列的实验分析所考虑的关系的属性。保留字：树自动机，互模拟，模拟，组合关系，规模缩减1571-0661 © 2009 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2009.08.02628P.A. Abdulla等人/理论计算机科学电子笔记251（2009）271介绍有限树自动机是词自动机的自然推广。 由于树（或术语）出现在计算机科学和工程的许多领域，树自动化的应用非常广泛，包括例如XML操作、自然语言处理或形式验证中的应用。在大多数这些应用中，处理尽可能小的自动机是非常可取的。为了减小一个树自动机的规模，人们总是可以尝试确定并最小化它，然而，确定可能导致规模的指数爆炸，甚至最小确定自动机仍然可能大于原始的非确定自动机。此外，即使最小确定自动机真的很小，由于非常昂贵的确定步骤，也可能无法计算它。另一种方法来减少一个给定的（非确定性）树自动机是确定一个合适的，语言保持等价关系，其状态和collapse这些状态是平等的，根据这种关系。在词自动机的情况下，这种关系的良好候选人是各种互模拟和模拟等效。特别是，所谓的前向和后向互模拟和模拟等价是众所周知的，是有用的，当减少字自动机的大小。在本文中，我们处理他们的树自动机扩展-所谓的向下和向上互模拟和模拟等价。向下（双）模拟，直接推广适当的向后（双）模拟从词自动机（自底向上）树自动机，是兼容的语言包含前序。也就是说，如果状态r向下（bi-）模拟状态q，则q接受的语言是r接受的语言的子集。因此，这些关系是减少树自动机规模的自然选择。向上（双向）模拟与语言包含前序不兼容。相反，它们与包含所谓的上下文语言兼容，其中状态q的上下文产生于在q处接受的树，通过用“洞”替换其一些叶子然而，可以证明，当我们将自己限制在与自动机的最终状态集兼容的向上（双向）模拟时，向下和向上（双向）模拟可以以这样一种方式结合起来，即它们产生语言兼容的等价。在最坏的情况下，组合关系与适当的向下（双向）模拟等价一样粗糙，但根据我们的实际实验，它通常会导致自动机的显著更好的约简。Trebisimul inscane mmintint imeO（r2mlogn），其中r是输入符号的最大秩，m是转换表的大小，并且 n是给定树自动机的状态数[3，9，1]。然而，减少1电子邮件：parosh@it.uu.se2 电子邮件地址：holik@fit.vutbr.cz3 电子邮件：lisa. it.uu.se4电子邮件地址：vojnar@fit.vutbr.cz5这项工作得到了捷克科学基金会（项目102/07/0322、102/09/H 042）和捷克教育、体育和青年部（MSM0021630528项目）的支持。P.A. Abdulla等人/理论计算机科学电子笔记251（2009）2729通过使用互模拟获得的结果通常是有限的。树模拟比互模拟弱，因此不能得到更好的约简。另一方面，尽管最近为计算它们而设计的算法取得了进展[2]，但它们的计算成本要高得多计算模拟前序的时间复杂度这是一个复杂度为O（lr=2m2）的算法，其代价是所有相的大小。在本文中，我们提出了一个新的概念，向上模拟和bisimulation- tions参数化的诱导向下模拟或互模拟（在任何可能的组合）。此外，我们引入了一个新的操作符-称为一个削弱- ING组合操作符-结合这种向上和向下的模拟和互模拟关系的树自动机。通过这种方式，我们获得了一个统一的树（双）模拟框架，它带来了几个显著的优点。首先，所提出的框架允许人们不仅组合如在先前的工作[2，1]中考虑的最大向下和向上模拟或最大向下和向上互模拟，而且组合任何诱导向下模拟（即，也是向下互模拟，例如，恒等关系）与任何诱导的向上模拟（即，也是互模拟或同一性）。这样，我们统一地解释了文献[9，2，1]中的几个结果，并得到了几个新的适用于约简树自动机的组合关系。这种关系的使用以各种方式混合了模拟和双模拟的优点，允许用户微调可能的减少与其成本之间的比率我们仔细分析了各种考虑关系的相互关系。我们建立了一定的偏序之间的还原能力，但我们也表明，他们中的许多人有一个无与伦比的还原能力。此外，与以前的工作相比，新提出的组合算子还带来了一种显着改进的计算组合（双）模拟关系的方法。在组合之前，通过随机寻找满足要求的组合关系来完成组合。新提出的组合算子计算一个最大的组合关系，我们证明是唯一的。我们为此目的提出的算法是非常简单的，运行时间为O（n3）（或者，事实上，甚至在一个稍微好一点的时间）。在实验中，最大组合关系的使用本身就比以前使用的随机组合算法给出了更好的结果。让我们也注意到，我们提出的组合（双）模拟关系的概念是适用于词自动机作为树自动机的特殊情况为了实验性地检查我们的框架所提供的广泛的关系，我们实现了一个原型工具，在该工具中，我们基于所谓的正则树模型检查和绝对正则树模型检查[6，4，7，5]，对来自无限状态系统的形式验证领域的树自动机进行了我们的实验结果证实，我们已经获得了广泛的算法减少树自动机，在其计算复杂性和减少能力的差异。30P.A. Abdulla等人/理论计算机科学电子笔记251（2009）27相关工作。文献中已经提出了几种算法，用于减少非确定性树自动机的大小第一次尝试是在[3]中完成的，其中提出了一种受Paige和Tarjan [11]的分区细化算法启发的算法在[9]中，提出了两种不同类型的互模拟-向后和向前互模拟。这些互模拟原来是在我们的框架中产生的关系的特殊情况在[2]中讨论了计算树自动机上的模拟等价的有效算法，并提出了组合模拟关系。在[1]中，将[2]中的思想推广到互模拟。在本文中，我们结合这些以前的工作在一个框架，使我们能够解释他们在一个统一的方式，而且，获得多个新的关系适用于减少树自动机。所获得的框架允许用户混合模拟和互模拟方法的优势，在一定程度上适合于一个给定的场景。我们用来计算我们所处理的向上和向下关系的方法受到[2]和[1]的方法的启发。然而，我们通过新提出的弱化组合算子提供了一种新的和显著改进的组合这些关系的方法。纸的计划论文的其余部分组织如下。我们从第二节的一些细节开始。在第3节中，我们介绍了向下（双）模拟的概念，并提出了参数化向上（双）模拟的概念。随后，在第4节中，我们提出了弱化组合算子及其用于获得适合于约简树自动机的组合关系。接下来，第5节分析了最有趣的可能组合关系的性质。第6节概述了可用于计算向下和向上（双向）模拟的算法在第7节中，我们给出了一个实验评估使用所获得的关系谱约简树自动机。最后，我们总结了论文，并在第8节讨论了未来可能的工作。2预赛在这一节中，我们将介绍一些关于关系、树和树自动机的概念。树排序字母表是一组符号和一个函数#：→N。对于f∈F，值#（f）称为f的秩。对于任何n≥0，我们用n表示从n开始的秩为n的所有符号的集合。设表示空序列。排序字母表上的树t是满足以下条件的部分映射t：N→N• dom（t）是N的有限的预闭子集，并且P.A. Abdulla等人/理论计算机科学电子笔记251（2009）2731π• 对于每个p∈dom（t），如果#（t（p））= n≥ 0，则{i|pi∈dom（t）}={1，. ，n}。每个序列p∈dom（t）称为t的一个节点。对于一个节点p，我们定义第ip的子树是节点pi，p的第i个子树是树tJ，tJ（pJ）=t（pipJ），对所有pJ∈N<$. t的叶子是没有任何子节点的节点p，即，不存在i∈N且pi∈dom（t）。我们用T（）表示字母表上所有树的集合树自动机一个（有限的，非确定的，自下而上的）树自动机（以下简称TA）是一个四元组A=（Q，F， Δ，F），其中Q是一个有限的状态集，F是一个最终状态集，F是一个排序字母表，Δ是一个转换规则集。 每个转换规则都是形式为（（q1，.，qn），f，q），其中q1，.，qn，q ∈Q，f∈n，且#（f）=n.我们使用（q，...，q）-f → q来表示（（q，.，q），f，q）∈1n1nΔ。在n= 0的特殊情况下，我们谈论所谓的叶规则，我们有时将其表示为−f→q。我们用Lhs（A）表示左规则的侧面，即， 形式为（q，.，q），其中（q，.，q）−f→ q1n1n为 了 我 和 我 的 孩 子 。最后，我们证明了（A） 的最小值n∈N 满足对每个m∈N有atn≥m，其中（q1，...，qm）∈Lhs（A），其中qi∈Q，1 ≤i≤ m.为了避免混淆，我们省略了A的提法。A在树t∈T（n）上的游程是一个映射π：dom（t）→Q，使得对于每个结点p∈dom（t），其中q=π（p），如果qi=π（pi），其中1≤i≤n，则Δ有一个规则（q ，...，q）t（p）π q表示π是A在t上的游程，使得1n−→q。我们写t=π（π）=q。 我们用t=<$q表示对于某个游程π，t=<$q。的语言astateqisdefineedyL（q） ={t|t=q}，其中A的语言由L（A）=q∈FL（q）.一个环境是一个形式为（（q1，.，qi−1，Q，qi+1，. ，qn），f，q）是通过从规则（（q1，..，qi-1，qi，qi+1，. ，qn），f，q），并用一个特殊符号Q/∈Q（以下称为洞对于迁移规则，我们写（q1，...，Q，.，qn）−f→q，如果（（q1，.，qi-1，qi，qi+1，.，qn），f，q）∈Δ，qi∈Q。 有时，我们也把环境写成（q，.，Q，.，q）−f→q 到1i n强调孔在位置i处。我们表示所有环境的集合，A由Env（A）表示，如果没有混淆，我们将删除对A的引用关系对于一个定义在集合Q上的等价关系，我们称每个等价类都是一个块，并使用Q/A来表示块的集合。对于一个预序P，我们将把包含在P中的最大等价记为P。商树自动机。减少自动机规模的思想是在其状态上识别合适的等价关系，然后折叠形成等价的状态集32P.A. Abdulla等人/理论计算机科学电子笔记251（2009）27班考虑TAA =（Q，Δ，F）和Q上的等价关系Δ. 的从A和F导出的商树自动机是A=（Q，F，Δ，F），其中：•Q是在k中的块的集合。换句话说，我们将属于同一块的所有状态折叠成商自动机的一个状态。• （B，.，B）−f→B i（q，.，q）−f→q，对于某个q ∈B，.，q∈B，q∈B。1n1n1 1n n也就是说，在商自动机i中存在转换，并且在原始TA中的对应块中的状态之间存在转换。• Fntainsa blockB iBF/=。实际上，一个区块是一个正在接受的状态。3树自动机的我们现在提出向下（双向）模拟的定义，随后，我们提出了一个由向下模拟参数化的向上（双向）模拟的概念，我们将用作向上（双向）模拟的参数的向下模拟称为诱导关系，并且所获得的向上（双向）模拟将被称为诱导关系。在下一节中，我们将展示如何将一对诱导关系和诱导关系组合成一个新的等价关系，适用请注意，诱导关系因此以两种不同的方式使用：作为向上（双向）模拟的参数和作为组合关系的组成部分。通过考虑各种诱导关系，我们得到了一系列在计算复杂度和粗糙度方面不同的组合关系（通常比诱导关系好，但绝不会比诱导关系差3.1向下（双向）模拟对于树自动机A =（Q，Δ，F），向下模拟D是Q上的二元关系，使得如果qDr和（q1，.，qn）−f→q，则（r1，.，rn）−f→ r，其中qiDri对于每个i：1≤i≤n。向下互模拟D是Q上的二元关系如果qDr，则（q，.，q）−f→q当且仅当（r，.，r）−f→r，其中q Dr1N对于每个i：1≤i≤n。1n i i下面的两个引理陈述了向下（双向）模拟的一些基本性质引理3.1 A上所有向下模拟的集合在自反和传递闭包下以及在并下是闭的。证据联合：给定两个向下模拟D1和D2，我们想证明D=D1<$D2也是向下模拟。设对某个q，r∈Q，有qD1r或qD2r.在不失一般性的情况下，假设qD1r。然后从向下模拟的定义，无论何时（q1，. ，qn）−f→ q，则存在一个规则（r，.，r）−f→r，其中q D r对所有i：1 ≤i≤n。 为DQ博士给Q博士 为所有1ni1 i1ii位置i，D满足向下模拟的定义。P.A. Abdulla等人/理论计算机科学电子笔记251（2009）2733自相似闭包：从向下模拟的定义可以看出，恒等式是向下模拟。因此，恒等式和任何向下模拟的联合都是向下模拟。传递闭包：设D是向下模拟，设DT是它的传递闭包结束 设q1DTqm和（q1，. ，q1）−f→ q1. 从q1DTqm，我们得到1N是状态q1，.，qm，使得q1Dq2D. Dqm. 从定义上看，向下模拟，也有规则（q1，. ，q1）−f→ q1，. ，（qm，. ，qm）−f→1n1nqm加上q1D... Dqm和q1D ... Dqm对所有i：1 ≤i≤n。 因为，T是我我D的传递闭包，得到了对所有i：1≤i≤n，q1DTqm. 我们已经证明我我DT满足向下模拟的定义。Q引理3.2 A上所有向下互模拟的集合是A上所有向下模拟的集合的子集，并且它在对称、自反和传递闭包下以及在并下是封闭的。证据每个向下互模拟也是向下模拟的事实直接从这些关系的定义中得出。在并、自反性和传递性下的封闭性可以像向下模拟的情况一样被类比地证明。剩下的就是对称下的封闭设D为向下互模拟，设DS=D<$D−1为其对称闭包。证明D−1是向下互模拟是足够的，因为从并下的闭包来看，DS也是向下互模拟。设qD−1r. 然后，从rDq，我们有（r1，.，rn）−f→r当且仅当（q，.，q）−f→q，其中rDq对于所有i：1≤i≤n。 因为rDq等于1n i iqD−1r，我们可以写为（q，.，q）−f→q i（r，...，r）−f→r，其中q D−1r为1n1n i i所有i：1≤i≤n。我们直接看到D−1符合向下互模拟的定义。Q引理3.1和引理3.2意味着对于一个给定的树自动机，存在唯一的最大向下互模拟，它是一个等价，也存在唯一的最大向下互模拟，它是一个预序。我们注意到向下互模拟的概念对应于[9]中的向后互模拟的概念。任何向下互模拟都是向下模拟，这一明显的事实使我们能够简化一些进一步的推理，只考虑向下模拟，并将互模拟作为其特例处理。3.2诱导向上模拟给定树自动机A=（Q，λ， Δ，F）和A上的诱导向下模拟预序D，由D诱导的向上模拟U是Q上的二元关系，使得如果qUr，则(i) 如果（q1，.，qn）−f→QJ，其中qi= q，1 ≤i≤n，则（r1，.，rn）−f→rJ，其中ri=r，qJUrJ，且qjDrj，对于每个j：1≤j(ii) q∈F =r∈F.i≤n;34P.A. Abdulla等人/理论计算机科学电子笔记251（2009）27下面的引理包含了向上模拟的基本性质。注意，这也意味着对于任何诱导的向下模拟前序D，总是存在唯一的由D诱导的最大向上模拟，这是一个前序。引理3.3给定A上的一个向下模拟预序D，由D诱导的所有向上模拟的集合在自反传递闭包和并闭包下是闭的。证据并集：给定由D诱导的两个向上模拟U1和U2，我们想证明U = U1<$U2也是由D诱导的向上模拟。设qUr对某个q，r∈Q，则qU1r或qU2r. 在不失一般性的情况下，假设qU1r。然后，根据向上模拟的定义，每当（q1，. ，qn）−f→ qJ，其中qi= q，则存在规则（r1，. ，rn）−f→ rJ其中qJU1rJ，qJ∈ F =<$rJ∈ F，且qjDrj对于所有j：1≤j/ =i≤n。当U1U给出qJUrJ时，U满足定义D.自反闭包：从定义中可以看出，恒等式是D对任何向下模拟前序D诱导的向上模拟。因此，从并下闭包出发，恒等式与D诱导的任何向上模拟的并是D诱导的向上模拟。传递闭包：设U是由D诱导的向上模拟，UT是它的传递闭包。 设q1UTqm和（q1，.，q1）−f→r1，其中q1 = q1。1ni从q1UTqm，我们有状态q1，.，qm，使得q1Uq2U. 乌克山因此，也有规则（q1，.，q1）−f→r1，.，（qm，.，qm）−f→rm，其中1n1nq1 = q1，.，qm= qm，r1U. Urm，r1∈F= ⇒...=<$rm∈F，且q1D. Dqmii i j j对于所有j：1≤j/ =i≤n。因此，根据UT的定义，我们有r1UTrm，根据=的传递性，我们有r1∈F=rm∈F，根据对于所有j：1≤j/ =i≤n，我们有q1Dqm。我曾以为，这是一个奇迹。J J定义了由D.Q3.3诱导向上互模拟设A=（Q，Q， Δ，F）是树自动机，D是A上的向下模拟预序. 由D诱导的A上的向上互模拟U是Q上的二元关系，使得如果qUr，则(i) （q，.，q）−f→qJ，其中q = q，1 ≤i≤n，当且仅当（r，.，r）−f→rJ，其中1n i1nri=r，qJUrJ，且qj<$Drj，对于每个j：1≤j(ii) q∈Fr∈F.i≤n;对于向上互模拟，证明向上互模拟的基本性质并不难.注意，下面的引理意味着对于任何向下模拟预序D，存在唯一的由D诱导的最大向上互模拟，这是等价的。同样清楚的是，由D诱导的任何向上互模拟也是由D诱导的向上模拟。这将使我们能够证明向上模拟的主要结果，并将互模拟作为特例。P.A. Abdulla等人/理论计算机科学电子笔记251（2009）2735引理3.4给定A上的向下模拟预序D，由D诱导的所有向上互模拟的集合是由D诱导的所有向上模拟的集合的子集，并且它在对称、自反、传递闭包和并闭包下是封闭的。证据事实上，每个向上的互模拟由一个向下的模拟引起，D也是由D直接从这些关系的定义导出的向上模拟在并、自反性和传递性下的封闭性可以像向上模拟的情况一样剩下的就是对称下的封闭设U是由向下模拟引起的向上互模拟前序D，设US=U<$U−1为其对称闭包。证明U−1是由D诱导的向上互模拟是足够的，因为从并下的闭包来看，US也是由D设qU−1r. 然后，从rUq，我们有（r，.，r）−f→rJ，其中r = r，如果1n i且仅当（q，.，q）−f→qJ，其中q = q，rJUqJ，且r <$q 对于所有j：1≤1n i j D jji≤n。 由于D是等价的，并且由于rJUqJ等价于qJU−1rJ，我们可以write（q，.，q）−f→qJ，其中q = q i <$（r，.，r）−f→rJ，其中r = r，qJU−1rJ，并且1n i1n iqj<$Drj对于所有j：1≤ji≤ n。我们直接看到U-1符合定义D.Q让我们注意到，由恒等关系导出的向上互模拟的概念对应于[9]中的向前互模拟的概念约简树自动机的4种向上模拟等价和向上互模拟不能单独用于约简树自动机，因为它们不保留它们的语言。为了避免这个问题，我们必须考虑诱导关系，并将其与诱导向上（双向）模拟结合起来-正如我们在前一节中已经提到的，诱导关系因此以两种不同的方式使用作为本文的主要贡献之一，我们现在将定义一个新的组合算子-我们称之为弱化组合算子-在诱导的向下模拟和诱导的向上模拟上。与以前的作品[2，1]中使用的算子不同，新算子允许我们结合任何诱导向下模拟（即，也是互模拟或恒等式）与任何引起的向上模拟（互模拟、恒等式）一起，从而使我们获得所得到的关系的宽范围。此外，在以前的工作中，我们随机计算一个关系的可能的语言保持组合关系的集合。在这里，我们首先证明了对于给定的向上模拟及其诱导的向下模拟，总是存在唯一的 在第6节中，我们提供了一个计算这个极大前序的简单算法。从实际的角度来看，在某些情况下，使用最大前序而不是随机前序这对约简自动机的规模有很大的影响，我们的实际实验证明了这一点。36P.A. Abdulla等人/理论计算机科学电子笔记251（2009）274.1一个弱组合算子在任意前序上，我们定义了通常用于诱导向下模拟和诱导向上模拟的弱化组合算子：给定集合Q上的两个前序H和S，对于x，y∈Q，x（H<$S）yi <$（i）x（H<$S）y和（ii）<$z∈Q：yHz=Hx（HS）z.6 直觉上，在HS中的一对e=（x，y）∈Q×Q在将其添加到前序H之后也将出现在HSi中，存在通过在HS中的Q的其他元素对来补充所获得的关系H{e}以确保传递性并且以这种方式再次获得前序的可能性。引理4.1对任意集合Q和任意预序H，S <$Q × Q，H <$S是唯一的极大预序使得H<$H <$S <$H <$S。证据设W=HS，C=HS。[7]请记住W、H、S和C，H和S是自反的和传递的。我们首先证明了对于任意x，y，z∈Q的一些辅助事实，使我们能够推导出我们正在处理的关系的某些元素的存在性(I) xCy=xHwSy，对于某个w∈Q，它直接由C的定义得出。(II) xHyCz=xCz。由yCz和（I），我们有yHwSz，其中w∈Q。从xHyHw，我们有xHw。根据xHwSz和C的定义，我们得到xCz。(III) xWyHz=xCz，直接从W的定义得出。(IV) xCySz=xCz。 从xCy和（I），我们有xHwSy，对于某些w∈Q。从wSySz我们有wSz了 从xHwSz和（II），我们有xCz。(V) xWyCz=xCz。 由yCz和（I），我们有yHwSz，其中w∈Q。 从xWyHw和（III），我们有xCw，它与（I）一起给出了对于某个v∈Q的xHvSw。从vSwSz，我们有vSz，因此vCz（作为SC），它与xHv和（II）一起得到xCz。现在，我们可以证明引理的主张。首先，我们要说的是， 为了做到这一点，假设xHy对于某个x，y∈Q。 我们将展示xWy。 作为HC，我们有xCy，它满足条件（i），从定义。为了满足条件（ii），我们必须证明对于任意z∈Q，这样的yHz，xCz成立。根据H的传递性和xHyHz，我们有xHz，这意味着当我们考虑H<$C时，xCz。因此，即使条件（ii）也满足了，我们从定义xx y得到xWy。 因此，我们证明了H？此外，事实上，WC是微不足道的，因为它是定义的一部分，- 是的现在我们将证明W是一个预序。我们首先用反证法证明：W是可传递的。设存在x，y，z∈Q使得xWyWz，但不6 这里，HS是关系的共同组成，即，<$x，y∈Q：x（H<$S）y Q：xHzSy。[7]为了在符号中更容易地定位，让我们注意到，我们使用W作为应用弱化组合算子的结果，C表示H和S的合成，H是一个前序，它在必须包含在W中的意义上是P.A. Abdulla等人/理论计算机科学电子笔记251（2009）2737我xWz。回想一下，W.从（I），我们有xHwSyHvSz，对于某个v，w∈Q。从xWyHv和（III），我们有xCv。从xCvSz和（IV），我们有xCz。从xCz的定义来看，xCz与非xWz一起意味着存在一个q∈Q使得xCzHq，但不是xCq。从yWzHq和（III），我们得到yCq。然后是xWyCq，而（V）给出xCq，这是一个矛盾。我们证明了关系W是传递的。表明W也是反射性的是直接的，因为我们已经知道H是反射性的。因此，我们证明了W是一个前序。最后，我们将证明W是包含在C中且包含H的唯一极大预序。 从H的定义可以很容易地看出，任何对（x，y）∈C\W都不能包含在任何前序P中，使得H<$P<$C作为没有关系P，使得H<$P<$C和（x，y）∈P可以传递。 因此，W包含可以是包含在C中并且包含H的前序的元素的所有对，并且因此，任何这样的前序P都是W的子集。因为我们已经证明W本身是一个预序，所以它必须是唯一的包含H且自身包含在C中的极大预序。Q引理4.1是一个关键结果，它允许我们定义适用于减少树自动机大小的组合前序和等价关系，如下所示。4.2约简树自动机的组合关系考虑一个树自动机A=（Q，，Δ，F），A上的一个向下模拟预序D，以及由D诱导的一个向上模拟U。 我们称关系W=D<$U−1为一个组合前序，而称关系W = D <$W为一个组合等价。正确使用在下面的定理4.6中说明了通过递归减少树自动机的大小的组合等价性，该定理4.6涉及A和A的语言。8在定理4.6的证明中，我们使用了上下文的概念。简而言之，上下文是一棵有“洞”而不是叶子的树。 形式上，我们考虑一个秩为0的特殊符号Q/∈N。一个在C上的上下文是一个在C上的树，对于所有的叶p∈c，我们有c（p）=Q。 对于具有叶子p1的上下文c，.，pn对于树T1，. ，tn，我们定义c [t1，. ，tn]是树t，其中• dom（t）= dom（c）{p1·pJ|pJ∈dom（t）} ···{pn·pJ|pJ∈dom（tn）}，• 对于每个p=pi·pJ，我们有t（p）=ti（pJ），并且• 对于每个p∈dom（c）\ {p1，.，pn}，我们有t（p）= c（p）。换句话说，c [t1，. ..，tk到c的孔。我们将运行的概念扩展到上下文。设c是一个上下文，其中叶子为p1，.，pn. A在c上的运行π从（q1，.，n）的定义类似于一个树上的运行，除了对一个叶子pi，我们有π（pi）=qi，1≤i≤n。换句我的意思是，我的意思是， 我们使用c[q， .. . ， q]=π<$q1N表示π是A在c上从（q1，.，qn）使得π（π）= q。符号c [q1，. ，qn]= n，q以类似于树上的运行的方式解释。[8]请注意，与向下模拟相反，组合前序不必细化语言包含前序，这是因为它们也强烈依赖于向上模拟，而向上模拟与语言包含前序不兼容。然而，定理4.6表明，当用于折叠自动机时，组合等价仍然保留整个自动机的语言。38P.A. Abdulla等人/理论计算机科学电子笔记251（2009）27引理4.2如果c [q1，.，qn] = n，q和qDr，则存在状态r1，.，rn，使得对于每个i，其中1 ≤ i ≤ n，qiDri，并且c [r1，.. ，rn]= nr.证据通过对C的高度的归纳。基本情况（其中c为空）是平凡的。我们考虑c至少包含一个节点的情况我们知道πc [q1，.，qn]=q，对于某个π。 设c（f）=f.此外，我们知道，是qJ，... ，qJ， 使得（qJ，.，qJ）fq，且π（i）=qJ对于每个i，其中1≤1m1M−→ii≤m。 换句话说，运行将根标记为q，并将子标记为根与qJ，.，qJ分别表示。 这意味着对于所有i：1≤i≤m，c[q1mπiJth我ni−1+1，. 其中ci是c的i子树，πi是π到ci，n0= 0，且nm=n。 由于qDr，我们知道有rJ，.，rJ1m使得（RJ，.，rJ）fr和qJ对于每个i，1≤i≤m。 由感应1m −→ii假设，可以得出，对于每个i，1 ≤i≤m，存在状态rni−1，.。，rnisuchthatfor reachj，ni−1+ 1≤j≤ni，qjDrjanddci[rni−1+ 1， . . ，rn]=rJ. Hence我我c [r1，.，rn]= nr.Q引理4.3如果c [q1，q2，. ，qn]=q且qiU ri，其中1 ≤ i ≤ n，则有状态r 1，.，ri−1，ri +1，.，rn，r，使得对于每个j，qjDrj：1 ≤j并且c [r1，.，rn] = nr.i≤n，qUr，证据 为了简化符号，我们假设（不失一般性）i =1.我们对c的结构使用归纳法。基本情况是微不足道的，因为上下文C由单个孔组成对于归纳步骤，我们假设c不是π只有一个洞。 假设c [q1，q2，...，qn]=q，对于某个游程π，q1U r1。设p是叶子p 1的父节点，标记为q1，设p1，.，pm是它的孩子。 设cp是c的以p为根的子树。 注意，对于所有i，2≤i≤m，ci[qnnπqJ，其中ci是以pi为根的c的子树，nn = 1，m =i−1+ 1，.，qi]=i1k，其中k≤n。设QJ=π（p），CJ为上下文c，子树有根atp， .. . ， pdeletted. 在这些文字中，dom（cJ） =dom（c）\m{ppJ|pJ∈N<$}，1mi=1iCJ（PJ）=c（PJ），如果PJ∈dom（CJ），且CJ（p）=Q. 观察到cJ [qJ，qk+1，.，qn]=q和（q1，qJ，...，qJ）−f→qJ对某个f。 以“向上”的2m模拟和前提q1U r1，它遵循有rJ，.，RJ，RJ，使得2mqjJ博士，.，qJDrJ，qJUrJ，以及（r1，rJ，.，rJ）−f→rJ。由于cJ小于c，2 2米2米归纳假设，有rk+1，... ，rn，r使得qk+1Drk+1，. ，qn博士n并且cJ [rJ，rk+1，.，rn] = nr. 对于每个i，2≤i≤m，我们有qJDrJ，因此通过我我引理4.2，存在状态rni−1+ 1，. ，rni使得对于每个j，ni−1 ≤ j ≤ ni，qJDrJ和ci [rn+1，.，rn]=rJ. 索赔立即跟进Qi−1jji ii对于一个状态r∈Q，一个状态集合B<$Q，以及一个关系R<$Q×Q，我们写BRq表示存在q∈B，其中qRr。引理4.4对于块B1，.，Bn，B∈Q∈W和上下文c，如果c [B1，.，Bn]=Bn，则存在状态r1，.，rn，r∈Q，其中B1Dr1，.，BnDrn，BUr，和c [r1，.，rn] = nr.证据这一主张是通过对c的结构的归纳来证明的。 在基本情况下，上下文c由单个孔组成。我们选择任何q∈B <$F，前提是P.A. Abdulla等人/理论计算机科学电子笔记251（2009）2739j+1nj+1nj+1nn1n一期+1一期+1一期+1一期+1B∈F/=B，且任意q∈B都是任意的。D.对D.的重视使我们受益匪浅。和联合对于诱导步骤，我们假设c不仅是单个空穴。 假设c[B， .. . ，B]=π<$B，对于π， LETP， .. . ， 请注意，1n1j共同的父母 设p是p 1的父节点，... ，pj. 注意B1= π（p1），. ，Bj= π（pj）.设BJ= π（p），并且设CJ是具有叶子p1，.，pj被删除。换句话说，dom（c，J）=dom（c）I {p，.，pj}，CJ（PJ）= c（PJ），如果PJ∈dom（CJ）\ {p，p1，.，pj}，并且cJ（p）= Q。 观察到cJ [BJ，Bj+1，.，Bn]=B. 由于cJ小于c，我们可以应用归纳假设，包括有v，q，J，.，qJ，qJ，使得BJDv，Bj+1DqJ，.，BnDqJ，BUqJ，j+1nj +1ncJ[v，qJ ，.，qJ] = qJ. 因此，有u∈BJ，qj+1∈Bj+1，. ，qn∈Bn，q∈B使得uDv，qUqJ，and qj+1DqJ，.，qnDqJ. 根据定义，有状态q∈B，...，qj∈B，且z∈BJ使得（q，...，q）−f→ zW11J1J对于一些F。由于DW和uDv，我们得到uW v。 由于u，z∈BJ，因此u<$Wz，因此zWu。从W的传递性，我们得到zWv。根据W的定义，有一个状态w使得zDw和vUw。根据定义，语言包含前序和前提zDw和（q1，. ，qj）−f→ z，则有国家r，.，r 关于Q博士，q Dr，和（r，.，r）−f→w. 根据引理4.3，1j1 1j1j前提vUw和CJ [v，QJ，.，qJ] = qJ，存在状态rj+1，. ，rn，和r，Jj+1博士j+1，.，qJDrn，qJUr，以及cJ [w，rj+1，.，rn] = nr. 最后，根据D和U，我们得到qj+1Drj+1，.，qnDrn，qUr. 因此，该主张成立。Q引理4.5如果t =<$B，则对于某个w，t =<$w，其中B为Uw。此外，如果B∈F<$W，则w也∈F。证据 假设t =πB为π。 令p，... ， p是T的叶子，让101nπ（pi）=Bi对于每个i：1≤i≤n。 设c是我们从t得到的上下文，我不想让你知道我是谁。 . ， p. Obs ervethatc[B， .. . ，B]=πB. Itfollowsfromom1n1n引理4.4存在状态r1，.，rn，r ∈ Q且q1 ∈ B1，.，qn∈Bn，q∈ Bsuc hth atq1Dr1， . . ，qnDrn，qUr，c[r1， . . ，rn]=r，anddifBF=/，tenr ∈F. 以A的定义，，则有qJ∈B1，.，qJ∈B，和DF， .. . . ，fsu c hth at−f→iqJforreachisu c hth at1≤i≤n.Wen1ni通过对i归纳证明，对于每个i，使得1≤i≤n，存在状态ui，.，ui，vi ，.，vi，wi使得qJDui，.，qJDui，qi+1Dvi，...，qnDvi，rUwi，1i i +1n11 iii+1n并且c [u]i，.，ui，vi ，.，vi] = nwi. i= 0的基本情况是平凡的。我们1i i +1n考虑诱导步骤。由于DW和qi+1Dvi+1，我们得到qi+1W vi+1。以来qi+1，qJ∈Bi+1，我们有qJWqi+1，因此qJWqi+1。 通过传递性，则qJWvi+1。 根据W的定义，有zi+1，使得J一期+1Dzi+1和vi+1U zi+1。 根据引理4.3，有z1，...，zi，zi+2，.，zn，z，uiDz1，.，uiDzi，vi Dzi+2，.，viDzn，wiUz，以及c [z1，.，zn] = πz. 通过transi-1i i +2n的性质和前提qjDui和uiDzj，我们有qjDzj，对于每个j：1≤j≤i。QQ40P.A. Abdulla等人/理论计算机科学电子笔记251（2009）27JJj j j j通过D的传递性和前提qjDvi和viDzj，我们对每个j：i+2≤j≤n。 定义ui+1=zj forj：1≤j≤i +1，vi+1=zj forj：i+2≤j≤n，J J且wi+1=z。P.A. Abdulla等人/理论计算机科学电子笔记251（2009）2741上面的归纳证明意味着c [un，. ，un]= n. 从定义1N如果在队列中执行预处理或导出，并且预处理为s-f→i，qJandqJDun，itfollowws我我我that−f→iunforeachi： 1≤i≤n. 这使得t=c[f， . . ，f]=n. Byi1nU的定义和当B∈F<$W时h∈FifB<$F/=n的条件满足所有i：1≤i≤n，其中i∈F.因此，在引理的主张中，假设取w=wn。Q定理4.6对任意树自动机A和每个组合预序W，L（A<$W）= L（A）.证据 包含L（A<$W）<$L（A）是平凡的。设t∈L（A<$W），即，t=0.01B，这是我的blockB whichereBbenefit. 4.我爱你5impliesthat=wsuc hth atw∈F. Q请注意，该定理还涵盖了仅使用向下模拟（和互模拟）的约简自动机的情况实际上，给定任何向下模拟D，恒等式总是由D诱导的向上模拟。然后，组合前序Did−1等于D，这意味着我们可以使用我的天 特别是，这涵盖了特殊情况下的正确性证明减少自动机使用向下互模拟和模拟等价在[2]中陈述推论4.7对于任意树自动机A和每个向下模拟预序D，L（A <$D）= L（A）。5组合关系的变式及其性质定理4.6和引理3.2和3.4允许我们考虑适合于约简树自动机的相当大的关系谱。我们现在研究这个谱中的关系的性质，当我们考虑恒等式、最大向下互模拟和最大