The lattices of prefixes and overlaps of traces (Q1815323)

Traces are considered. A partially commutative alphabet is a pair \((A,I)\), where \(A\) is a finite alphabet and \(I\subseteq A\times A\) is a symmetric and irreflexive binary relation on \(A\), called the independence relation. By \(A^*\) the free monoid over \(A\) is denoted. The symbol \(\equiv\) denotes the congruence on \(A^*\) generated by the set of pairs \(\{(ab,ba)\mid (a,b)\in I\}\), and the quotient monoid \(M(A,I)=A^*/\equiv\) is called the trace monoid. Its elements are called traces. A prefix of a trace is a left factor in the trace monoid and a suffix is a right factor. The prefixes form a lattice with respect to a certain order called prefix order. If a prefix of a trace is also a suffix, it is called an overlap of this trace; the overlaps also form a lattice. The lattices of prefixes and of overlaps are studied. Among the results, it is proved that every finite distributive lattice is isomorphic to the prefix lattice of some trace, and a necessary and sufficient condition for a lattice to be isomorphic to the overlap lattice of a trace is stated.