Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.30389 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917544966750208 |
|---|---|
| author | Luo, Wei |
| author_facet | Luo, Wei |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_30389 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Inclusion Depth of Pattern Languages: An Open Problem in Algorithmic Learning Theory Luo, Wei Formal Languages and Automata Theory Machine Learning F.4.3; F.1.1; I.2.6 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. |
| title | The Inclusion Depth of Pattern Languages: An Open Problem in Algorithmic Learning Theory |
| topic | Formal Languages and Automata Theory Machine Learning F.4.3; F.1.1; I.2.6 |
| url | https://arxiv.org/abs/2605.30389 |