×

Optimal impliciational bases for finite modular lattices. (English) Zbl 0963.06006

Summary: Each finite closure system, whence each finite lattice, can be described in terms of “implicational bases” (called “covers of functional dependencies” in relational database theory). Although an NP-complete problem in general, it turns out that for modular lattices an optimal implicational base can be computed in polynomial time.

MSC:

06C05 Modular lattices, Desarguesian lattices
68P15 Database theory
06A07 Combinatorics of partially ordered sets
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI