Markov semigroups, monoids and groups. (Q2923337)

The authors extend the notions of a Markov/strongly Markov group to monoids and semigroups. Let \(M\) be a monoid and \(A\) its finite generating set. A Markov language for \(M\) over \(A\) is a regular prefix-closed language \(L\subseteq A^*\) that contains a unique representative for every element of \(M\). Additionally, if, for each \(x\in M\), the length of its representative in \(L\) is equal to the length of the shortest word over \(A\) representing \(x\), then \(L\) is called robust. A monoid \(M\) is (robustly) Markov with respect to a finite generating set \(A\) if there exists a (robust) Markov language for \(M\) over \(A\), and \(M\) is strongly Markov if, for every finite generating set \(A\) for \(M\), there exists a robust Markov language for \(M\) over \(A\). The definitions apply to the semigroup case mutatis mutandis; for instance, \(L\) should exclude the empty word in that case. The authors verify that for monoids the monoid and the semigroup versions of these definitions are equivalent.NEWLINENEWLINE The paper contains several results and examples that aim at clarifying the relations between Markov and strongly Markov monoids and other classes of finitely generated monoids specified by certain properties of their languages of representatives. In particular, the authors exhibit a non-Markov monoid that admits a regular language of unique representatives over any finite generating set and show that the classes of Markov, robustly Markov and strongly Markov monoids are distinct. If \(\langle A,\mathcal R\rangle\) is a confluent Noetherian rewriting system such that the set of left-hand sides of rewriting rules in \(\mathcal R\) is regular, then the presentation \(\langle A\mid\mathcal R\rangle\) defines a Markov monoid, and its language of normal forms is a Markov language. Finitely generated commutative semigroups are strongly Markov but there exists a virtually abelian group with a non-Markov subsemigroup. The authors also study closure properties of the classes of Markov monoids and semigroups with respect to adjoining 0 or 1, direct and free products and passing to finite Rees index extensions and subsemigroups.