Semicommutations and algebraic languages (Q1199527): Difference between revisions

Let \(\theta\) be a binary irreflexive relation over an alphabet \(X\) (semi- commutation relation) and let \(P\) be a rewriting system with the rules \(\{ab\to ba\mid\;(a,b)\in\theta\}\). For a language \(L\subseteq X^*\), \(f_ \theta(L)\) denotes the set of all words that can be obtained from elements of \(L\) by means of \(P\). The authors show that it is possible to decide if for a given \(\theta\) the family \(\{f_ \theta(L)\mid\;L\) rational subset of \(X^*\}\) contains only algebraic languages.