Semicommutations and algebraic languages
type: Item
instance of: scholarly article
title: Semicommutations and algebraic languages
zbMATH Open document ID: 0756.68061
DOI: 10.1016/0304-3975(92)90086-U
author: Mireille Clerbout
author: Yves Roos
published in: Theoretical Computer Science
publication date: 1993-01-16T00:00:00Z
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.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 94452
zbMATH Keywords: algebraic languages
reviewed by: Wiesław Zielonka
MaRDI profile type: Publication
cites work: Combinatorial problems of commutation and rearrangements
cites work: Q3723719
cites work: Semi-commutations
cites work: Q3736919
cites work: Langages infinitaires et produit de mixage
cites work: Cônes rationnels commutatifs
cites work: Q4347974
cites work: Q3698316
cites work: Q3725561
cites work: On lexicographic semi-commutations
cites work: Q3738586
cites work: Q3774977
cites work: Notes on finite asynchronous automata
description: scientific article; zbMATH DE number 94452