On the complexity of enumerating pseudo-intents

Felix DistelFelix Distel, Barış SertkayaBarış Sertkaya

Felix Distel, Barış Sertkaya
On the complexity of enumerating pseudo-intents
Discrete Applied Mathematics, 159(6):450-466, 2011

Details
Bibtex

KurzfassungAbstract
We investigate whether the pseudo-intents of a given formal context can efficiently be enumerated. We show that they cannot be enumerated in a specified lexicographic order with polynomial delay unless P = NP. Furthermore we show that if the restriction on the order of enumeration is removed, then the problem becomes at least as hard as enu- merating minimal transversals of a given hypergraph. We introduce the notion of minimal pseudo-intents and show that recognizing minimal pseudo-intents is polynomial. Despite their less complicated nature, surprisingly it turns out that minimal pseudo-intents cannot be enumerated in output-polynomial time unless P = NP.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@article{ DisSe11,
  author = {Felix {Distel} and Bar\i{}\c{s} {Sertkaya}},
  journal = {Discrete Applied Mathematics},
  number = {6},
  pages = {450--466},
  title = {On the complexity of enumerating pseudo-intents},
  volume = {159},
  year = {2011},
}