%0 Journal Article %1 1393768 %A Kuznetsov, Sergei O. %A Obiedkov, Sergei %C Amsterdam, The Netherlands, The Netherlands %D 2008 %I Elsevier Science Publishers B. V. %J Discrete Appl. Math. %K complexity fca pseudo-intent theory %N 11 %P 1994--2003 %T Some decision and counting problems of the Duquenne-Guigues basis of implications %U http://portal.acm.org/citation.cfm?id=1393768 %V 156 %X Implications of a formal context obey Armstrong rules, which allows one to define a minimal (in the number of implications) implication basis, called Duquenne-Guigues basis or stem base in the literature. In this paper we show how implications are reduced to functional dependencies and prove that the problem of determining the size of the stem base is a #P-complete problem.