%0 Journal Article %1 kuznetsov/ord/2001 %A Kuznetsov, Sergei %D 2001 %I Springer Netherlands %J Order %K complexity counting formalConceptAnalysis %P 313-321 %R 10.1023/A:1013970520933 %T On Computing the Size of a Lattice and Related Decision Problems %U http://dx.doi.org/10.1023/A:1013970520933 %V 18 %X The problem of determining the size of a finite concept lattice is shown to be #P-complete. Since any finite lattice can be represented as a concept lattice, the problem of determining the size of a lattice given by the ordered sets of its irreducibles is also #P-complete. Some results about NP-completeness or polynomial tractability of decision problems related to concepts with bounded extent, intent, and the sum of both are given. These problems can be reformulated as decision problems about lattice elements generated by a certain amount of irreducibles.

@article{kuznetsov/ord/2001, abstract = {The problem of determining the size of a finite concept lattice is shown to be #P-complete. Since any finite lattice can be represented as a concept lattice, the problem of determining the size of a lattice given by the ordered sets of its irreducibles is also #P-complete. Some results about NP-completeness or polynomial tractability of decision problems related to concepts with bounded extent, intent, and the sum of both are given. These problems can be reformulated as decision problems about lattice elements generated by a certain amount of irreducibles.}, added-at = {2010-09-08T09:39:16.000+0200}, author = {Kuznetsov, Sergei}, biburl = {https://www.bibsonomy.org/bibtex/2006c90bc830390864c68231f8b9cc577/mboley}, description = {SpringerLink - Order, Volume 18, Number 4}, doi = {10.1023/A:1013970520933}, interhash = {919f81b52542d9dd6783623499511bb8}, intrahash = {006c90bc830390864c68231f8b9cc577}, issn = {0167-8094}, issue = {4}, journal = {Order}, keyword = {Mathematics and Statistics}, keywords = {complexity counting formalConceptAnalysis}, pages = {313-321}, publisher = {Springer Netherlands}, timestamp = {2010-09-08T09:39:16.000+0200}, title = {On Computing the Size of a Lattice and Related Decision Problems}, url = {http://dx.doi.org/10.1023/A:1013970520933}, volume = 18, year = 2001 }