JUCS - Journal of Universal Computer Science 10(8): 927-933, doi: 10.3217/jucs-010-08-0927
On the Intractability of Computing the Duquenne-Guigues Base
expand article infoSergei O. Kuznetsov‡
‡ All-Russia Institute for Scientific and Technical Information VINITI, Moscow, Russia

Corresponding author: Sergei Kuznetsov ( serge@viniti.ru )

© Sergei Kuznetsov.
This article is freely available under the J.UCS Open Content License.
Citation: Kuznetsov SO (2004) On the Intractability of Computing the Duquenne-Guigues Base. JUCS - Journal of Universal Computer Science 10(8): 927-933. https://doi.org/10.3217/jucs-010-08-0927
Open Access
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
implication base, computational complexity