Some Complexity Results about Essential Closed Sets

Felix DistelFelix Distel

Download

Felix Distel
Some Complexity Results about Essential Closed Sets
In Petko {Valtchev} and Robert {J{\"{}a}schke}, eds., International Conference on Formal Concept Analysis, volume 6628 of LNCS, 81--92, 2011

Details
Bibtex

KurzfassungAbstract
We examine the enumeration problem for essential closed sets of a formal context. Essential closed sets are sets that can be written as the closure of a pseudo-intent. The results for enumeration of essential closed sets are similar to existing results for pseudo-intents, albeit some differences exist. For example, while it is possible to compute the lectically first pseudo-intent in polynomial time, we show that it is not possible to compute the lectically first essential closed set in polynomial time unless P = NP. This also proves that essential closed sets cannot be enumerated in the lectic order with polynomial delay unless P = NP. We also look at minimal essential closed sets and show that they cannot be enumerated in output polynomial time unless P = NP.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ Diste11,
  author = {Felix {Distel}},
  booktitle = {International Conference on Formal Concept Analysis},
  editor = {Petko {Valtchev} and Robert {J{\"{}a}schke}},
  pages = {81--92},
  series = {LNCS},
  title = {Some Complexity Results about Essential Closed Sets},
  volume = {6628},
  year = {2011},
}