Remarks on formal languages and the model theory of monoids

Christopher D. C. Hawthorne

Published 2018-03-20Version 1

Given a monoid $(M,\cdot ,\epsilon )$ that is freely generated on a finite set $\Sigma $, it is shown that the quantifier-free definable subsets of $M$ form a proper subclass of the star-free languages over $\Sigma $. Furthermore, a subset $A\subseteq M$ is shown to be a regular language over $\Sigma $ if and only if the $\phi $-rank of $x=x$ is zero, where $\phi (x; v)$ is the formula $xv\in A$. This latter result is extended to arbitrary monoids with recognizable subsets replacing regular languages.