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.
G. Markowsky and L. Markowsky, "Lattice Data Analytics: The Poset of Irreducibles and the MacNeille Completion," Proceedings of the 10th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems (2019, Metz, France), vol. 1, pp. 263 - 268, Institute of Electrical and Electronics Engineers (IEEE), Sep 2019.
The definitive version is available at https://doi.org/10.1109/IDAACS.2019.8924393
10th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications, IDAACS 2019 (2019: Sep. 18-21, Metz, France)
Keywords and Phrases
Dynamic algorithms (key words); Lattice data analytics; MacNeille completion; Poset of irreducibles
International Standard Book Number (ISBN)
Article - Conference proceedings
© 2019 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
01 Sep 2019