کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435734 | 689931 | 2010 | 10 صفحه PDF | دانلود رایگان |
We study the problem of listing all closed sets of a closure operator σ that is a partial function on the power set of some finite ground set E, i.e., σ:F→F with F⊆P(E). A very simple divide-and-conquer algorithm is analyzed that correctly solves this problem if and only if the domain of the closure operator is a strongly accessible set system. Strong accessibility is a strict relaxation of greedoids as well as of independence systems. This algorithm turns out to have delay O(|E|(TF+Tσ+|E|)) and space O(|E|+SF+Sσ), where TF, SF, Tσ, and Sσ are the time and space complexities of checking membership in F and computing σ, respectively. In contrast, we show that the problem becomes intractable for accessible set systems. We relate our results to the data mining problem of listing all support-closed patterns of a dataset and show that there is a corresponding closure operator for all datasets if and only if the set system satisfies a certain confluence property.
Journal: Theoretical Computer Science - Volume 411, Issue 3, 6 January 2010, Pages 691-700