Lattice Data Analytics: The Poset of Irreducibles and the MacNeille Completion


Automated and semi-automated systems that derive actionable information from massive, heterogeneous datasets are essential for many applications. The reasoning of such systems must be as clear as possible in order to earn our trust. Lattices have begun to play a key role in computer science finding applications in distributed computing, programming languages, concurrency theory, and data mining, thereby justifying G. C. Rota's belief that lattice theory will play an important role in 21st Century mathematics. In some instances, researchers must deal with posets that are not necessarily lattices and the question arises how these posets can be embedded in lattices. A classic way to answer this question is to construct the MacNeille completion of the lattice, which is the most compact way to embed a poset into a lattice. In 1973 G. Markowsky introduced the poset of irreducibles construction in his dissertation and demonstrated that this was a very compact way to represent a lattice. In addition, the poset of irreducibles has many of the properties of the poset of join-irreducibles of distributive lattices that was introduced by G. Birkhoff and described in his book. In this paper, we show how to construct the poset of irreducibles for the MacNeille completion of a poset efficiently. We conclude with some applications of these ideas.

Meeting Name

10th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications, IDAACS 2019 (2019: Sep. 18-21, Metz, France)


Computer Science

Keywords and Phrases

Dynamic algorithms (key words); Lattice data analytics; MacNeille completion; Poset of irreducibles

International Standard Book Number (ISBN)


Document Type

Article - Conference proceedings

Document Version


File Type





© 2019 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

01 Sep 2019