Recognizable subsets of some partially Abelian monoids (Q2266128): Difference between revisions

A free partially abelian monoid S is a monoid which has a finite alphabet A as generating set and in which all laws are of the form ab\(\simeq ba\) for some a,b\(\in S\). Let X be a finite set of words over A each containing all the letters of A at least once. Suppose that the graph the vertices of which are the letters of A and for which the edges correspond to non-commuting pairs of letters of A, is connected. Then the main theorem of the paper states that the subset \([X^*]\) of the free partially abelian monoid \(A^*/\simeq\) containing all the words equivalent to a product of words in X, is rational. Also, it is shown that the set of all words \(u\in A^*\) commuting with a given word \(w\in A^*\) (i.e. wu\(\simeq uw)\) is a rational, finitely generated subset of \(A^*\).