2005/01/01 by Wei Luo · 1 voice
Computer Science · Mathematics · #Algorithm #Algorithms and Data Compression #Characterization (materials science) #Computer science #Conjecture #Discrete mathematics #Identification (biology) #Inclusion (mineral) #Machine Learning and Algorithms #Mathematics #Optics #Theoretical computer science #cs.FL #cs.LG #semigroups and automata theory
paper · pdf · doi:10.1007/11503415_48
openalex publication_date 2005/01/01 · openalex created_date 2025/10/10 · arxiv published 2026/05/28 · arxiv updated 2026/05/28 · openalex updated_date 2026/08/05
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 IDSigma(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, IDSigma(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.