On the Word Problem for Special Monoids

DOI10.1007/S00233-022-10286-2arXiv2011.09466MaRDI QIDQ6354052FDOQ6354052

Publication date: 18 November 2020

Abstract: A monoid is called special if it admits a presentation in which all defining relations are of the form

w = 1

. Every group is special, but not every monoid is special. In this article, we describe the language-theoretic properties of the word problem, in the sense of Duncan & Gilman, for special monoids in terms of their group of units. We prove that a special monoid has context-free word problem if and only if its group of units is virtually free, giving a full generalisation of the Muller-Schupp theorem. This fully answers, for the class of special monoids, a question posed by Duncan & Gilman in 2004. We describe the congruence classes of words in a special monoid, and prove that these have the same language-theoretic properties as the word problem. This answers a question first posed by Zhang in 1992. As a corollary, we prove that it is decidable (in polynomial time) whether a special one-relation monoid has context-free word problem. This completely answers another question from 1992, also posed by Zhang.

Mathematics Subject Classification ID

Ordered semigroups and monoids (06F05) Free semigroups, generators and relations, word problems (20M05)

This page was built for publication: On the Word Problem for Special Monoids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6354052)