The Inclusion Depth of Pattern Languages: An Open Problem in Algorithmic Learning Theory
This work poses a new open problem for researchers in algorithmic learning theory and formal language theory, specifically regarding the computability and complexity of pattern language inclusion depth.
This paper introduces the problem of computing the inclusion depth of a pattern language, which measures the length of the longest strict inclusion chain from the universal pattern language to a language generated by a given pattern. The core question is whether this inclusion depth, ID_Sigma(p), is computable for any pattern p over any finite alphabet Sigma with at least two symbols, and if so, whether it can be computed in polynomial time.
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.