%0 Journal Article %1 keyhere %A Kuznetsov, Sergei %A Obiedkov, Sergei %D 2006 %J Formal Concept Analysis %K #P complexity fca pseudo-intent theory %P 306--308 %T Counting Pseudo-intents and #P-completeness %U http://dx.doi.org/10.1007/11671404_21 %X Implications of a formal context (G,M,I) have a minimal implication basis, called Duquenne-Guigues basis or stem base. It is shown that the problem of deciding whether a set of attributes is a premise of the stem base is in coNP and determining the size of the stem base is polynomially Turingequivalent to a #P-complete problem.

@article{keyhere, abstract = {Implications of a formal context (G,M,I) have a minimal implication basis, called Duquenne-Guigues basis or stem base. It is shown that the problem of deciding whether a set of attributes is a premise of the stem base is in coNP and determining the size of the stem base is polynomially Turingequivalent to a #P-complete problem.}, added-at = {2009-02-17T11:07:31.000+0100}, author = {Kuznetsov, Sergei and Obiedkov, Sergei}, biburl = {https://www.bibsonomy.org/bibtex/2de0a8419ab5d374012b9d05498f840b0/folke}, description = {Recognizing pseudo-intents is in coNP}, interhash = {621d51fff81b1ed566607b7e18480dbc}, intrahash = {de0a8419ab5d374012b9d05498f840b0}, journal = {Formal Concept Analysis}, keywords = {#P complexity fca pseudo-intent theory}, pages = {306--308}, timestamp = {2009-02-17T11:07:31.000+0100}, title = {Counting Pseudo-intents and #P-completeness}, url = {http://dx.doi.org/10.1007/11671404_21}, year = 2006 }