💻 computer science

The Inclusion Depth of Pattern Languages: An Open Problem in Algorithmic Learning Theory

This paper introduces the open problem of determining whether the inclusion depth of pattern languages—a metric for mind-change complexity in learning from positive data—is computable for all patterns and whether a simple conjectured formula allows for a polynomial-time solution.

Original authors: Wei Luo

Published 2026-06-01

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Wei Luo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to sort a massive collection of strings (like words or codes) into different boxes. Some boxes are very general, holding almost anything, while others are very specific, holding only a few exact items.

This paper, written by Wei Luo, is essentially a detective story about a specific type of puzzle involving these "pattern boxes." The author is asking two big questions: Can we always calculate exactly how specific a pattern is? and Is there a simple math formula to figure this out without doing a million calculations?

Here is a breakdown of the paper's ideas using simple analogies:

1. The "Russian Nesting Doll" of Patterns

The core concept is called Inclusion Depth. Think of pattern languages like Russian nesting dolls.

The biggest doll is a "universal" pattern (like a blank canvas that can become anything).
Inside that, you can fit slightly more specific patterns.
Inside those, you fit even more specific ones, until you reach your final, very specific pattern.

The Inclusion Depth is simply the count of how many "steps" or "layers" you have to go down to get from the biggest, most general doll to your specific target doll.

The Example:
If your target pattern is 0x11 (where x is a variable that can be anything), the author shows you can build a chain of 5 dolls:

The biggest one (anything goes).
A slightly smaller one.
A medium one.
A smaller one.
Your specific target 0x11.

The "depth" here is 4 (the number of steps between the top and the bottom).

2. The Big Question: Is There a Shortcut?

The author asks: Can we write a computer program to count these steps for any pattern?

Currently, checking if one pattern fits inside another is known to be a "nightmare" for computers (mathematically, it's undecidable). However, the author suspects that for this specific counting problem, there might be a much easier way.

The "Magic Formula" Hypothesis:
The author proposes a simple equation that might solve the whole puzzle instantly:

Depth = (2 × Length of Pattern) − (Number of Unique Variables) − 1

Think of it like this:

Length: How long the string is.
Variables: How many "wildcards" (like x1, x2) are in it.

If this formula is true, you don't need to build the nesting dolls one by one. You just count the letters and the wildcards, plug them into the formula, and boom—you have the answer. This would turn a difficult, slow calculation into a lightning-fast one.

3. The Detective Work So Far

The author has tested this "Magic Formula" on small patterns (short strings).

The Good News: For short patterns (up to 7 characters long), the formula works perfectly every time.
The Bad News: The author couldn't test longer patterns because the computer calculations get too heavy and slow.

The author suspects that if the formula fails, the "culprit" must be a very long pattern (longer than 7 characters).

4. Why Does This Matter?

The paper mentions that this isn't just about math for math's sake. It relates to "mind-change complexity."

Imagine you are a student learning a rule.

If the rule is very general, you might guess wrong a lot before you get it right.
If the rule is very specific, you might figure it out quickly.

The "Inclusion Depth" measures how many times your mind might have to change its guess before you finally learn the correct pattern. If we can calculate the depth easily (using the formula), we can predict exactly how hard a learning problem will be and build better AI learners that don't waste time guessing.

Summary

The Goal: Find a way to count the "layers of specificity" in a pattern.
The Hope: There is a simple math formula (based on length and variable count) that gives the answer instantly.
The Status: The formula works for small examples, but the author hasn't proven it for all patterns yet. The paper is an open invitation for other mathematicians to prove (or disprove) this formula.

Technical Summary: Computing Inclusion Depth of a Pattern

Problem Definition
This note addresses the problem of computing the inclusion depth of a pattern language, a metric designed to capture the "mind-change complexity" inherent in pattern identification problems. The central inquiry is whether this depth is computable for any given pattern and, specifically, whether it admits a simple combinatorial characterization based on the pattern's structural properties.

Formally, let $X$ be a set of variables and $\Sigma$ a finite alphabet with at least two symbols. A pattern $p$ is a finite non-empty sequence over $X \cup \Sigma$ . The language $L_\Sigma(p)$ consists of all ground strings generated by substituting each variable in $p$ with a non-empty string from $\Sigma^+$ .

The inclusion depth, denoted $ID_\Sigma(p)$ , is defined as the length of the longest strict inclusion chain connecting the language of the universal pattern $L_\Sigma(x_1)$ to the language $L_\Sigma(p)$ . For instance, if $p = 0x_11$ over $\Sigma=\{0,1\}$ , the inclusion depth is 4, corresponding to a chain of four strict inclusions from $L_\Sigma(x_1)$ down to $L_\Sigma(0x_11)$ .

Methodology and Conjectures
The paper approaches the computability of inclusion depth by proposing a direct combinatorial formula. The author posits that the inclusion depth is determined solely by the length of the pattern ( $|p|$ ) and the number of distinct variables it contains ( $\#var(p)$ ).

The primary hypothesis, Question 2, suggests that for any alphabet $\Sigma$ with $|\Sigma| \geq 2$ :
$ID_\Sigma(p) = 2|p| - \#var(p) - 1$

If this equation holds, it implies the existence of a linear-time algorithm to compute inclusion depth, thereby answering Question 1 (the existence of a computable algorithm) in the affirmative.

To validate this formula, the paper introduces Conjecture 1, which establishes a necessary condition for pattern inclusion. It states that if the language of pattern $p$ is a strict subset of the language of pattern $q$ ( $L(p) \subset L(q)$ ), then the following inequality must hold:
$2|p| - \#var(p) > 2|q| - \#var(q)$

The author notes that the dependency on the specific alphabet $\Sigma$ can be reduced to the case where $\Sigma$ contains exactly two symbols, as inclusion relationships are preserved across subsets of the alphabet.

Results and Partial Solutions
The paper does not provide a formal proof of the conjectures but offers empirical evidence and theoretical context:

Undecidability Context: It is acknowledged that the general problem of deciding pattern inclusion is undecidable. However, the author argues that computing inclusion depth may not require solving the general inclusion problem for arbitrary pairs.
Empirical Verification: An exhaustive computation performed by the author's program confirmed that the inequality in Conjecture 1 holds for all patterns with a length less than or equal to 7.
Computational Limits: The verification for patterns longer than length 7 was deemed computationally impractical. Consequently, if a counterexample to the conjecture exists, it must involve patterns with a length greater than 7.

Significance and Claims
The significance of this work lies in its attempt to bridge the gap between the theoretical complexity of pattern identification and practical computability.

Mind-Change Complexity: The inclusion depth is intended to quantify the mind-change complexity of identifying patterns given initial evidence.
Algorithmic Implications: If the proposed combinatorial characterization (Equation 1) is proven true, it would enable the construction of a linear-time algorithm to compute inclusion depth.
Learner Construction: A positive resolution to the computability question would allow for the calculation of mind-change bounds for pattern identification problems and facilitate the construction of a uniformly mind-change optimal learner.

The paper concludes by framing the problem as an open question, inviting further research to either prove the combinatorial characterization or find a counterexample in longer patterns.