理论计算机科学电子笔记123（2005）195-208www.elsevier.com/locate/entcs确定树自动机Damiann Niwin'ski1，2华沙大学信息学研究所波兰Igor Walukiewicz3LaBRI法国波尔多第一大学摘要我们展示了一个算法，对于一个给定的确定性奇偶自动机在无限树上，计算最小的Mostowski（或拉宾）指数的非确定性自动机识别相同的L一个N G G的。这些文本说明了如果一个特定的数据结构。该算法是在验证非确定奇偶自动机的非空性的同时运行关键词：奇偶树自动机，Mostowski指数，可判定性。1介绍Finite–state对于涉及分支的1由欧洲研究培训网络GAMES提供支持第一作者还得到了波兰KBN赠款4 T11C 042 25的支持。2电子邮件地址：niwinski@mimuw.edu.pl3电子邮件地址：igw@labri.fr1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2004.05.015196 D. 尼温斯基岛《理论与计算科学》中的电子选择注123（2005）195-208时间，无限树上的自动机似乎是最佳选择。一个著名的范例将公式转换成一个自动机来识别它的树模型，从而将模型检测归结为树自动机的非空性问题时态公式的语义复杂性由自动机的结构，特别是接受条件反映。今天，最常见的变体是奇偶条件，它揭示了自动机，μ-演算和游戏之间的微妙对应关系[3]。奇偶自动机可以根据它们的Mostowski指数4（见图1）组织成层次结构低）。理解这个层次结构有助于我们理解trade–off众所周知，Mostowski指数的层次结构对于所有类型的树自动机都是严格的：确定性[18]，非确定性[10]，交替[1]（建立在[2，7]上），以及所谓的弱交替自动机[9]。然而，很少有人知道这些层次结构的有效性，也就是说，我们是否可以计算最小的Mostowski指数的树语言，从任何给定的自动机。如果输入自动机是决定性的，问题似乎更容易一些。确定性树语言形成了所有可识别树语言的一个适当但有效的子类（只要可能，我们可以在EX-PTIME [13]中确定自动机）。计算确定性层次中的层次可以通过简化为单词自动机的类似问题来完成[12]，参见下面的注释2.4。然而，请注意，非确定性层次结构中的确定性语言的级别可以任意小于确定性层次结构中的级别5。考虑到层次不确定性，Urban′ski[17]如何确定-cideifagivendeterministic Rabinautomatonisquivalento aBuéchiautomato- ton（possibly nondeterministic）.在本文中，我们扩展了这一结果，显示一个算法，对于一个给定的确定性奇偶自动机，计算其确切的Mostowski指数的不确定性层次。为了完成这幅图，请注意，确定性语言与交替层次的关系对于s上的每个区域都是等价的，因为它们都是co-Bu-hi，因此在交替层次的（0，为了证明我们的结果，我们改进了[12]中介绍的技术，在那里我们解决了树语言L的问题，其中L<$$>ω和''以CTL方式是unstodd的（即，如果ω -词沿着所有路径读取，4这里我们记为A。W. Mostowski首先考虑了[8]具有这种接受条件的树自动机。Mostowski指数完善了Rabin指数[14]。参见[16]各种自动机之间的关系。[5]这很容易从以下事实得出：所有可识别的单词语言都可以被Bu？chiautomata识别，而确定的ministich erarc hy是有限的[1 8]。D. 尼温斯基岛《理论与计算科学中的电子选择注》123（2005）195197t在L中）。在那里，计算树语言的非确定性索引将其简化为检测L的确定性（词）自动机中的一些特殊模式，我们称之为自动机。如果我们考虑路径的标签和方向，则可以非常类似地表征任意确定性树语言（例如，对于二叉树，路径的字母表变为{l，r}）。事实证明，树语言的非确定性索引再次依赖于路径语言的确定性自动机中某些类似于艾森豪威尔模式的存在。在一个确定性的词自动机中搜索树自动机可以在多项式时间内进行，然而，该构造还需要检测输入树自动机的非生产状态。 这相当于解决了非空性问题，这个问题的确切复杂性目前尚不清楚（由UP Escherco-UP [5]估计）。2基本概念自动机在有限的话。一个无限词上的有限非确定奇偶自动机由A = R，Q，q I，Tr，rankR给出，其中R是一个有限字母表，Q是一个初始状态为q I 的 有 限 状 态 集，Tr=Q×R×Q是一个转移集，rank：Q → ω是排序函数. 转换（q，a，p）通常写为q→ap.可以给出一个自动机A在无限词u∈<$ω上的运行，一作为一个无穷词ρ∈Qω使得ρ（0）=qI，且ρ（m）→ρ（m+ 1），当u（m）=a时，对于每个m ω。像往常一样，运行ρ接受如果lim supn→∞rank（ρ（n））是偶数;换句话说，无限次重复的最高秩是偶数。A所识别的语言L（A）由以下组成：有一个接受游程的词。在无限树上的自动机。用有限字母表赋值（标号）的满二叉树是映射t：{l，r}→，我们用T表示所有这样的树的集合。一个非确定性奇偶树自动机A=， Q，qI，Tr，rank就像一个关于词的自动机，除了TrQ××Q×Q。A在树t∈T <$$>上的一个游程本身是一个Qρ中的一条路径是可接受的，如果沿着它无限经常出现的最高秩更正式地说，对于路径P = p0p1. ∈ {l，r}ω，这意味着lim supn→∞rank（ρ（p0p1. pn）是偶数。一个运行是接受的，如果所有的198 D. 尼温斯基岛《理论与计算科学》中的电子选择注123（2005）195-208AA××一≤±± ≤≤一ω路径。 2、语言T（ ）由T中的那些树组成这是一个可以接受的运行。确定性自动机。一个关于词或关于树的自动机是确定性的，如果Tr分别是从Q到Q或从Q到Q的部分函数。众所周知，奇偶字自动机总是可以转换成确定性的，但树自动机一般不能。 我们称树语言为确定性语言，如果它由确定性奇偶自动机识别。将有利的是，识别如上所述的确定性树自动机A，其具有关于无限词的（确定性）自动机Aw= k×{l，r}，Q，qI，Trw，rankk，其中a，l a，rTrw={q→q1，q→q2：（q，a，q1，q2）∈Tr}树t：{l，r}n → n中的标号路是无穷序列（σ0p0），（σ1p1），（σ2p2）. . ，使得σ i∈ Σ i，pi ∈{l，r}，t（p0. p i−1）= σ i（所以特别是t（ε）= σ0）。应该清楚的是，如果Aw识别树t，则A识别t的所有标记路径。相反地，任何在n × {l，r}上的确定性字自动机都以明显的方式导出一个在n上的（确定性）树自动机。 在后面的文章中，我们通常不会在符号上区分A和w，但如果我们把它看作是一个词或树上的自动机，那么从上下文中就可以清楚地看出这一点。Mostowski指数奇偶自动机的Mostowski指数是对（min（rank（Q）），max（rank（Q）。 我们令（ι，κ）（iJ，kJ）如果iJi和κkJ或i = 0、iJ= 1和k+ 2 kJ。很容易看出，如果（i，κ）（iJ，κJ），那么任何索引为（i，κ）的自动机都可以通过秩的修改而转换为索引为（iJ，κJ）的等价自动机因此，对于任何类型的自动机，Mostowski索引都会导致在图1. （不失一般性，我们可以假设min（rank（Q））∈{0， 1};否则按rank（q）按比例缩小秩：=rank（q）−2。众所周知，图1的层次结构对于单词和树上的确定性自动机6[18]以及树上的非确定性自动机[10]（也适用于我们在这里不考虑的交替自动机）是严格的我们回顾[10，11]中的例子，因为它们与我们的证明有关。对于n∈N，设Mn是字母表{0，1，.，n}，使得对于t的任意路径u∈ {l，r}，limsupi→∞t（u i）是偶数。设Nn为[6]严格地说，瓦格纳[18]没有考虑树，但结果很容易从case这个词得出;它也可以从[10]得出，因为那里的例子是确定性的。D. 尼温斯基岛《理论与计算科学中的电子选择注》123（2005）195199......、、，，，、、（1、 2k + 2）、、、（0， 2k + 1），，、、、、、............、、，，，（1， 4）、、、、、、、、（0， 3）、、（1， 3）、、、、、、、、（0， 2）、、（1， 2）、、......、、、、（0， 1）、、（一、一），，，，，，，，，（0， 0）Fig. 1. Mostowski指数的层次结构。类似地，将“偶数”替换为“奇数”。我们称一个树语言L，ι-n-可行的，如果存在一个索引为（ι，n）的非确定性奇偶自动机识别L。否则，L是1-n-不可行的。定理2.1（[10，11]）对n∈N：（i）Mn是0-n-可行的但1-（n + 1）-不可行的，（ii）Nn是1-（n + 1）-可行的但0-n-不可行的.花对于一个整数k，在一个确定的词自动机A中的k -循环是一条路径v1，. ，v j= v1，使得max {rank（v i）：i= 1，.，j}=k。给定整数m≤n，一个状态q∈Q是A中的m-n-幂乘子，如果对每个k = m，. ，n，则在A的图中存在包含q的k-环。我们在[12]中引入了这个概念，以及自动机上的秩提升操作，↑i（对于i∈N），它不改变状态和转移。自动机，但是对于某些状态，可以将排名移动到小于i（最大到i+ 1）。这里我们不需要这个操作的细节，所以我们只总结要使用的结果。、、、200 D. 尼温斯基岛《理论与计算科学》中的电子选择注123（2005）195-208A↑一≤ A↑↑-A联系我们→→2引理2.2（[12]）对于确定性词自动机A，设B=A ↑0↑1... ↑i. 则L（B）= L（A），并且如果状态q在则q是B中的m-i-幂。我们将使用这个引理的下列推论。引理2.3如果n大于的状态的所有秩，则在的任何强连通分量（SCC）中的最大秩01...n为n或 n+1。证据根据i的性质，它最大可以是n + 1。现在，如果状态q具有rank（q）=in01.那么根据前面的引理，它位于某个n-循环上，这当然包含在SCC中。 Q注2.4在[12]中，我们还展示了如何通过分析词自动机中的谓词来确定词自动机的决定性Mostowski指数。↑-modified automaton。连同前面提到的确定性树自动机和标记路径的词自动机之间的对应关系，这意味着确定性树语言在确定性层次结构中的级别的过程。正如我们也展示了[13]如何在可能的情况下（在EXPTIME范围内）将非确定性树自动机转换为确定性树自动机，确定性层次的情况可以被认为是解决的。3禁忌的权力模式现在，对于每个Mostowski指数（i，n），我们将定义一个类似于Mostowski的模式。 P（i，n），这是一族子图，其可以出现在n，r上的确定性字自动机中。回想一下，在上一节中，这样的自动机对应于一个在环上的树自动机。考虑索引（1，n）和（0，n1）是对偶的，其思想是表明如果包含P（i，n）模式，则T（A）不能被具有索引对偶于（i，n）的非确定性树自动机识别这些模式将以规则的方式从P（0， 2）和P（1， 3）开始构造，但基本情况有些不同。我们将使用字母a，b，c，. 为国家。 设a~b为 路径a = v1，.，v j= b。(We总是假设j>1，i. 例如， 这条路是通的。我们会写的b如果而且这是一个k路径，即， max {rank（vi）：i = 1，.，j}= k。 因此，a~ka是k-loop。我们有两条路径a=v1， . . . ，v，j=b，并且a=w1， . . 如果我离开，σ，p存在两个过渡，以及aσJ，pJw，使得σ = σJ，但pj = pJ。2D. 尼温斯基岛《理论与计算科学中的电子选择注》123（2005）195201L R2L R3.1（1， 2）情况P（1，2）型由a和a1+~2αa和a2+~2αa两个点组成(they不需要拆分）：1 2请注意，在第五节，我们给出了具有最小可能秩的模式，记住将它们移动相同的偶数会产生相同类的模式3.2（0， 1）的情况P（0，1）型由两个0+~2αa和1+~2αa构成，其中a为整数：0 1(Of当然，这幅图只代表两种对称情况之一。）3.3（0， 2）的情况一个P（0，2）模式n由三个环a0+~2αa，a1+~2αa和a2+~2αa组成，其中前两个环在a处分裂（注意第三个环不需要与它们中的任何一个分裂）。0 13.4（1， 2， 3）例P（1，3）模式稍微复杂一点：202 D. 尼温斯基岛《理论与计算科学》中的电子选择注123（2005）195-208123L R123L R它可以由点a、b、c、d表示（其中a和b不必不同），halopa1+2αa和路径a~b，b~c，b~d，c~a，dd~a，使得合成b~c~a~b形成2+ 2α-环，合成b~d~a~b形成3+ 2α-环，这两个环在b处分裂.3.5（1，n）情形，n≥4通过在a中添加4+ 2α循环，从如上所述的P（1，3）模式获得P（1，4）模式：4更一般地说，当n ≥ 4时，P（1，n）模式是由一个P（1，n-1）模式（带一个提升参数2α）通过a lopan~+2αa得到的.3.6（0，n）情形，n≥3与前面的情况类似，通过在a中添加3 + 2α循环，从P（0，2）模式获得P（0，3）模式：2L R∈ {}A∈ {}AD. 尼温斯基岛《理论与计算科学》第三卷注记123（2005）195-20 8 2030 1更一般地说，当n ≥ 3时，P（0，n）模式是由一个P（0，n-1）模式（带一个提升参数2α）通过a lopan~+2αa得到的.自动机A的状态q是生产性的，如果A接受来自q的某棵树，是T（Aq），其中Aq是A，初始状态被q代替。图案如果所有的状态都发生在其中（即，由构造区分的状态，以及路径上的状态），则是生产性的。设（i，n）表示（i，n）的对偶指数。我们准备声明如下。定理3.1如果一个确定性树自动机A包含一个生产性（i，n）模式（i0，1），则T（）不能被一个索引为（i，n）的非确定性树自动机识别。证明（思想）我们遵循以前在[10]和[12]中探索的证明层次结果的一般方法，这反过来又遵循Rabin [15]的原始思想，Rabin首先证明（在我们的符号中）M1不能被索引（1， 2）的自动机接受。给定一个假设的m个状态的自动机，为了“愚弄”自动机，人们将禁止模式发展成一棵树。生产力用于完成不存在的子树。参数是从（0，3）和（1，4）层开始递归的，但基本层需要一些特殊的解释。Q4从积极的方面一个更困难的方向是证明，如果自动机A不包含禁止模式，那么T（A）确实可以被所需索引的非确定性自动机识别（通常小于A的索引）。定理4.1如果一个确定性树自动机A不包含任何产生式（i，n）模式（i0，1），则T（）被一个索引为（i，n）的非确定性树自动机识别.根据（i，n），证明分为几种情况。一个典型的论点将包括分解一个自动机A（视为自动机的话）204 D. 尼温斯基岛《理论与计算科学》中的电子选择注123（2005）195-208一^^^^^一强连接的组件，并应用归纳参数的子自动机诱导这种方式。在下文中，我们提出一个条件，即自动机只有生产状态;因此，所考虑的所有模式也是生产的。回想一下，我们称树语言（i，n）-可行，如果它可以被索引为（i，n）的非确定性自动机识别。4.1（0， 1）的情况引理4.2如果A 中不存在P（1，2）模式，则T（A）是（0，1）-可行的。证据从[12]的花引理可以得出，A是一个（确定的）（0， 1）-自动机，因此A本身是表元。Q4.2（1， 2）情况引理4.3如果A不具有P（0，1）模式，则T（A）是（1，2）-可行的。虽然这种情况在[13]中已经解决了，我们在这里给出另一个证明，它将作为归纳论证的基础。证明（草图）设A = A ↑0↑1. ↑n其中n是大于A中最大秩的奇数。给定T（A）中的树t，存在A在t上的唯一游程。这定义了树中被A的不同强连通分量（SCC）接受的部分。我们可以有一个没有接受条件的自动机，它在每个节点上计算t的唯一运行的状态。我们要构造的自动机将是这个自动机和（1，2）自动机的乘积，A的每个SCC对应一个。后一个自动机的作用将是检查是否A的运行的所有路径永远停留在给定的SCC中。这些自动机的组合将给出识别T（A）的（1，2）自动机。首先考虑一个最大秩为n的SCC，比如C。我们知道n是奇数，在C中没有P（0， 1）模式。这意味着C中没有秩为2引理4.6设i2. 如果没有P（1，i + 1）模式，则T（ ）是（0，i）-可行。草图（Sketch）i = 2的情况在引理4.5中得到解决。我们考虑i为奇数的归纳步骤;另一种情况类似。设A = A ↑0↑1. ↑n其中n是大于A中最大优先级的偶数。取一个具有最大n的SCCC。由于n是偶数，我们知道在C\ {q：rank（q）=n}中没有P（1，i）模式。因此，根据归纳假设，这部分等价于一个（0，i-1）自动机。 那么C也等价于一个（0，i− 1）自动机，因为我们可以把n变成2。取最大秩为n+1的SCCC。 部分C q：rank（q）=n+1等价于上面段落中的（0，i因此，当我们将秩n+1变为i时，C等价于（0，i）自动机。Q4.6在（1，i）情况下，i>2引理4.7设i2.如果 没有P（0，i）模式，则T（ ）是（1，i +1）-可行。D. 尼温斯基岛《理论与计算科学中的电子选择注》123（2005）195207^^^A≤^一一K∩∩草图（Sketch）i = 2的情况在引理4.4中得到解决。我们考虑对i为奇数的归纳步骤，另一种情况是类似的。设A = A ↑0↑1. ↑n其中n是大于A中最大优先级的奇数。如前所述，逐一考虑A取一个SCC，称之为C，具有最大的秩n。 当我们移除状态从C的秩n，那么在其余的，我们不能有P（0，i- 1）模式。归纳假设意味着这部分可以用（1，i）自动机来模拟.因此，当我们将i用于最初秩为n的顶点时，整个C可由（1，i）自动机识别。现在让C是具有最大秩n+ 1的SCC。当我们考虑没有秩为n+ 1的状态的C时，通过前面的段落，我们得到这个图的每个SCC都等价于一个（1，i）自动机。因此，我们可以用i+1代替n+ 1，得到一个等价于C的（1，i+ 1）自动机。Q5决策程序我们现在估计的过程的复杂性，给定一个确定性的奇偶校验树自动机A，计算T（A）在非确定性层次的水平。我们首先需要将A的图简化为仅生产状态。 假设A没有更多的非生产状态，我们计算A = A ↑0↑1. ↑n↑n+1，其中n是A的最大秩，在时间多项式上|一|（[12]）。搜索P（i，k）模式，对于k n，当然可以在多项式时间内进行因此，该过程中最昂贵的部分在于计算（视为树自动机）的生产状态 确定性的事实并没有帮助（任何自动机都可以转换为具有相同非空状态的确定性自动机，即自动机读取原始自动机的运行）。这个问题等价于模态微演算的模型检验问题，以及解决奇偶博弈[4]。时间复杂度为O（n2）时间复杂度为O（n）[6]，其中n =|一|并且（i，k）是自动机的索引。最好的非确定性估计是UP co-UP [5]（改进了[4]的NP co-NP上界），这将我们的问题置于PUPco-UP中。引用[1] Arnold，A.，µ-calculus alternation-depth hierarchy对二叉树是严格的，RAIRO- TheoreticalInformatics and Applications33（1999），329208 D. 尼温斯基岛《理论与计算科学》中的电子选择注123（2005）195-208∩[2] 布拉德菲尔德，J.C.， 模态μ演算交替层次结构是严格的，理论。Sci. 195（1997），133[3] 埃默森，EA，和C. S. Jutla，“Tree automata，mu-calculus and determinacy”，收录于：Proceedings 32th Annual IEEE Symp.计算机基础Sci. （1991），368[4] 埃默森，EA，C. S. Jutla和A.P. Sistla，关于µ-演算片段的模型检查，CAVSci. 697（1993），385[5] Jurd zin'sk i，M. ，DecidingthewinnerinparitygamesisUPCo-UP，InformatitonProcessingLetters68no.3（1998），119[6] Jurd zin'sk i，M. ，Smallprogreses ure esores o r eso 不是计算。Sci. 1770（2000），290[7] Lenzi，G.，μ-演算的一个层次定理，在：ICALP Sci. 1099（1996），87[8] Mostowski，A.W.，无限树的正则表达式和自动机的标准形式，在：计算理论，Lect。Sci. 208（1985），169-176.[9] Mostowski，A.W.，弱自动机和弱一元公式的层次，理论计算。Sci. 83（1991），323[10] 我的天啊。，Ofixed edpointclones，ICALP'86，L e c t. 不算。 Sci. 226（1986），464-473.[11] 我的天啊。，Fixededpointscharacterizationoffinitebehaviourofitestatesystems，TheoreticalComputer Science189（1997），1[12] 我的天啊。 和我[1998]《自动化与自动化技术研究》，1998年，《计算机技术讲义》。Sci. 1373（1998），320-331。[13] 我的天啊。 和我我们了解到，确定的语言、基本的计算能力是一个巨大的差距。Sci. 303（2003），215[14] 拉宾作案手法二阶理论和无限树上自动机的可判定性，美国社会科学院学报，141（1969），1-35。[15] 拉宾作案手法“Weakly definable relations and special automata”, in:[16] 托马斯，W.，“Languages, automata, and logic”, in:[17] 你的孩子，T。 F. ，OndecidingigifdeterministicRabi nlagis inBu？chiclass，ICALP2000，Lect. Notes Comput.Sci. 1853（2000），663-674.[18] Wagner，K. ，EinetopologischeCharakterissierungeinigerKlassenregulaürFolgenmengenn，J. Inf. Process.赛博恩EIK13（1977），473
我的内容管理
收起
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助 
