restricted homomorphism
Let be a homomorphism over an alphabet . Let be a language
over . We say that is -restricted on if
- 1.
there is a letter such that no word in begins with and contains more than consecutive occurrences of in it,
- 2.
for any ,
Here, is the set of all letters in that occur in words of .
It is easy to see that any -restricted homomorphism on is a -linear erasing on , for if is a non-empty word, then we may write , where each , and each is a non-empty word not containing any occurrences of . Then
Note that since for each . A -linear erasing is in general not a -restricted homomorphism, an example of which is the following: and given by and . Then is a -linear erasing, but not a -restricted homomorphism, on .
A family of languages is said to be closed under restricted homomorphism if for every , and every -restricted homomorphism on , . By the previous paragraph, we see that if is closed under linear erasing, it is closed under restricted homomorphism. The converse
of this is not necessarily true.
References
- 1 A. Salomaa, Formal Languages
, Academic Press, New York (1973).