Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 10 / Issue 8

available in:   PDF (99 kB) PS (106 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-010-08-0927


On the Intractability of Computing the Duquenne-Guigues Base

Sergei O. Kuznetsov (All-Russia Institute for Scientific and Technical Information VINITI, Russia)

Abstract: Implications of a formal context (G, M, I) obey Armstrong rules, which allows for definition of a minimal (in the number of implications) implication base, called Duquenne-Guigues or stem base in the literature. A long-standing problem was that of an upper bound for the size of a stem base in the size of the relation I. In this paper we give a simple example of a relation where this boundary is exponential. We also prove #P-hardness of the problem of determining the size of the stem base (i.e., the number of pseudo-intents).

Keywords: computational complexity, implication base

Categories: F.2, H.2