Some Computational Problems Related to Pseudo-intents

Barış SertkayaBarış Sertkaya

Download

Barış Sertkaya
Some Computational Problems Related to Pseudo-intents
In Sébastien Ferré and Sebastian Rudolph, eds., Proceedings of the 7th International Conference on Formal Concept Analysis, (ICFCA 2009), volume 5548 of Lecture Notes in Artificial Intelligence, 130-145, 2009. Springer

Details
Bibtex

KurzfassungAbstract
We investigate the computational complexity of several decision, enumeration and counting problems related to pseudo-intents. We show that given a formal context and a subset of its set of pseudo-intents, checking whether this context has an additional pseudo-intent is in coNP, and it is at least as hard as checking whether a given simple hypergraph is not saturated. We also show that recognizing the set of pseudo-intents is also in coNP, and it is at least as hard as identifying the minimal transversals of a given hypergraph. Moreover, we show that if any of these two problems turns out to be coNP-hard, then unless P = NP, pseudo-intents cannot be enumerated in output polynomial time. We also investigate the complexity of finding subsets of a given Duquenne-Guigues Base from which a given implication follows. We show that checking the existence of such a subset within a specified cardinality bound is NP-complete, and counting all such minimal subsets is #P-complete.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

The final publication is available at Springer.

@inproceedings{ Sert09,
  author = {Bar\i{}\c{s} {Sertkaya}},
  booktitle = {Proceedings of the 7th International Conference on {F}ormal {C}oncept {A}nalysis, {(ICFCA 2009)}},
  editor = {S\'ebastien {Ferr\'e} and Sebastian {Rudolph}},
  pages = {130--145},
  publisher = {Springer Verlag},
  series = {Lecture Notes in Artificial Intelligence},
  title = {Some Computational Problems Related to Pseudo-intents},
  volume = {5548},
  year = {2009},
}