Semi-commutations

A semi-commutation system \(S=<X,P>\) is a semi-Thue system, where X is a finite alphabet and P is a set of production rules of the form xy\(\to yx\) for some x,y\(\in X\), \(x\neq y\). The corresponding semi-commutation is the map which assigns to every set \(R\subseteq X^*\) of words over X the set f(R) of all words over X which can be derived from some member of R by means of the production rules in P. The paper contains two main results: a) If both \(f(R_ 1)\) and \(f(R_ 2)\) are regular then so is \(f(R_ 1R_ 2)\). b) \(f(R^*)\) is regular provided \(R=f(R)\) is regular and for every word \(\omega\) the directed graph \(\Gamma\) (\(\omega)\) is strongly connected, where \(\Gamma\) (\(\omega)\) is defined as follows: vertices are all letters \(x\in X\) occurring in \(\omega\). There is an edge \(x\to y'\) iff \(x\neq y\) and the production rule xy\(\to yx\) does not belong to P.

Recommendations

Cites work

Cited in

(38)

This page was built for publication: Semi-commutations

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