- Titel
- Some Computational Problems Related to Pseudo-intents
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:14-qucosa2-795104
- Schriftenreihe
- LTCS-Report
- Bandnummer
- 08-06
- Erstveröffentlichung
- 2008
- DOI
- https://doi.org/10.25368/2022.169
- Abstract (EN)
- 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 set of its 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 saturated. We also show that recognizing the set of pseudo-intents is also in conp and it is at least as hard as checking whether a given hypergraph is the transversal hypergraph of another 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.
- Freie Schlagwörter (DE)
- Duquenne-Guigues-Basis, Beschreibungslogik, Transversalität, Pseudo-Absichten
- Freie Schlagwörter (EN)
- Duquenne-Guigues Base, description logic, transversal, pseudo-intents
- Klassifikation (DDC)
- 004
- Klassifikation (RVK)
- ST 136
- Publizierende Institution
- Technische Universität Dresden, Dresden
- Version / Begutachtungsstatus
- angenommene Version / Postprint / Autorenversion
- URN Qucosa
- urn:nbn:de:bsz:14-qucosa2-795104
- Veröffentlichungsdatum Qucosa
- 16.06.2022
- Dokumenttyp
- Bericht
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis
CC BY 4.0