‘Markov semigroups, monoids, and groups’
[with V. Maltcev]
International Journal of Algebra and Computation, 24, no. 5 (August 2014).
DOI: 10.1142/S021819671450026X. MR: 3254716. ZBL: 1325.20055.


A group is Markov if it admits a prefix-closed regular language of unique representatives with respect to some generating set, and strongly Markov if it admits such a language of unique minimal-length representatives over every generating set. This paper considers the natural generalizations of these concepts to semigroups and monoids. Two distinct potential generalizations to monoids are shown to be equivalent. Various interesting examples are presented, including an example of a non-Markov monoid that nevertheless admits a regular language of unique representatives over any generating set. It is shown that all finitely generated commutative semigroups are strongly Markov, but that finitely generated subsemigroups of virtually abelian or polycyclic groups need not be. Potential connections with word-hyperbolic semigroups are investigated. The interaction of various semigroup constructions with the classes of Markov and strongly Markov semigroups is studied. Several questions are posed.