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.

Description

SpringerLink - Order, Volume 18, Number 4

Links and resources

Tags

community

  • @johirth
  • @dblp
  • @mboley
@mboley's tags highlighted