Commutative semigroups with a context-free word problem

Free semigroups, generators and relations, word problems (20M05) Commutative semigroups (20M14) Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45)

Review text

Let \(M\) be a commutative monoid generated by a finite set \(A\) that does not contain \(\#\). Consider a language \(L\), consisting of all words of form \(u\#v^R ,\) where \(u,v\) are non-empty words in the alphabet \(A\cup\{\#\}\) such that \(u=v\) in \(M,\) and \(v^R\) is the word \(v\) written in the opposite order.\N\NThe main result is that \(L\) is context-free if and only if \(M\) does not contain a free commutative monoid on two generators as a submonoid. A similar result is obtained for the semigroups.\N\NThe article contains many other interesting results about such monoids, e.g. that for any \(a,b\in M\) there exists a non-negative \(q\) such that at least one of the following equalities holds in M:\N\begin{itemize}\N\item[(1)] \((a^qb^q)a^s=a^qb^q\) for some positive integer \(s;\)\N\item[(2)] \((a^qb^q)b^s=a^qb^q\) for some positive integer \(s;\)\N\item[(3)] \((a^qb^q)a^s=(a^qb^q)b^t\) for some positive integers \(s,t\);\N\item[(4)] \((a^qb^q)a^sb^t=(a^qb^q)\) for some positive integers \(s,t\).\N\end{itemize}

Cites work

This page was built for publication: Commutative semigroups with a context-free word problem

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