Algorithmics of Posets Generated by Words over Partially Commutative Alphabets⋆

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 graph-ical representation are Hasse diagrams. We will investigate this relation in detail and propose an efficient on-line algorithm that decompresses a string to Hasse diagram. Further we propose a definition of the canonical representatives of classes of equivalent words. The advantage of this representation lies in the fact that we can enumerate the classes of equivalent words in a lexicographical order. We will give an algorithm which enumerates all distinct classes of words over partially commutative alphabets by their lexicographically minimal representatives