Semicommutations and algebraic languages (Q1199527)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Semicommutations and algebraic languages |
scientific article |
Statements
Semicommutations and algebraic languages (English)
0 references
16 January 1993
0 references
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.
0 references
algebraic languages
0 references