File(s) under permanent embargo
Compute inclusion depth of a pattern
conference contributionposted on 2005-01-01, 00:00 authored by Wei LuoWei Luo
We define a concept of inclusion depth (see Definition 1) to capture mind-change complexity [3,1] of pattern identification problems . 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.