Parallel Substitution on Words and Languages.
Adrian Atanasiu, Víctor Mitrana · Scientific Annals of Cuza University · 1993
Adrian ATANASIU, Victor MITRANAUniversity of Bucharest, Faculty of Mathematics,Academiei 14, 70109 Bucharest, ROMANIAAbstract. First, the paper presents some results concerning the decomposition ofa word. Next, one considers parallel substitutions of a subword of a given word withan other string. There are investigated some necessary and sucient conditions inorder to obtain the original word w after parallel substituting a word x by y and thensubstituting y by x.1.Preliminaries.To substitute a subword of a word with an other word is a generalisation of theinsertion and deletion operations introduced in [4].A substitution has been de nedas an operation on an alphabet; in this case a word must be substituted. In thisrespect, this type of substitutions can be viewed as a generalisation of the commonsubstitution mappings.This paper is a continuation of [2] where the sequential substitution was investi-gated.In the sequel, the basic notions and notations will be presented. For formal lan-guages details, the reader is referred to [3],[6]. An alphabet is a nite nonempty set;if V = fa