Compute Inclusion Depth of a Pattern

Wei LuoCOLT 2005 · DOI

TL;DR

This paper introduces "inclusion depth" as a measure of complexity for pattern identification problems, aiming to quantify "mind-change" complexity. The authors pose the fundamental question of whether this inclusion depth is computable and conjecture a simple combinatorial formula relating it to a pattern's length and the number of distinct variables.

What Problem Does This Paper Address?

In pattern identification, we often deal with patterns that represent sets of strings. Understanding how complex it is to distinguish between these sets is crucial. The authors introduce "inclusion depth" as a metric to capture this complexity, specifically the "mind-change complexity" involved in identifying a pattern. This is analogous to how many times a learner might need to revise its hypothesis when presented with new examples. The core challenge is to determine if this inclusion depth can be efficiently computed and if it can be characterized by simple properties of the pattern itself, rather than requiring complex analysis of the languages the patterns represent.

Methods

The paper defines inclusion depth formally as the length of the longest strict inclusion chain of languages, starting from the universal language $L_\Sigma(x_1)$ and ending at the language of a given pattern $L_\Sigma(p)$. The authors then propose a conjecture that this inclusion depth can be computed using a simple formula: $ID_\Sigma(p) = 2|p| - \#var(p) - 1$, where $|p|$ is the length of the pattern and $\#var(p)$ is the number of distinct variables. To support this conjecture, they propose a related conjecture (Conjecture 1) stating that if $L_\Sigma(p) \subset L_\Sigma(q)$, then $2|p| - \#var(p) > 2|q| - \#var(q)$. Proving this would imply the computability and a linear-time algorithm for inclusion depth.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Inclusion Depth as a Complexity Measure: The paper formalizes a notion of complexity for pattern languages that directly relates to the "mind-change" required in learning scenarios. This provides a more nuanced understanding beyond simple language membership.
  • The Power of Combinatorial Characterization: The central hypothesis is that a complex language-theoretic property (inclusion depth) can be reduced to a simple combinatorial formula based on pattern length and variable count. This is a common goal in theoretical computer science, aiming for efficient algorithms.
  • Conjecture 1 as the Key: The paper hinges on Conjecture 1. If true, it elegantly links language inclusion to a simple arithmetic comparison of pattern properties, paving the way for efficient computation.

Key Results

The paper does not present definitive computational results but rather poses open questions and conjectures.

  • Open Questions:
    1. Is there an algorithm to compute $ID_\Sigma(p)$ for any pattern $p$ and alphabet $\Sigma$? If so, is there a polynomial-time algorithm?
  • Is the formula $ID_\Sigma(p) = 2|p| - \#var(p) - 1$ true for all patterns and alphabets with at least two symbols?
  • Empirical Support: The authors state that their program verified Conjecture 1 for patterns up to length 7, suggesting the conjecture might hold. However, computation for longer patterns was impractical.

Limitations and Future Work

  • Undecidability of Pattern Inclusion: The paper acknowledges that general pattern inclusion is undecidable, highlighting the importance of finding computable measures like inclusion depth.
  • Unproven Conjectures: The core of the paper relies on two unproven conjectures. The primary future work would be to prove or disprove these conjectures. If proven, it would lead to a linear-time algorithm for computing inclusion depth.
  • Alphabet Dependence: While the authors suggest the alphabet $\Sigma$ can be reduced to size two, the formal proof of this reduction is not detailed.
  • Computational Impracticality: The empirical verification of Conjecture 1 was limited by computational constraints for longer patterns, indicating that a direct brute-force approach to finding counterexamples is not feasible.

Summary updated

BibTeX
@inproceedings{luo2005compute,
  author = {Wei Luo},
  title = {{Compute Inclusion Depth of a Pattern}},
  booktitle = {Conference on Learning Theory},
  year = {2005},
  doi = {10.1007/11503415\_48},
}
Figure