On the Complexity of Computing Generators of Closed Sets

Miki HermannMiki Hermann, Barış SertkayaBarış Sertkaya

Download

Miki Hermann, Barış Sertkaya
On the Complexity of Computing Generators of Closed Sets
In Raoul Medina and Sergei A. Obiedkov, eds., Proceedings of the 6th International Conference on Formal Concept Analysis, (ICFCA 2008), volume 4933 of Lecture Notes in Computer Science, 158-168, 2008. Springer

Details
Bibtex

KurzfassungAbstract
We investigate the computational complexity of some decision and counting problems related to generators of closed sets fundamental in Formal Concept Analysis. We recall results from the literature about the problem of checking the existence of a generator with a specified cardinality, and about the problem of determining the number of minimal generators. Moreover, we show that the problem of counting minimum cardinality generators is #.coNP-complete. We also present an incremental-polynomial time algorithm from relational database theory that can be used for computing all minimal generators of an implication-closed set.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

The final publication is available at Springer.

@inproceedings{ HeSe08,
  author = {Miki {Hermann} and Bar\i{}\c{s} {Sertkaya}},
  booktitle = {Proceedings of the 6th International Conference on {F}ormal {C}oncept {A}nalysis, {(ICFCA 2008)}},
  editor = {Raoul {Medina} and Sergei A. {Obiedkov}},
  pages = {158--168},
  publisher = {Springer Verlag},
  series = {Lecture Notes in Computer Science},
  title = {On the Complexity of Computing Generators of Closed Sets},
  volume = {4933},
  year = {2008},
}