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

We define a concept of inclusion depth (see Definition 1) to capture mind-change complexity [3,1] of pattern identification problems [2]. Our basic question is whether the inclusion depth for any pattern is computable. We conjecture a combinatorial characterization that, if true, leads to a linear time algorithm to compute inclusion depth.