Hardness of Enumerating Pseudo-Intents in the Lectic Order

Felix DistelFelix Distel

Download

Felix Distel
Hardness of Enumerating Pseudo-Intents in the Lectic Order
In Barış Sertkaya and Léonard Kwuida, eds., Proceedings of the 8th International Conference on Formal Concept Analysis, (ICFCA 2010), volume 5986 of Lecture Notes in Artificial Intelligence, 124-137, 2010. Springer

Details
Bibtex

KurzfassungAbstract
We investigate the complexity of enumerating pseudo-intents in the lectic order. We look at the following decision problem: Given a formal context and a set of n pseudo-intents determine whether they are the lectically first n pseudo-intents. We show that this problem is coNP-hard. We thereby show that there cannot be an algorithm with a good theoretical complexity for enumerating pseudo-intents in a lectic order. In a second part of the paper we introduce the notion of minimal pseudo-intents, i.e. pseudo-intents that do not strictly contain a pseudo-intent. We provide some complexity results about minimal pseudo-intents that are readily obtained from the previous result.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

The final publication is available at Springer.

@inproceedings{ Distel-ICFCA-10,
  author = {Felix {Distel}},
  booktitle = {Proceedings of the 8th International Conference on Formal Concept Analysis, (ICFCA 2010)},
  editor = {Bar\i{}{\c{s}} {Sertkaya} and L\'eonard {Kwuida}},
  pages = {124--137},
  publisher = {Springer},
  series = {Lecture Notes in Artificial Intelligence},
  title = {Hardness of Enumerating Pseudo-Intents in the Lectic Order},
  volume = {5986},
  year = {2010},
}