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 |