不连续语法：O(nlog4n)优化算法处理复杂句法与局部成本函数

不连续语法（DG）是一种复杂的句法形式主义，起源于中心语驱动短语结构语法、政府约束、德语依存语法等多个理论框架的融合。它汲取了优选论、树邻接语法、词汇功能语法和心理语言学的思想，旨在提供一种更为灵活和精细的句法分析方法。在DG中，语法图是无环和有向的，由类型化的节点和边构成，这些节点和边按照继承层次结构组织，这使得它可以有效地处理词序、着陆点、岛屿、协议、选择性限制等语言现象。 DG的核心在于局部成本函数，这是一种用于编码语法约束和违反成本的工具。它允许将句法分析视为一个优化问题，通过搜索部分句法分析来找到代价最小的解析树。作者在《理论计算机科学电子笔记》第53期（2001年）中提出了一个基于局部搜索的句法分析算法，该算法针对DG的特点设计，特别在树深度和岛约束条件下，其最坏情况复杂度达到了O(nlog4n)。这表明在有限的资源消耗下，算法能有效处理各种不连续词序现象，如主题化、相对化、提取、加扰和不连续AP。 然而，值得注意的是，尽管算法在存在局部歧义的情况下表现良好，但当遇到所谓的“花园路径”句子时，即那些可能导致无限递归的句子，它会与人类分析者一样面临困难，无法找到解析。这是因为花园路径结构可能会导致局部最优而非全局最优，这是DG分析中的一个挑战。 不连续语法及其局部成本函数处理复杂性分析和优化问题的方法，为理解自然语言提供了新的视角，但同时也揭示了语言理解和解析的复杂性，特别是对于那些需要深层结构分析的复杂语言现象。未来的研究可能继续探索更高效、更全面的算法，以克服花园路径问题并提高处理这类句子的能力。