Lambek演算中序列可导性

►理论计算机科学电子笔记53（2003）网址：http://www.elsevier.nl/locate/entcs/volume53.html22页Lambek演算中序列可导性杰拉尔德·佩恩1多伦多大学计算机科学系10 KingToronto M5S 3G4，Canada摘要一个图论的建设表示的推导侧条件的建设中的公理化的联系Lambek证明网，以及一个天真的算法，将其应用到可导性问题的Lambek演算。文中还介绍了这种结构的一些基本性质，并讨论了与Lambek范畴文法句法分析有关的一些复杂性问题。1引言本文考虑的问题是否可以解析一个字符串的话相对于Lambek范畴语法（LCG）在多项式时间。虽然LCG被认为是弱等价于上下文无关文法（CFG），但这个解析问题的最相关的形式上的联系仍然是，即，“是否可以在Lambek C a l cul us中导出等式A1：A n B？，“其中A 1 ;：：; A n ; B a re（p o ssi bl y complex）catego r ie s. 给定一个LCG，G，和一个具有唯一词法特征的环w1：wn，A1：A n ，在G中，当B=s时，这相当于串识别，B =s是G的区别类别.本文提出了一个简单的图论构造，用来表示LCG导子的良形性约束，称为LC-图还提供了一个类似于标准CFG图表解析器的算法，用于回答上述可导出性问题。至关重要的是，该算法不是多项式时间的，因此它不能解决开放问题，但希望它将有助于最终解决1电子邮件地址：gpenn@cs.toronto.edu2003年3月由ElsevierScienceB出版。 V. 操作访问根据C CB Y-NC-N D许可证进行。Penn2可导性问题。文中还讨论了一些相关的句法分析问题。使用LCG进行图表解析并不是一种新方法。Koenig [5]提出了一个图表解析器，它增加了元规则，只要应用了引入规则，就会产生一个新的Hepple [4]建议将这些图表合并为一个单一的在这个图中，像往常一样，合法边形成一个本原区间的全序序列，但是每当假设一个假设范畴时，就增加一个新的本原区间，它有一个自由端。然后，引入相当于将使用这个新的假设区间的边抽象回到它被添加到的完全有序的区间序列上Morrill [8]使用了一种类似图表的表示方法，并结合了Lambek演算的证明网[14]。Penn[10]在Elf编程语言[12]中使用了类似的表示法来表示Lambek演算中的演绎。Morrill [9]还提供了一个实际的解析算法，同样基于证明网。证明的优点是，它们从直接基于自然演绎或Lambek Calculus的非线性表示的证明搜索技术中产生的所有虚假歧义中抽象出来。因此，它们揭示了LCG识别的最坏情况复杂性分析必须面对的非确定性的本质来源然而，最近关于LCG解析的大部分工作都选择了在高阶（线性）逻辑编程语言中详细描述LCG证明搜索的优雅实现。虽然这些确实很优雅，但它们可能不是发现手头问题复杂性的最佳选择。正是出于这个原因，本文选择了一种“回到基础”的方法，只使用一些简单的算法和基本的图论来解决这个问题。LC-图表示LCG推导证明网中与公理公式链接相关的替换信息。鉴于我们在图论领域中对算法效率和NP完全性的广泛了解，我们希望这里给出的算法可以被增强并被证明是多项式的，或者如果不能这样增强它，将揭示一个已知的NP难问题嵌入到LCG识别中。在子结构逻辑的证明搜索中使用图论也不是一个新的问题。LC-图及其良构性约束肯定会让人想起GirardMoot和Puite [7，13]提出了一个包含LCG及其所有多模态扩展的图重写系统。LC-图要简单得多，但其扩展到多模态LCG仍然是一个有待进一步研究的课题。各种LCG解析问题的时间复杂性是一个更广泛的理论图景的一部分，这个图景本身就非常有趣Lambek演算只是大量子结构逻辑中的一个，Penn3到目前为止，所有这些都可以通过模态算子的相对存在或不存在以及控制这些算子行为的推理结构规则而相互关联[6]。目前还不完全清楚的是，这些操作符和规则的存在或不存在如何影响证明搜索的复杂性 正如乔姆斯基形式语言体系中的每一个著名的成员一样，我们用计算字符串成员所需的自动机和栈来描述这类语言的特征，这类逻辑的操作特征也是非常有用的，既可以作为表示的对偶形式，也可以作为构造具有某些操作属性的其他逻辑的指南。在这个更广泛的图片，Lambek演算脱颖而出，作为一个逻辑的巨大的历史利益，时间复杂性的可导性仍然是未知的。此外，由于LCG与上下文无关语言的弱等价性，它在计算语言学和计算生物学中具有许多非常有趣的潜在应用，其中已经使用了CFG。特别地，LCG原则上可以用作无上下文等效统计模型的底层离散结构，该统计模型自然地暴露与标准CFG的那些数值参数非常不同的数值参数选择，或者对于该统计模型，可以更容易地从数据估计某些参数。为了简单起见，这里的演示将考虑Lambek演算的无乘积片段，其中不能导出具有空前提的序列第2节首先介绍证明网，以及如何构建它们。第三节介绍了LC-图及其良构性准则。第四节给出了LC-图的一些基本性质，并说明了它们与证明网正确性准则的关系。第5节展示了如何将这些图与一个类似于上下文无关的图表解析器的简单解析算法结合起来。 第6节然后讨论了几个相关的LCG分析问题的最坏情况分析复杂度。2 证明网这一节的大部分内容摘自Roorda的优秀论文[14]。然而，这里的介绍偏向于使用LCG进行解析在解析中，构造证明网涉及四个主要步骤：(i) 从候选序列创建终端公式序列(ii) 将终端公式的序列词法展开为公理公式，(iii) 在公理公式上建立公理链接，然后(iv) 应用从词汇展开导出的变量替换规则Penn4►和公理化的联系。前两步非常快速、简单和确定，而且总是成功的。公理化链接是麻烦的开始：这一步并不总是成功的，即使成功了，它创建的变量子项规则也可能不是格式良好的，这意味着必须找到另一个公理化链接。2.1终端公式给定一个概率复杂度为x的类别的序列，A1：AnB ，我们首先将它们写为以下极化公式序列AA *A B+;12N也就是说，所有前提都接收负极性，而结果接收正极性。这些被称为终端的公式。例如，以开头：（A=（A\A））=AA A\A A\A A股;这里A是文法中的一个基本范畴，我们得到了下列终结公式序列：（（A=（A\A））=A） 一 （A\A） （A\A） A+：我们还必须用变量来标记序列中的每个公式+（（A=（A\A））=A）：b A：a（A\A）：h（A\A）：l A：m2.2词汇展开下一步是通过使用以下规则为序列中的每个公式替换一串更简单的公式来转换终端公式序列，直到不能进行更多的替换为止（在本文A\B的意思是，（ A\B） −→A+B（A\B）+−→B+A（ A=B ） −→AB+ （ A=B ）+−→B A+Penn5B）：v−→B：vA：u[v：= u：v]从上面的终端公式序列开始，我们得到变换：（（A=（A\A））=A） 一 （A\A）（A\A） A+−→（A=（A\A））A+A （A\A） （A\A） A+−→一 （A\A）+A+A （A\A）（A\A） A+−→一 A+A A+A （A\A） （A\A）A+−→一 A+A A+A A+A（A\A） A+−→一 A+AA+A A+AA+A A+这些公式中的范畴随着每一个规则的应用而变得更简单，因此这很容易终止，并且无论选择变换的赎回顺序如何，最终的结果都是相同的。在最后的序列中，所有的公式都由极化的原子/基本范畴组成这就是公理化公式的序列。一般来说，每个正公式将被标记为一个变量，每个负公式将被标记为一个来自非类型化Lamb- da演算的项。当我们创建终端公式序列时，我们为所有公式分配了变量，无论是正的还是负的。 在词法展开过程中，我们必须指定由转换规则产生的公式的标签。 这涉及到使用新的变量和形成新的条款，从这些新的变量和旧的条款标签展开的公式。每当我们展开一个正公式时，我们还必须指定一个额外的变量替换作为关联该规则所使用的变量+（A\B）：t−→A：uB：tu++（A\0 0+（A=B）：t−→A：tu B：u++0 0（A=B）：v −→ B：uA：v [v：= u：v]上面标记的终端公式序列然后像这样展开+（（A=（A\A））=A）：b A：a（A\A）：h（A\A）：l A：m−→++（A=（A\A））：bc A：c A：a（A\A）：h（A\A）：l A：m−→+++A：bcd（A\A）：dA：c A：a（A\A）：h（A\A）：l A：m−→（ n）+++A：bcdA：e A：fA：c A：a（A\A）：h（A\A）：l A：m−→关于我们A：bcdA：e A：fA：c A：aA：g A：hg（A\A）：l A：m−→关于我们A：bcd A：e A：fA：c A：aA：g A：hg A：k A：lk A：m具有替换，d：=f：e，从步骤（E）开始。Penn6\\2.3公理化链接在 词 汇 展 开 之 后 ， 我 们 将 匹 配 的 公 理 化 极 公 式 对 r （ X + 和 X， 对 于BasicategryX）。公理公式的子序列加上这些链接的完全匹配称为（公理）链接。 如果子序列是由展开一个终端公式序列得到的整个序列，则我们将其区分为一个生成链。 在一个链接中，我们还可以识别子链接，即每个链接跨越其边界零次或两次的连续链接，即，没有链接跨越子序列 以下是上述示例的两个跨接连杆：（一）关于我们A：bcdA：e A：fA：c A：aA：g A：hg A：k A：lkA：m+（A\A）：d（A\A）：h（A\A）：l（A=（AA））：bc（（A=（A\A））=A）：b（二）关于我们A：bcdA：e A：fA：c A：aA：g A：hg A：k A：lkA：m+（A\A）：d（A\A）：h（A\A）：l（A=（AA））：bc（（A=（A\A））=A）：b通常，我们把词法展开写在公理序列下面，把链接写在上面。第一个生成链接包含一个子链接+在A：F和A：G之间。第二个没有，虽然有一个+在A：F和A：K之间。2.4变量替换每个公理链接：+X：v X：t可以与替换相关联，v：= t。 上述两个跨越键的取代是：（1）d：=f：e;m：=bcd;e：=lk;g：=f;k：=hg;c：=a（2）d：=f：e;m：=bcd;e：=lk;k：=f;c：=hg;g：=aPenn7+第一个替换来自于在逻辑展开过程中获得的副条件。最后一步是将相关的替换迭代地应用于标记正终端公式的变量，直到没有更多的替换可用。在我们运行的示例中，这个标签是m：(1) m→bcd→bc（f：e）→ba（f：e）→ba（f：lk）→ba（f：lhg）→Ba（f：lhf）(2) m→bcd→bc（f：e）→bhg（f：e）→bha（f：e）→bha（f：lk）→bha（f：lf）2.5证明网的正确性准则一个（Lambek）证明网由一个词汇展开的项公式序列、一个由此产生的公理公式序列的生成链接和一个产生项t的变量替换组成，其中：PN（1）恰好有一个正终端公式，PN（2）变量替换终止（t是有限项），PN（3）如果t包含s，则新的事件发生在s中并且不会发生在s之外，PN（4）分配给负终端公式的每个变量出现在t，PN（CT）t没有封闭子项，并且PN（L）公理连杆是平面的，即，可以如上面的（1）和（2）中那样绘制公理链接，使得没有两个链接交叉。14，pp.31 -34]证明了一个证明网在Lambek演算中是可导的，当且仅当存在一个证明网，其终端公式对应于它。3 LC-图连续生成链接并根据证明网的正确性标准对其进行测试显然不是使用LCG进行解析的有效方法。理想情况下，我们想要的是一种动态编程方法来增量地构建证明网，用某种方式表示我们关于正确性的知识的状态，并增量地、紧凑地组合这些知识。本节定义了一个图，用来表示我们对正确性的认识状态。第5节提出了一种使用这些图的动态规划方法。首先，我们需要更多的术语。给定一个终端公式序列和一个词法展开，变量v在展开中的任何地方标记公式X：v，称为aPenn8⟨⟩正变量如果X是一个基本范畴，我们通过说它是一个简单加变量如果X是一个复范畴，那么我们通过以下方式区分V：说它是一个可达变量。一个变量，v，那个标签是公式X：v 是一负变量一般来说，负公式用项来标记，并且这些项一般包含负变量和正变量。在词汇展开期间，为形式为v：= u：w的每个可变量v添加替换。在这种情况下，u和w被称为v的子变量。给定一个公理公式序列，V（）是作为公理公式标号的子项出现的变量集。给定一个公理公式序列上的连接M，它的LC-图是一个有向图G = V; E，使得V是最小集合，其中：V（ ）V，V包含每个子变量，其中至少有一个子变量五，而E是最小的集合，其中：对于每一对u; v∈V，如果v是一个双变量，u是v的子变量之一，则（v; u）∈E，并且对于M中的每一个公理链：+X：v X：t对于t中的每个变量u，（v; u）∈E。G当G中存在从某个u到v的路径时，我们说u;v，或者u;v，当很清楚G指的是哪个如果u = v，则u;v。在LC-图的上下文中，当我们看到一个加变量（分别为 负变量、负变量等），我们称之为正节点（分别为负节点、负节点等）。此外，我们称G中的一个节点为终端节点当且仅当它的出度为0。然而，请注意，加节点经常出现在标记负公理公式的术语中（加节点的负出现），但它们仍然是加节点。这是由以下两个词汇展开规则引起的：+（A\B）：t−→A：uB：tu+（A=B）：t−→A：tu B：u;其中u标记正公式，因此是正节点，但也发生在项tu中，其标记负公式。 一个负节点对应于一个变量，它作为一个负公式的标签单独出现，A：v. 负节点永远不会出现正的情况。我们说一个具有LC-图G=V; E的联结M是整数当且仅当：I（1）G中存在唯一的入度为0的节点，Penn9∈节点是路径可访问的，I（2）G是无环的，对于每一个节点v vV，都有一条从它的正子节点到它的正子节点的路径，u，到它的负女儿w，以及I（CT），对任意一个结点v ∈ V，在G，v; x中有一条路，其中x是最小结点，且r是nolambda-n odev0 ∈Vhthatv;v0 →x。上述例子中的两个跨越连杆是一体的。它们具有以下LC图：（一）Bm+c+a le+k+hDG+F（二）M+Hg+ae+Lf k+λ节点被圈出。 d是一个带子节点e和f的双结点。负节点和简单的正节点用符号表示请注意，节点的极性不受轴向连接选择的任何影响-它仅来自末端序列及其合法展开。当我们说一个结点出现在一个子链接的LC图中时，我们会滥用符号说它出现在一个子链接中4 LC-图的基本性质LC-图表示在证明网构造的最后步骤中必须进行的替换 每个正节点对应于一个替换的redex，该替换必须被它所指向的由正节点和负节点组成的项替换。 有了这种直觉，LC图完整性标准的相关性证明网建设可以证明。4.1程度命题4.1对于每个LC-图，每个加节点：(i) 标记一个正终止公式，在这种情况下，它的入度为BC+dPenn100，或(ii) 具有至多1的入度在生成链接中，唯一入度为0的加节点是正终端公式的标签。证据加 节点通过负发生（从公理链接接收一个弧）或通过lambda节点父节点获取传入弧。一个正终结公式的加节点既不具有这两种性质，也不具有这两种性质，因此其入度为0。通过对词汇展开规则的考察，我们可以发现，在一个跨越连接中，每一个其他的加节点要么有一个负出现，要么是一个加节点的子节点，而不是两者都有。所以其他人的入度都是1。在非生成子链接中，可能发生子链接中的正节点具有负出现，但负出现落在子链接之外。在这个子链接的LC图中，这个加节点的入度为0。 根据定义，如果一个正子链在子链的LC图中，那么它的正节点父链也在子链的LC图中。2命题4.2对于每个LC-图，每个负节点：(i) 是一个节点的负子节点，在这种情况下，它的入度为2，或者(ii) 其入度为1。证据 通过对词法展开规则的考察，可以发现每个负节点都出现在一个公理化公式的标号中。由于公理链必须是公理公式的完全匹配，因此每个负节点从公理链接收一个传入弧负子节点还从它们的lambda节点父节点接收一个传入弧。2我们说一个节点是链接中的根节点当且仅当它在链接的LC-图中的入度为0。 根据命题4.2，根节点总是正节点. 如果它标记了一个正终端公式，那么根据命题4.1，我们称它为它出现的任何链接中的真根节点如果它是一个正节点，它的负出现落在一个子链接之外，那么我们称它为不正确的根节点。命题4.3对于每个LC-图，每个负节点的出度为0。证据 所有的弧都从一个正节点指向一个负节点或一个正节点。负节点对应的标签终端公式所产生的前提和约束变量的条件。 这些永远不是替代品的赎回。2Penn11命题4.4对于每个LC-图，每个C-节点的出度为1或2。在一个生成链中，每个节点的出度都是2。证据 一个双结点的出度是1还是2取决于它的一个或两个子结点是否在链中。如果这个连锁是一个跨越连锁，那么它的两个子连锁都在其中。2命题4.5在生成链中，每个简单加节点的出度至少为1，即，没有终端加节点。证据 每个简单的加节点标记一个正的公理化公式。由于链是公理公式的完全匹配，每个正的公理公式都有一个公理链，从这个公理链在LC-图中产生至少一个从其加节点标号出发的外弧。根据命题4.4，每一个加节点都有1或2的出度，所以没有终端加节点。2简单的加节点具有无限的出度。 其原因是简单的加节点将它们的输出弧归功于公理链。公理链接映射到出现在项中的所有变量，标记为负的公理公式，并且对该项中的变量数量没有限制然而，我们可以区分出一个特定的外向弧命题4.6对于每个LC-图，每个非终结单正节点都有一条到负节点的外弧。证据 这些公理链接映射的项恰好包含一个自由负节点。这一点可以通过归纳来证明，归纳的词汇展开步骤的数量来得出它们。由正展开规则创建的子节点是负子节点，因此由单个负节点组成 由负展开规则创建的词由应用于新加节点的词汇展开步骤较少的词组成。24.2路径命题4.7对于每个LC-图，每条路都从一个正节点开始，只通过正节点，终止于正节点或负节点。证据命题4.3的一个微不足道的推论。2反对意见4. [8]设 u;v和 w;v ，且dv不是节点的负数，n是ru;w或w;u。证据 如果v不是一个节点的负子节点，那么根据命题4.1和命题4.2，它的入度为1。此外，根据命题4.7，路径u;v和w;v上的每一个中间节点都是一个加节点，而根据命题4.1，其入度为1。2Penn12→命题4.9给定一个真根结点，存在一个唯一的加结点，它标记一个公理公式，可以从它通过一条只通过加结点的路径访问。证据 这是公理化公式的标号，它是由正终端公式沿其正子体的词汇展开得到的。2我们把命题4.9中提到的公理标号称为真根结点的公理反射如果正终结公式是一个基本范畴（因而也是一个公理公式），那么它的真根结点的公理映射就是真根结点本身。4.3正确性命题4.10如果一个生成链满足I（2），那么它满足PN（2）。证据 由于LC-图是无圈的，它的节点可以拓扑排序。如果我们总是按照这个顺序选择排名最高的redex进行下一步扩展，那么在变量替换的每一步中，排名最高的redex的排名严格递减，因此变量替换终止。2命题4.11如果一个生成链满足I（2）和I（3），则它满足PN（3）。Proof.给定nI（3），r是像w是e在s中发生v的r。 如果有5个值出现在s外，则r将是一个p，来自某个p-nodew;v，使得u;w（并因此扩展为s的子项）和w;u（其中v：s是w的扩展的子项）都不存在。根据命题4.2，v的入度是2，其中一条弧来自它的外节点l，另一条弧通过公理链来自其他的外节点x。我相信这一点; v我们返回vial，在re中也会是一条路径w;l→u。如果路径u;v通过l，则会有一个圈u;lu，其由y（2）包围。这是一个很好的例子.由于x不是负节点，那么根据命题4.8，如果从w到vp的路径是通过hx的，则在hu;w;x→v或路径w;u;x → v处的r是r a p，这与我们的假设相矛盾。 2命题4.12如果一个生成连锁满足I（1），那么它满足PN（1）和PN（4）。证据 如果存在唯一的入度为0的结点，则根据命题4.1，存在唯一的正终结公式。所有节点都可以从唯一的正确根节点进行路径访问，包括负节点。由于变量替换从这个正确的根节点开始，并且由于根据命题4.3，每个负节点的出度为0，因此应用所有替换Penn13直到不能再应用时，将产生一个包含每个负节点的项，包括负终端公式的所有标签。2命题4.13如果一个生成连锁满足PN（3），那么它满足I（3）。证据 给定PN（3），每个子项v：s对应于一个具有一个负子项v和一个正子项u的双结点，其在变量替换下的展开产生s。 v在s中的出现则意味着存在一条路径u;v。2命题4.14如果一个生成链满足PN（1）和PN（2），那么从正终结公式的标号中没有路径可达的节点包含在一个圈中。证据 如果一个节点v是从（唯一的）正终端公式的标签路径可访问的，它包含在一个循环中，那么从该标签开始的变量substitution将不会终止，因为对应于n的redex将扩展到包含v的项。2命题4.15如果一个跨越连锁满足PN（1），PN（2），PN（3）和PN（4），那么它满足I（1）。证据 如果生成链接满足PN（1）和PN（4），那么由于变量替换从唯一正端公式的标签开始，并导致一个包含所有负端公式标签的负变量的项，那么相应的负节点必须是从相应的真根节点（入度为0）可路径访问的。正确根节点的公理反射，以及其间的所有lambda节点都可以从正确根节点访问每个这样的子节点都有一个负的子节点，这些子节点同样是可访问的，因为每个子节点都有一条路径到它的两个子节点。LC图中的所有其他节点都被引入词汇展开中的一个位置，在它们下面的某个地方有一个负公式。 这些剩余的节点是从适当的根节点的路径可访问的证明是通过归纳的词汇展开步骤的数量下降到最低的这样的负公式。 为了使归纳法能够进行下去，我们必须通过增加这样一个条件来加强这一主张，即对于负结点，存在一条路径，它的最后一步来自一个公理链。基例正是负终端公式的负结点和从真根到其公理化反射路径上的负子结点。 对于前一个范畴，最后一步必须是公理链，因为负终结公式不是一个公理结点的子体。 对于后一个范畴，命题4.13使I（3）成立，因此这些负子体m中的每一个都有一个正姐妹子体p，使得存在一条路径p;m。这条路径的最后一步必须是由于公理链接，因为p的最大节点父节点和Penn14→→∈→→ →/联系我们B）：v−→B：vm位于从适当根节点到其公理反射的路径上，并且在该路径上的节点都没有负出现。假设最后一个展开步骤是正向展开：++（A\0++0（A=B）：v−→B：uA：v根据归纳假设，有一条到下交点v的路径，因此有一条p到上交点v0。通过I（3），从V0开始， 给你。 4.我的朋友2，则u的入度为2，但hv0时p的最大值为 ; uwereviav你，他在休息会是一个循环v0 ; vv0. 根据命题4.14，这是一个矛盾，因为v是从properrootnode可达的路径。在hv0时， ; u是从公理链中产生的。否则，最后的展开步骤是负展开：+（A\B）：t−→A：uB：tu+（A=B）：t−→A：tu B：u根据归纳假设，有一条通往t中负结点的路径，它的最后一步来自公理链。因为t不标记公理公式，所以链接必须附加到包含tu的否定公式，因此也有一条到u的路径。2命题4.16如果一个生成连锁满足I（1）和PN（2），那么它满足I（2）。证据 根据命题4.14，从标号正终结公式中没有路径可达的节点包含在圈中，而根据I（1），每个节点都是路径可达的。2命题4.17如果一个生成连锁满足I（2）和I（3），则它满足I（CT）当且仅当它满足PN（CT）。证据 给定I（CT），它声称没有任何一个节点在变量替换下扩展为闭项。 给定一个带负子体w的双结点v，存在一条路径v; x，其中x是某个终端结点，对于该终端结点，r不等于v0 V的值等于v;v0x。 4.我的朋友5，x是一个负节点。如果x不是一个负结点的负子结点，则x对应于一个负终端公式的标号，因此v不平凡地表示一个闭项。否则，假设每个这样的x是一个节点的负子节点，即， 对应于som_e_e_m的约束变量。 让v0是一个无意识的人，而你是v0的一部分。x=w，andv0 =v，或者实际上是v;v0x。由I（3）可知，剩余部分是一条路径v0u0 yx，其中y=v0，或者r是一个环，其中h是常数I（2）。4 .支持2，x具有2的n-degreee，因此r v;v0 →x，whichA：uPenn15→与我们对x或v的选择相矛盾。在后一种情况下，根据提案4。8，v0 ; v. 这意味着一个在x的空间中包含一个自由的元素，因此它不是封闭的。给定PN（CT），没有一个双曲项l是闭项，所以必须有一条从其对应的双曲节点v到除从v可达的双曲节点的负子节点之外的负节点的路径。（三）坚持。2PN（L）将在第5节中讨论。4.4非跨越式链接虽然许多上述结果只涉及跨越联系，有几个评论，我们可以做一般的联系如上所述，可能会发生正节点出现在链接中，但它的负出现落在链接的边界之外。这些是不正确的根节点。相反的情况也可能发生：一个负的正节点出现在一个链接中，但正节点却落在链接之外。 这些是终端加节点。 生成链接是一种特殊情况，其中只有一个根节点-一个真正的根节点-并且没有终端加节点。此外，一个子链中的外链节点的出度可以是1或2，这取决于它们有多少子链落在外链上。命题4.18在满足I（2）的任何链接中，至少有一个根节点，并且每个节点都是从至少一个根节点可路径访问的。证据循 环 性的一个平凡结果和LC-图有有限多个节点的事实。2命题4.19在任何链接中，每个节点都是最多从一个根节点可访问的路径，除了根节点的负子节点。证据命题4.8的一个微不足道的推论。2我们称子链接中的终端公式T为外围公式，当且仅当子链接的公理序列中最右边 我们称子链接中的节点为外围的，当且仅当它是从外围终端公式的词汇展开中派生出来的。 这显然包括出现在术语中标记子链接中最右边或最左边的公理公式的节点，但它可能包括更多。以下是根节点和ter-numerals-plus-节点的有趣特征，用于可导性的目的命题4.20如果一个终端公式序列有一个正终端公式，并且它是最右边的终端公式，那么在该序列的任何子链接中，每个根节点和终端加节点都是外围的。Penn16证据 终端加节点和不正确的根节点有一个负（分别为）。正的）出现在给定的子链接内，以及正的（相应地，负的）发生在子链接之外 但是，当一个节点的正向和负向出现同时存在时，必然源自相同的词汇展开，即，同一终端公式的词汇展开。这意味着词汇的展开必须是外围的，因为一次出现，也就是展开的一部分，落在子链接之外正确的根节点是不同的-它们在任何地方都没有负的发生概率。然而，根据假设，正确的根节点标记了最右边的终端公式，所以当它们出现在子链接中时，它们必然是最右边展开的一部分。25 建立跨越式联系LC-图本身的定义并不能解释解析的复杂性，如果我们只是在构建一个生成链接后使用它们来检查变量替换的话。 我们真正需要的是一种建立链接的方法，它允许我们逐步检查相关LC图的完整性。为了帮助我们完成这项任务，我们可以使用剩下的一个证明网正确性标准PN（L），它要求公理化的联系可以被画成公理化公式序列上方的平面图这就是根据上下文无关语法对字符串进行括号的方式。因此，我们可以在固定的语法上使用图表解析器来列表链接及其LC图：1）L→B L2）B→XL X+;对每个基本范畴X3）B→X+LX;对每个基本范畴X4）B→XX+;对每个基本范畴X5）B→X+X;对每个基本范畴X6）L→BL对应于在其上存在子键的那些公理式的连续 B对应于在其上存在由单个公理链括起来的子链的那些连续性。用这种文法构造的任何生成链接或子链接都将满足PN（L）。 为了满足其他正确性标准，我们必须描述每个规则应该如何组合其右侧边的LC图。Penn175.1基本情况：规则（4）和（5）对于这些规则，产生的链接由单个公理链接组成-没有其他LC子图可以组合。此链路的LC图是由以下组成的最小图a.一组节点，由标记X+的多个节点来管理，其中每个弧映射到X的标记中的每个节点，以及对于LC-图中的每个子节点，从其父节点到其自身的弧。5.2括号：规则（2）和（3）这里，所得到的链接具有LC-图，其是由上述两类弧加上：L.C.G. L. C. L. D. L. C. L. D. L.C.L.D.5.3附例：规则（1）对于规则（1），所得到的链接具有LC-图，该LC-图是由以下各项组成的该LC-g表示该特定H和-侧类别B，LC-g表示的是右侧和右侧类别，L和对于LC-图中的每个子节点，从其父节点到其自身的弧。5.4轻微附带关系：规则（6）在规则（6）中，结果的LC-图与R_h和R_s的LC-图相同。5.5解析复杂度图分析的边有附加LC-图违反了上下文无关图分析的一个非常重要的不变量，即覆盖相同子序列的任何两个边可以被视为相等，而不管它们是如何导出的。这里，通过两个不同的附加或通过一个附加和一个括号，它是可能的，得到两个边覆盖同一子序列的不同LC-图。没有已知的方法来处理这些边缘作为平等的，虽然见第7进一步讨论这一点。这意味着在添加新的边之前，我们必须检查覆盖相同区间的现有边，并将它们的LC-图组合成一个集合。Penn18虽然可以添加到图中的边的数量仍然与公理公式序列的长度成二次关系（这反过来又随着初始边的长度而增长），但是通过附加来组合两个现有边涉及将所有可能的LC-图对组合在它们各自的集合中，结果是这些集合的大小可以作为边所覆盖的区间的函数指数地增长。 因此，该算法在最坏情况下不是多项式时间的。5.6逐步实施完整性标准尽管该算法的最坏情况复杂度为指数级它在LC-图的完整性准则的执行上确实允许一定程度的增量在这三个完整性准则中，I（2）是最突出的，因为它要求一种特定的路径，即循环，不存在，而I（3）和I（CT）要求一种特定的路径确实存在。这使得I（2）很容易增量执行 在断言一条边之前，我们简单地从它的集合中丢弃具有圈的LC-图。如果没有LC-图，则可以丢弃边本身。I（3）和I（CT）可以用LC图在较小程度上逐步地强制执行，尽管关于这一点的进一步讨论见第7如果没有一个终端加节点是从一个lambda-节点的加-子节点可路径访问的，并且该加-子节点还具有I（3）和I（CT）所需的路径，那么它将永远不会具有它们，并且LC-图可以被丢弃。如果所需的路径已经存在，那么它们将永远不会消失，因此不需要再次检查这个子加I（1）不能增量检查，但是：命题5.1如果一个生成连锁满足I（2）和PN（1），那么它满足I（1）。证据 给定PN（1），只有一个节点的入度为0。由于没有循环，因此每个节点都必须是从该节点可路径访问的2PN（1）可以在一开始就通过确保三个公式的序列只有一个正公式来实施。 这意味着如果我们检查I（2），我们可以忽略I（1）。6 相关解析问题重要的是要认识到，可推导性决策问题只是LCG解析的一个方面 还有其他复杂性的来源，以及其他可以做出的限制，这些限制可以影响整个问题的复杂性。Penn196.1修正语法Pentus [11]通过展示如何从任何LCG构造等价的CFG，证明了LCG与CFG是弱等价的在最坏的情况下，结果CFG的大小是指数大于原来的LCG，所以这种结构不能用来建立一个多项式时间的双射之间的两类解析问题。另一方面，如果我们固定一个特定的LCG，G，离线应用Pentus的构造，然后问“给定一串单词w，w属于L（G）吗？”，则该固定LCG识别问题是多项式时间的，因为CFG识别也可以在多项式时间中执行 Finkel和Tellier [2]对此进行了详细描述。6.2词汇歧义给定一个单词串w和一个语法G（unfixed），如果我们想知道w是否属于L（G），我们必须首先通过G的词典找到与w的每个单词相关联的类别，然后再提出可导性问题。然而，通常情况下，与w的词相关的类别不止一个。即使可导性问题在多项式时间内是可解的，迭代地选择类别并执行可导性检查也可能导致2nPossiblecategoryselectionsgivesnastrinninggofnwords. 事实上，没有一种方法可以在一次校对过程中以某种方式组合多个词汇类别，尽管很可能存在一种方法6.3解析与识别序列可导性，就像上下文无关的图表解析一样，问一个是或否的问题。在CFG解析的上下文中，这被称为字符串识别问题。 真正的CFG解析不仅涉及确定字符串是否可解析，还涉及提供字符串的解析树（如果可解析）。在最坏的情况下，这需要指数级的时间，因为虽然解析图表可以在多项式时间内构建，但解包图表并解析其中包含的每个树可能需要指数级的时间。类似于非可推导性的情况，是为推导提供一个实际的语义术语，而不仅仅是“是”或“否”。 该项是在标注最右（正）末端公式的标签上执行变量替换后获得的项。 正如在某些CFG中存在固有的二义性字符串一样，在Lambek演算中也存在固有地具有多于一个语义读数的序列。事实上，读数的数量可以作为候选数据集长度的函数呈指数增长定义家庭成员之间的关系，参数如下：{（A=（A\A））：bi}A：a{A\A：hiA\A：li}► A：m我我Penn20+D我e我K+我G+我F我1L2HGLKJKJK≤ ≤−≤≤例如，S2是：（A=（A\A））：b1（A=（A\A））：b2A：a A\A：h1A\A：l1A\A：h2A\A：l2 A：m命题6.1对于所有的自然数i，在Lambek演算出i，其语义读数由字符串给出：b1x1： bixia（fi：liyifi）： （fi：l1y1f1）其中对于所有1 ≤ j ≤ i，要么（xi= and yi= hi），要么（xi= hiand yi=）。证据设Gi为图：我+的我我我Gi是图：我我++我我+的我我+的我我且令尾1（i）= ci且尾2（i）= gi。可以看出，Gi和Gi在内部1 2拥有I（3）和I（CT）所要求的路径，它们包含的节点是无环的。设j1：ji是一个由1和2组成的序列，G是包含下列子图和弧的最小图：G1 ; G2 ;：;Gi;j1j2jim→b1; m→c1; m→d1;tailji（i）→a;且对所有1≤k≤i−1;tailjk（k）→bk+1;tai ljk（k）→ck+1;tai ljk（k）→dk+1：不管j1：ji的选择如何，G都是非循环的，因为所有的Gk是对于1 k i是非循环的，并且对于任何1 k i 1，都没有弧从k +1索引节点遍历到较少索引节点。此外，b k、c k和d k中的所有三个都是路径可访问的任何节点都可以访问Gk的每个节点，包括尾部jk（k），G的每个节点都是路径可访问的。对于任意j1：ji的选择，G都存在Planar联系，大致类似于本文第2节中给出的运行示例，实际上是S1。当jk= 1时，yk=hk，xk=. 当jk= 2时，xk = hk，yk =.2jk的选择是相互独立的，因此Si有2i个可能的读数。请注意，这完全是用DiBCHBCeF