求解模式语言包含深度，揭示学习复杂性本质。
The Inclusion Depth of Pattern Languages: An Open Problem in Algorithmic Learning Theory
- 提出模式语言包含深度定义，衡量学习过程中的思维转换次数。
- 给出包含深度的猜想公式：2|p| - #var(p) - 1，若成立可线性求解。
- 连接形式语言、组合词论与有限时间内学习的可识别性问题。
模式语言是形式语言理论和算法学习理论中的经典模型。本文提出计算模式语言包含深度的问题：从全集模式语言到给定模式生成语言之间严格包含链的最长长度。包含深度反映了仅凭正例进行模式识别时的思维转换复杂度。核心开放问题是：对任意有限字母表（至少两个符号）上的任意模式 p，包含深度 ID_Sigma(p) 是否可计算？是否可在多项式时间内计算？一个简单猜想公式为 ID_Sigma(p) = 2|p| - #var(p) - 1，若成立则可实现线性时间算法。该问题关联模式语言包含关系、词论组合、在极限下语言识别以及受限思维转换的学习。
原文摘要 · Abstract (English)
Pattern languages are a classical model in formal language theory and algorithmic learning theory. This note formulates the problem of computing the inclusion depth of a pattern language: the length of the longest strict inclusion chain from the universal pattern language to the language generated by a given pattern. Inclusion depth captures the mind-change complexity of pattern identification from positive data. The central open question is whether the inclusion depth ID_Sigma(p) is computable for every pattern p over every finite alphabet Sigma with at least two symbols, and whether it is computable in polynomial time. A simple conjectured formula, ID_Sigma(p) = 2|p| - #var(p) - 1, would imply a linear-time algorithm. The problem connects pattern language inclusion, combinatorics on words, language identification in the limit, and mind-change-bounded learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。