Semicommutations and algebraic languages

DOI10.1016/0304-3975(92)90086-UMaRDI QIDQ1199527zbMATH OpenFDO

Authors Mireille Clerbout, Yves Roos

Publication date 16 January 1993

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(92)90086-U

zbMATH Keywords

algebraic languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

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.

Recommendations

Cited in

(13)

This page was built for publication: Semicommutations and algebraic languages

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