Algorithmics of Posets Generated by Words Over Partially Commutative Alphabets (Extended)

Abstract

It is natural to try to relate partially ordered sets (posets in short) and classes of equivalent words over partially commutative alphabets. Their common graphical representation are Hasse diagrams. We investigate this relation in detail and propose an efficient online algorithm that decompresses a concurrent word to its Hasse diagram. The lexicographically minimal representative of an equivalence class of words is called the lexicographical normal form of this class. We give an algorithm which enumerates, in the lexicographical order, all distinct classes of words identified by their lexicographical normal forms. The two presented algorithms are the main contribution of this paper.