没有合适的资源?快使用搜索试试~ 我知道了~
0Array 15 (2022) 1002030BY-NC-ND许可下的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。0ScienceDirect提供的内容列表0数组0期刊主页:www.elsevier.com/locate/array0正规阶乘语言的决策树0Mikhail Moshkov0沙特阿拉伯Thuwal 23955-6900,科技王国大学(KAUST)的计算机、电气和数学科学与工程部和计算生物科学研究中心0文章信息0关键词:正规阶乘语言 识别问题成员问题 确定性决策树非确定性决策树0摘要0本文研究了有限字母表�上的任意正规阶乘语言。对于长度为�的单词�(�)属于正规阶乘语言�的情况,我们研究了解决识别和成员问题的决策树的深度,确定性和非确定性。在识别问题的情况下,对于来自�(�)的给定单词,我们应该使用查询来识别它,其中每个查询对于某个�∈{1,…,�},返回单词的第�个字母。在成员问题的情况下,对于长度为�的字母表�上的给定单词,我们应该使用相同的查询来识别它是否属于集合�(�)。对于给定的问题和树的类型,我们研究了解决�(�)问题的考虑类型的决策树的最小深度�(�)的平滑最小深度�(�)=max{�(�)∶�≤�}。随着�的增长,解决识别问题的决策树的平滑最小深度要么被上界常数限制,要么随对数或线性增长。对于其他情况(解决识别问题的非确定性决策树,以及解决成员问题的确定性和非确定性决策树),随着�的增长,决策树的平滑最小深度要么被上界常数限制,要么线性增长。作为获得的结果的推论,我们研究了考虑四种情况的决策树的平滑最小深度的联合行为,并描述了正规阶乘语言的五个复杂度类。我们还研究了由一个禁止词给出的{0,1}字母表上的正规阶乘语言类。01.介绍0本文研究了有限字母表�上的任意正规阶乘语言。阶乘语言满足以下条件:如果单词�1��2属于语言,则单词�也属于它。对于长度为�的单词�(�)属于正规阶乘语言�的情况,们研究了解决识别和成员问题的决策树的深度,确定性和非确定性。在识别问题的情况下,对于来自�(�)的给定单词,我们应该使用查询来识别它,其中每个查询对于某个�∈{1,…,�},返回单词的第�个字母。在成员问题的情况下,对于长度为�的字母表�上的给定单词,我们应该使用相同的查询来识别它是否属于�(�)。对于给定的问题(识别问题或成员问题)和树的类型(确定性或非确定性解决问题),我们研究了解决�(�)问题的考虑类型的决策树的最小深度�(�)的平滑最小深度�(�)=max{�(�)∶�≤�意正规阶乘语言,随着�的增长,解决识别问题的决策树的平滑最小深度要么被一个0邮箱地址:mikhail.moshkov@kaust.edu.sa。0常数,或者随着对数或线性增长。这些结果立即可以从更一般的结果中得出,该结果是在[1]中针对任意正则语言得到的。对于其他情况(决策树解决非确定性识别问题和解决成员问题的决策树非确定性和确定性),随着�的增长,决策树的平滑最小深度要么被常数上界限制,要么线性增长。在会议论文[2]中,宣布了关于解决非确定性识别问题的决策树的平滑最小深度的任意正则语言的分类,但没有给出证明。在本文中,我们考虑了正则阶乘语言的更简单的分类,并给出了完整的证明。与解决成员问题的决策树相关的结果是新的。作为得到的结果的推论,我们研究了所考虑的四种情况下决策树的平滑最小深度的联合行为,并描述了正则阶乘语言的五个复杂度类。我们还研究了字母表�={0,1}上的正则阶乘语言类,其中每个类由一个禁止词给出。评估有限字母表�上的无限语言�的复杂度的一个众所周知的方法是研究其所谓的组合0https://doi.org/10.1016/j.array.2022.1002032022年1月7日收到;2022年6月2日修订后收到;2022年6月3日接受20数组15(2022)1002030M. Moshkov0复杂度(也称为计数函数)��(�)是长度为�的单词在�中的数量[3,4]。本文提出了评估语言�的复杂度的其他方法,该方法基于研究解决识别和成员问题的决策树的深度如何取决于单词的长度。这种方法更加复杂,但可以给出更详细的语言分类。为了证明这一点,我们比较了图5和图6中所示的由图表�3和�4生成的语言。对于两种语言,计数函数都是线性增长的。对于第一种语言,解决识别问题的决策树的最小深度随对数增长,但对于第二种语言,解决识别问题的决策树的最小深度线性增长。0我们应该提到最近的一篇论文[5],其中得到了类似的结果0对于字母表�上的子词闭合语言,得到的结果是:如果一个单词�1�1�2�������+1则单词�1���也属于语言。0很明显,每个子词闭合语言都是一个阶乘语言。0此外,有限字母表上的每个子词闭合语言都是一个正则语言[6]。可以证明,由一个禁止词00给出的字母表�上的语言�(00)是一个正则阶乘语言,但不是子词闭合的。因此,字母表�上的子词闭合语言类是字母表�上的正则阶乘语言类的一个适当子类。0在本文和[5]之间的主要区别在于,0在后一篇论文中,我们并不假设子词闭合语言是由确定性有限自动机给出的。我们描述了一些简单的标准(基于语言中特殊类型的单词)来解决解决识别问题的决策树的最小深度的行为。对于解决识别问题的决策树的行为的不同表述需要非常不同的证明。另一个区别是,在[5]中,我们直接考虑决策树的最小深度。0本文的其余部分组织如下。在第 2 节中,我们0考虑主要概念,在第 3 节中是主要结果,在第 4 节中是这些结果的两个推论。02. 主要概念0在本节中,我们讨论与正则阶乘相关的概念。0语言和解决这些语言的识别和成员问题的决策树。02.1. 正则阶乘语言0� = {0, 1, 2, …} 是非负整数集,� 是一个0至少有两个字母的有限字母表。通过 ��,我们表示字母表 �上的所有有限词,包括空词 �。如果 � ∈ �� 是词 � ∈ �� 的一个因子,那么称 � ∈ 的一个因子,其中 �1,�2 ∈ ��。如果一个语言 � � ��包含其词的所有因子,则称其为阶乘语言。如果一个词 � ∈ �� 是 �的最小禁止词,如果 � � � 并且 �的所有真因子属于 �,则称其为 �的最小禁止词。我们用 ��(�) 表示 � 的最小禁止词语言。已知[7],如果且仅当语言 �的最小禁止词语言 ��(�) 是正则的时,阶乘语言 �才是正则的。特别地,具有有限最小禁止词集 ��(�) 的阶乘语言 �是正则的。在本文中,我们研究任意非空正则阶乘语言。0众所周知,每个正则语言都可以用0确定有限自动机(DFA)[8]。与[8]中一样,我们将考虑不仅具有完全过渡函数的完全DFA,还具有部分过渡函数的部分DFA。这样的DFA可以用其过渡图(简称图)[9]表示。0在字母表 � 上的图是一个三元组 � = (�, �0, �),其中 �0是一个有限有向图,可能具有多条边和环,其中每条边都标有来自 �的字母,并且离开每个边缘的边缘都标有来自 � 的字母。0节点用两两不同的字母标记,�0 是称为起始的 � 的节点,并且 � 是 �节点的一个非空集。0图的路径是一个任意序列 � = �1, �1, …,��,0��,��+1 是 � 的节点和边的序列,使得边 �� 离开节点 �� 并进入节点 ��+1,对于 � =1,…,�。我们现在以以下方式定义 �� 中的一个词 �(�):如果 � = 0,则 �(�) = �。让 � > 0并且让 �� 是附加到边 �� 的字母,� = 1,…,�。那么 �(�) = �1 � ��。我们说路径 � 生成词�(�)。注意,从相同节点开始的不同路径会生成不同的词。0我们用 �(�) 表示图 � 的所有路径的集合,每个0它从节点 �0 开始,并在 � 中的一个节点结束。0�� = {�(�)∶� ∈ �(�)}。0我们说图 � 生成语言 ��。众所周知,��是一个正则语言。0如果恰好0| � | 边缘离开 � 的每个节点。注意,这些边缘用 �中两两不同的字母标记。这样的图对应于完全DFA [8]。如果对于 �的每个节点,存在一条从 �(�) 开始并包含该节点的路径,则称图 �为简化的。这样的图对应于简化的DFA [8]。已知[8],对于字母表 �上的每个正则语言,都存在一个在字母表 �上的完全图,可以生成该语言。因此,对于每个非空正则语言,都存在一个可以生成该语言的简化图。0设 � 是一个正则阶乘语言,� = (�, �0, �) 是一个0生成语言�的简化图。由于语言�是阶乘的,我们可以额外假设图�的每个节点都是终结的——这不会改变由�生成的语言,因为对于每个单词,语言�包含这个单词的每个前缀。如果图�是简化的,我们将称之为f-简化的,因为它是简化的,并且图�的每个节点都是终结的。此外,我们将假设所考虑的正则阶乘语言�是非空的,并且由一个f-简化的图给出,该图生成了这个语言。0我们不会考虑非确定有限自动机(NFA)来代表0由于NFA的研究本质上是更复杂的任务,所以我们不会考虑NFA。02.2. 识别和成员问题的决策树0任何自然数�,记�(�)=�∩��,其中��是字母表�上长度等于�的单词的集合。我们考虑与集合�(�)相关的两个问题。识别问题:对于来自�(�)的给定单词,我们应该使用属性(查询)��1,…,���来识别它,其中���,�∈{1,…,�},是从��到�的函数,使得0���(�1���)=��对于任何单词�1���∈��。成员问题:对于来自�(�)的给定单词,我们应该使用相同的属性来识别这个单词是否属于集合�(�)。为了解决这些问题,我们使用在�(�)上的决策树。0在�(�)上的决策树是一棵带有根的有限有向树,0具有以下特性的属性:0• 根和离开根的边没有标记。• 每个节点,不是根也不是终端节点,都标有0与集合{��1,…,���}中的属性一起。0• 离开一个节点的边,不是根的节点,都标有一个0字母来自字母表�。0如果满足以下条件,则称�(�)上的决策树为确定性的0以下条件:0• 根有且仅有一条边。• 对于任何节点,不是根也不是终端节点,边0离开这个节点的标记有两两不同的字母。30Array 15 (2022) 1002030M. Moshkov0图1. 解决{100,010,001}单词集的识别问题的决策树,确定性和非确定性。0让�是�(�)上的决策树。�中的完整路径是任何0�=�0,�0,…,��,��,��+1的序列,�的节点和边,使得�0是根,��+1是终端始节点,��+1是终端节点,对于�=0,…,�。我们以以下方式定义集合�(�,�):如果则�(�,�)=��。让�>0,属性����附加到节点��,��是0附加到边��的字母,�=1,…,�。然后0�(�,�)={�1���∈��∶��1=�1,…,���=��}。0让�(�)≠�。我们说决策树�在�(�)上解决了0如果�满足以下条件,则称�(�)上的决策树为非确定性的0• �的每个终端节点都标有来自�(�)的单词。•对于�(�)中的任何单词�,树�中存在一条完整路径�0�,使得�∈�(�,�)。0• 对于树�中的任何单词�∈�(�)和树�中的任何完整路径�0使得�∈�(�,�),路径�的终端节点标有单词�。0我们说�对�(�)解决了识别问题0如果�是解决�(�)识别问题的确定性决策树,则�是确定性地解决了�(�)的识别问题。0说明所考虑的概念的决策树示例0在图1中呈现。0我们说�对�(�)解决了问题0如果�满足以下条件,则�以非确定性方式解决了�(�)的成员问题:0•�的每个终端节点都标有来自集合的数字0•对于任意单词�∈��,树�中存在一条完整路径�0•对于任意单词�∈��和树�中的任意完整路径�0使得�∈�(�,�),路径�的终端节点如果�∈�(�)则标记为数字1,否则标记为数字0如果�是解决�(�)成员问题的决策树,则�对�(�)解决了问题0如果�是解决�(�)成员问题的确定性决策树,则�以非确定性方式解决了�(�)的成员问题0设�是�(�)的决策树。我们用�(�)表示决策树的最大深度0�中完整路径中不是根节点也不是终端节点的节点数。值�(�)称为决策树�的深度。0我们用����(�)(����(�))表示决策树的最小深度0对于�(�)的树,该树以非确定性(确定性)方式解决了�(�)的识别问题。如果�(�)=�,(�)=����(�)=0我们用����(�)(����(�))表示决策树的最小深度0对于�(�)的树,该树以非确定性(确定性)方式解决了�(�)的成员问题。如果�(�)=�,(�)=0����(�)=0。03.决策树深度的界限0设�是一个非空的阶乘正则语言。在本节中0我们考虑四个函数����,����,����和����的行为0定义在集合��{0}上,其值来自�。对于任意自然数�,0����(�)=max{����(�)∶1≤�≤�},0����(�)=max{����(�)∶1≤�≤�},0����(�)=max{����(�)∶1≤�≤�},0����(�)=max{����(�)∶1≤�≤�}。0对于任意一对��∈{��,��,��,��},函数����(�)是平滑的0函数����(�)的类比。03.1.决策树确定性解决识别问题0设�=(�,�0,�)是字母表�上的f-简化图。0图�的路径如果至少有一条边,并且该路径的第一个节点等于最后一个节点,则称为图�的循环。图�的循环如果除最后一个节点外,其节点是两两不同的,则称为基本循环。0如果每两个不同的基本0图�的循环没有共同的节点。设�为简单图,�为图�的路径。图�的不同基本循环的数量,这些循环与�有共同节点,用��(�)表示,并称为路径�的循环长度。0��(�)=max{��(�)∶�∈�(�)0被称为图 � 的循环长度。0让 � 是一个简单图, � 是图的一个基本循环0� ,并且 � 是循环 � 的节点。从节点 � 开始,循环 �生成了一个无限周期的单词,字母表为 � 。这个单词将被表示为 � ( �, �, � ) 。我们用� ( �, �, � ) 表示单词 � ( �, �, � ) 的最小周期。如果图 � 存在两个不同的基本循环 � 1 和 �2 ,循环 � 1 和 � 2 的节点分别为 � 1 和 � 2 ,以及图 � 的路径 � 从 � 1 到 � 2,满足以下条件: � ( �, � 1 , � 1 ) = � ( �, � 2 , � 2 ) 且路径 � 的长度可以被 � ( �, � 1 , � 1 )整除。如果图 � 不是依赖的,那么它就是独立的。下一个定理立即遵循自定理2.1[ 1 ],这是一个类似的陈述,适用于所有正则语言。0定理1. 设 � 是一个非空的正则阶乘语言,覆盖了0字母表 � 和 � 是一个f-简化图,生成了语言 � 。那么以下陈述成立:0(a)如果 � 是一个独立的简单图且 �� ( � ) ≤ 1 ,那么 � �� � ( � ) =0� (0(b)如果 � 是一个独立的简单图且 �� ( � ) ≥ 2 ,那么 � �� � ( � ) =0� (log � ) .0(c)如果 � 不是独立的简单图,那么 � �� � ( � ) = � ( � ) .03.2. 用决策树解决识别问题的非确定性方法0设 � 是一个非空的正则阶乘语言,覆盖了字母表0� . 对于任意自然数 � ,我们定义语言 � 的参数 � � ( � ) 。如果 � ( � ) = � ,那么 � � ( � ) =0 。让 � ( � ) ≠ � , � = � 1 � � � ∈ � ( � ) ,并且 � � {1 , … , � } 。表示 � ( �, � ) = { � 1 � �� ∈ � ( � ) ∶ � � = � � , � ∈ � } (如果 � = � ,那么 � ( �, � ) = � ( � ) ),并且 � � ( �, � ) =min{ | � | ∶ � �0{1 , … , � } , | � ( �, � ) | = 1} . 那么0� � ( � ) = max{ � � ( �, � ) ∶ � ∈ � ( � )} .0请注意,对于任意单词 � ∈ � ( � ) , � � ( �, � ) 是单词 �的最小字母数,允许我们将其与属于 � ( � ) 的所有其他单词区分开。4𝐿the word 𝛼𝑢𝑖 from the words 𝛼𝑢𝑗𝑤𝑢𝑖−𝑗−1, 𝑗 = 0, … , 𝑖−1, we need to useat least one letter from each of 𝑖 words 𝑢 appearing in 𝛼𝑢𝑖. Therefore𝐿0inimum lengthfrom 𝛴∗ ⧵ 𝐿. Denote by 𝑡 the length of 𝑤0. Since |𝐿| = ∞, 𝐿(𝑛) ≠ ∅ forany natural 𝑛. Let 𝑛 be a natural number such that 𝑛 > 𝑡 and 𝛤 be adecision tree over 𝐿(𝑛) that solves the problem of membership for 𝐿(𝑛)nondeterministically and has the minimum depth. Let 𝑤 ∈ 𝐿(𝑛) and 𝜉be a complete path in 𝛤 such that 𝑤 ∈ 𝛴(𝑛, 𝜉). Then the terminal nodeof 𝜉 is labeled with the number 1. Beginning with the first letter, wedivide the word 𝑤 into ⌊𝑛∕𝑡⌋ blocks with 𝑡 letters in each and the suffixof the length 𝑛−𝑡 ⌊𝑛∕𝑡⌋. Let us assume that the number of nodes labeledwith attributes in 𝜉 is less than ⌊𝑛∕𝑡⌋. Then there is a block such thatqueries (attributes) attached to nodes of 𝜉 does not ask about lettersfrom the block. We replace this block in the word 𝑤 with the word𝑤0 and denote by 𝑤′ the obtained word. It is clear that 𝑤′ ∉ 𝐿 and𝑤′ ∈ 𝛴(𝑛, 𝜉), but this is impossible since the terminal node of the path𝜉 is labeled with the number 1. Therefore the depth of 𝛤 is greaterthan or equal to ⌊𝑛∕𝑡⌋. Thus, ℎ𝑚𝑎𝐿 (𝑛) ≥ ⌊𝑛∕𝑡⌋. It is easy to construct adecision tree over 𝐿(𝑛) that solves the problem of membership for 𝐿(𝑛)als to 𝑛. Therefore ℎ𝑚𝑑𝐿 (𝑛) ≤ 𝑛.0数组15(2022)1002030M. Moshkov0引理2. 设 � 是一个非空的正则阶乘语言,覆盖了0字母表 � . 那么对于任意自然数 � ,都有 � �� � ( � ) = � � ( � ) .0证明。首先,我们证明 � �� � ( � ) ≥ � � ( � ) . 让 � 是一个关于0� ( � ) ,它以非确定性方式解决了 � ( � ) 的识别问题,且 � ( � ) = � �� � ( � ) . 让 � 是来自� ( � ) 的单词,对于该单词0� � ( � ) = � � ( �, � ) . 然后决策树 � 包含一条完整的路径 � ,使得 � ∈ � ( �, � ) 且路径 �的终端节点标记为单词 � 。很明显 � ( �, � ) ∩ � ( � ) = { � } . 让 � 包含 �个不是根节点也不是终端节点的节点,且 � � � 1 , … , � � � � 是属性0附加到这些节点。表示 � = { � 1 , … , � � } . 那么 � ( �, � ) = { � } . 因此 � ≥ � ( � ) . 很明显 � ( � ) ≥ � . 因此, � �� � ( � ) = � ( � ) ≥ � ≥ � � ( �, � ) = � 0我们现在证明 � �� � ( � ) ≤ � � ( � ) . 可以证明,对于每个0� ∈ � ( � ) ,我们可以构造一条完整路径 � � ,满足以下条件: � �中不是根节点也不是终端节点的节点数等于 � � ( �, � ) , � ( �, � � ) ∩ � ( � ) = { 的终端节点标记为单词 � 。如果我们合并所有路径 � � , � ∈ � ( � ),我们得到一个决策树,它以非确定性方式解决了 � ( � ) 的识别问题,且深度等于 � � ( � ) 。因此, � �� � ( � ) ≤ � � ( � ) 且 � �� � ( � ) = � � ( � ) . □0定理3. 让 � 是一个非空的正则阶乘语言,由字母表 � 生成,并且 � = (�, �0, �)0字母表 � 上的非空正则阶乘语言 � = (�, �0, �) 是一个f-减少的图表,它生成语言�。那么以下陈述成立:0(a) 如果 � 是一个独立的简单图表,则 ����(�) = �(1)。0(b) 如果 � 不是独立的简单图表,则 ����(�) = �(�)。0证明。(a) 让 � 是一个独立的简单图表,并且 ��(�) ≤ 1。根据定理1,����(�) = �(1����(�) ≤ ����(�)。因此0��0让 � 是一个独立的简单图表,并且 ��(�) ≥ 2。让 � 是0自然数。如果 �(�) = �,那么 ��(�) = 0。让 �(�) ≠ �。用 � 表示图表 �中的节点数。在引理4.5 [1] 的证明中,证明了对于任何单词 � ∈ �(�),��(�, �) ≤ �(+1)。因此 ��(�) ≤ �(4� + 1)。因此,根据引理2,����(�) ≤ �(4� + 1)对于任何自0� 和 ����(�) = �(1)。0(b) 让 � 不是简单图表,并且 �1,�2 是不同的基本0图表 � 的循环,它们有一个共同的节点 �。由于 �是一个f-减少的图表,它包含从节点 �0 到节点 � 的路径 �,并且 �是一个最终节点。让路径 � 的长度等于 �,循环 �1 的长度等于 �,循环 �2 的长度等�。让 � 是由路径 � 生成的单词,� 是由从 � 到 � 通过循环 �1 经过 �次得到的路径生成的单词,� 是由从 � 到 � 通过循环 �2 经过 �次得到的路径生成的单词。单词 � 和 � 是不同的,并且它们的长度相同为 ��。0� ∈ ��{0}。集合 �(��) 包含单词 ���和单词 ������−�−10对于 � = 0,…,� − 1。很容易证明 ��(��, ���) ≥ �:为了区分单词 ��� 和单词 ������−�−1,� = 0,…,� −1,我们需要至少使用每个单词 � 中的一个字母。因此 ��(��) ≥ �,并且根据引理2,����(��) ≥ � = (�� − �)∕(��)。让 � ≥ �10并且让 � 是最大的自然数,使得 � ≥ ��。显然,� − �� ≤ ��。因此 ����(�) ≥ ����(��) ≥ (� − �� −�)∕(��)。因此0����(�) ≥ �∕(2��) 对于足够大的 �。不等式 ����(�) ≤ � 是0显而易见。因此,����(�) = �(�)。0让 � 是一个依赖的简单图表。那么存在两个不同的0图表 � 的基本循环 �1 和 �2,循环 �1 和 �2 的节点 �1 和 �2,以及图表 � 的路径 � 从 �1 到�2,满足以下条件:�(�, �1, �1) = �(�, �2, �2) 并且路径 � 的长度是 �(�, �1, �1)的倍数。让我们提醒一下,对于 � = 1,2,�(�, ��, ��) 是由以节点 �� 开始的循环 ��生成的字母表 � 上的无限周期单词,并且 �(�, �1, �1) 是单词 �(�, �1, �1) 的最小周期。因此0图2. 图表 �0。0� 是一个f-减少的图表,它包含从节点 �0 到节点 �1 的路径 �,并且图表 �的所有节点都是最终的。让路径 � 生成长度为 � 的单词 �。记 � = �(�, �1, �1)。让循环 �1的长度等于 ��,路径 � 的长度等于 ��,并且路径 � 生成单词 �。用 � 表示单词 � (�, �1, �1)的长度为 �的前缀。现在我们定义两个长度为 ��� 的单词:� = ��� 和 � = ���(�−1)。很明显 � ≠�。0� ∈ � � {0} 。集合 � ( � � ) 包含单词 �� � 和单词 �� � �� � − � −10让 � 是最大的自然数,使得 � ≥ � � 。显然, � − � � ≤ ��� 。因此 � �� � ( � ) ≥ � �� � ( � � ) ≥ ( � − ��� − � )∕( ��� ) 。因此0显然, � �� � ( � ) = � ( � ) 。□0语言)根据解决识别问题的非确定性决策树的最小深度对简化图的分类更加复杂[2 ]。特别是,存在一个依赖简化图 � 0 (见 图2)的简化图,其起始节点标记为符号 + ,唯一的终节点标记为符号 �,生成了字母表 {0 , 1} 上的正则语言 � 0 = {0 � 10 � ∶ �, � ∈ � },该语言不是阶乘的,并且对于该语言 � �� � 0 ( � ) =03.3. 解决成员问题的决策树0� 是一个无限语言,而符号 | � | < ∞ 意味着 � 是一个有限语言。0(a)如果 | � | = ∞ 且 � ≠ � � ,那么 � �� � ( � ) = � ( � ) 且 � �� � ( � ) = � ( � ) 。0证明。很明显,对于任何自然数 � ,都有 � �� � ( � ) ≤ � �� � ( � ) 。0因此, � �� � ( � ) = � ( � ) 且 � �� � ( � ) = � ( � ) .Array 15 (2022) 1002035Table 1Complexity classes 1, … , 5.0表1 复杂度类 � 1, … , � 5 .0� 是独立的 ��(�) � � � �� � � � �� � � � �� � � � �� � � 简单图0� 1 是 = 0 �(1) �(1) �(1) �(1) � 2 是 = 1 �(1) �(1) �(�) �(�) � 3 是 ≥ 2 �(log �) �(1) �(�) �(�) � 4 不等于 � � �(�) �(�) �(�) �(�) � 5 不等于� � �(�) �(�) �(1) �(1)0任意自然数 � ≥ �。因此,对于每个自然数 � ≥ �, � �� �(�) = 0 和0� �� �(�) = 0。因此, � �� �(�) = �(1) 和 � �� �(�) = �(1)。0假设 � = � �, � 为自然数, � 为字母表 � 上的决策树0�(�),它由根节点、一个标记为 1的终端节点和一个离开根节点并进入终端节点的边组成。可以证明 �在确定地解决了 �(�) 的成员问题,并且深度等于 0。因此 � �� �(�) = 0 和 � �� �(�) =0。因此,0� �� �(�) = �(1) 和 � �� �(�) = �(1)。□04. 推论0在本节中,我们考虑定理1,3和4的两个推论。04.1. 函数 � �� �, � �� �, � �� �, 和 � �� � 的联合行为0在本节中,我们假设每个正则阶乘语言0字母表 � 由一个 f-简化图 � 给出,它生成了由 � � 表示的考虑的语言。为了研究函数 � �� � �, � �� � �, � �� � �, 和 � �� � � 的所有可能的联合行为,我们考虑五个类别0正则阶乘语言 � 1,…, � 5 在表1的第2-4列中描述。特别地, � 1由所有正则阶乘语言 � � 组成,其中图 � 是一个独立的简单图且 ��(�) =0。很容易证明复杂度类 � 1,…, � 5 是两两不相交的,并且每个正则阶乘语言 � �属于这些类别之一。对于每个类别,表1中考虑的函数 � �� � � 和 � �� � �的结果直接来自定理1和3。0每个类别 � 1,…, � 5。假设 � = ( �, � 0 , � ) 是字母表 � 上的一个f-简化图,它生成了一个正则阶乘语言。0假设 � � ∈ � 1。由于 ��(�) = 0,� 是一个有向无环图,而且0语言 � � 是有限的。使用定理4,我们得到 � �� � �(�) = �(1) 和0� �0假设 � � ∈ � 2。由于 ��(�) = 1,� 包含循环,并且0语言 � � 是无限的。根据引理4.2 [1],| � �(�) | = �(1)。因此 � � ≠ ��。0假设 � � ∈ � 3。由于 ��(�) ≥ 2,� 包含循环,并且0语言 � � 是无限的。根据引理4.2 [1],| � �(�) | = �(���(�))。因此 � � ≠ ��。0假设 � � ∈ � 4。由于 � 不是一个独立的简单图,� 是一个0包含循环的图,语言 � � 是无限的。我们知道 � � ≠ � �。使用定理4,我们得到 � ��(�0假设 � � ∈ � 5。那么 � � = � �。使用定理4,我们得到 � �� � �(�) =0� (0我们现在展示类 � 1,…,� 5 都是非空的。对于simplic-0ity,我们假设 � = �,其中 � ={0,1}。很容易将所考虑的例子推广到至少有两个字母的任意有限字母表 �的情况。在图中的例子中,起始节点标记为符号 +,所有节点都是最终的。0用字母 � 描述的图 � 1 。0我们可以证明 � 1 是一个独立的简单的f-减少的图,并且 �� ( � 1 ) =0。这个图生成了语言 � � 1 = { �,0},这是阶乘的。因此 � � 1 ∈ � 1。0图3. 图 � 1 。0图4. 图 � 2 。0图5. 图 � 3 。0图6. 图 � 4 。0图7. 图 � 5 。0用字母 � 描述的图 � 2 。0我们可以证明 � 2 是一个独立的简单的f-减少的图,并且 �� ( � 2 ) =1。这个图生成了语言 � � 2 = {0 � ∶ � ∈ �},这是阶乘的。因此 � � 2 ∈ � 2。0用字母 � 描述的图 � 3 。0我们可以证明 � 3 是一个独立的简单的f-减少的图,并且 �� ( � 1 ) =2。这个图生成了语言 � � 3 = {0 � 1 � ∶ �, � ∈ �},这是阶乘的。因此 � � 3 ∈ � 3。0用字母 � 描述的图 � 4 。0我们可以证明 � 4 是一个依赖的简单的f-减少的图,生成了语言 � � 4 = {0 � 1 � 0 � ∶ �, �∈ �, � ∈ {0,1}},这是阶乘的。很明显 � � 4 ≠ ��。因此 � � 4 ∈ � 4。0用字母 � 描述的图 � 5 。0我们可以证明 � 5 是一个f-减少的图,不是简单的。这个图生成了语言 � � 5 =��,这是阶乘的。很明显 � � 5 = ��。因此 � � 5 ∈ � 5。0正规阶乘语言 � 可以有不同的f-减少的dia-0grams,它们生成它。然而,对于这样的每个图 �,语言 � � = �将属于相同的复杂性类。让我们假设相反:存在一个正规的阶乘语言 �和两个生成它的f-减少的图 � 1 和 � 2,并且对于这样的语言 � � 1 和 � � 2属于不同的复杂性类。那么,对于一些对 �� ∈ { ��, ��, ��, �� },函数 � �� � � 1 和 � �� � � 2 有0不同的行为,但这是不可能的,因为 � �� � � 1 ( � ) = � �� � � 2 ( � ) 对于0任何自然数 �。60数组15(2022)1002030M. Moshkov0图8. 图 � (0)。04.2. 由一个禁止的词给出的字母表 {0,1} 的语言0让 � = {0,1},� ∈ ��,并且 � ≠ �。我们用 � ( � ) 表示0字母表 � 上的语言,由所有不包含 � 作为因子的 �� 中的单词组成。这是一个具有 �� ( � ( �)) = { � } 的正规阶乘语言。下面的定理指示了对于每个非空单词 � ∈ ��,语言 � ( � )属于的复杂性类 � �。0定理5. 让 � ∈ �� 并且 � ≠ �。0(a)如果 � ∈ {0,1},那么 � ( � ) ∈ � 2。(b)如果 � ∈ {01,10},那么 � ( � ) ∈ � 3。(c)如果 � � {0,1,01,10},那么 � ( � ) ∈ �4。0我们现在描述一个f-减少的图 � ( � ) ,它生成了lan-0guage � ( � ) 对于一个非空单词 � ∈ ��。让 � = � 1 � � �,�0 = �,并且 � � = � 1 � � � 对于 � =1,…,� − 1。集合 � ( � ) = { � 0,� 1,…,� � −1 } 是单词 �的所有合适前缀的集合。然后 � ( � ) = ( �, � 0, � ),其中图 � 的节点集等于 � ( � ),� 0 = �0,并且 � = � ( � )。对于 � = 0,…,� −2,一条边离开节点 � � 并进入节点 � �+1。这条边标记为字母 � � +1。对于 � = 0,…,� − 1,一条边离开节点 � �并进入节点 � � ∈ � ( � ),使得 � � 是单词 � � �� � +1 的最长后缀,其中 �� � +1 = 0 如果 � � +1= 1,且 �� � +1 = 1 如果 � � +1 = 0。这条边标记为 �� � +1。很容易证明 � ( � )是一个在字母表 � 上的f-减少的图。从定理10 [ 7 ] 可以得出图 � ( � ) 生成了语言 � ( �)。0让�∈���{�},并且�=�1���。我们用 ��表示单词 ��1� ���。0很容易证明以下陈述。0引理6. 让�∈��,并且�≠�。那么
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- RTL8188FU-Linux-v5.7.4.2-36687.20200602.tar(20765).gz
- 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
- SPC统计方法基础知识.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功