On a generalization of partial commutations. (English) Zbl 0593.68058

Topics in the theoretical bases and applications of computer science, Proc. 4th Hung. Conf., Györ/Hung. 1985, 15-24 (1986).
Summary: [For the entire collection see Zbl 0578.00003.]
We extend the notion of partial commutation by introducing that of semi- commutation which is its non-symmetrical version. A semi-commutation function f is associated to a semi-Thue system \(<X,P>\) where the rules are of the form yx\(\to xy\) with x,y\(\in X\). We study this operation in connection with rational operations. We prove that if f(R) and f(R’) are regular languages, then f(RR’) is a regular language and we give a sufficient condition which insures that \(f(R^*)\) is a regular language.


68Q45 Formal languages and automata


Zbl 0578.00003