Overlaps in free partially commutative monoids (Q2639969)

A free partially commutative monoid M(\(\Sigma\),\(\Theta\)) is given through a finite alphabet \(\Sigma\) and an independence relation \(\Theta\subseteq \Sigma \times \Sigma\), which is symmetric and irreflexive. Then M(\(\Sigma\),\(\Theta\)) is the quotient monoid \(\Sigma^*/\equiv\), where \(\equiv\) denotes the Thue congruence induced by the commutation rules \(T_{\Theta}=\{(ab,ba)|\) (a,b)\(\in \Theta \}\). The subject of this paper is the set of overlaps of elements in free partially commutative monoids, and the focus is on how properties of overlaps in free monoids generalize to this situation. For a word \(u\in \Sigma^*\) let alph(u) denote the set of letters that occur in u. The trace [u] is a connected element of M(\(\Sigma\),\(\Theta\)) if alph(u) cannot be decomposed as \(alph(u)=A_ 1\cup A_ 2\), \(A_ 1\neq \emptyset \neq A_ 2\), such that \(A_ 1\times A_ 2\subseteq \Theta\). For \(x\in \Sigma^*\), \(OVL([x])=\{[u]|\) \(x\equiv uv_ 1\equiv v_ 2u\) for some \(v_ 1,v_ 2\neq e\}\) is the set of congruence classes of overlaps of [x] in the monoid M(\(\Sigma\),\(\Theta\)). The following results are obtained. For each element [x], the set of congruence classes OVL([x])\(\cup \{[x]\}\) is a lattice under the prefix-ordering \(\leq\) in M(\(\Sigma\),\(\Theta\)). If [x] is a connected element, then OVL([x]) is already a lattice under \(\leq\) (Theorem 3.3). If [x] is not connected, then the lattice OVL([x])\(\cup \{[x]\}\) is the direct product of the lattices \(OVL([x_ i])\), each with a new ``top'' element \([x_ i]\) adjoined, where the \([x_ i]\) are the connected components of [x]. Finally, an algorithm is presented that, given a connected element [x] as input, determines a maximum overlap of [x] in time linear in the length of x (Theorem 4.3).