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"aschke, 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},
}