# restricted homomorphism

Let $h$ be a homomorphism over an alphabet $\Sigma$. Let $L$ be a language over $\Sigma$. We say that $h$ is $k$-restricted on $L$ if

1. 1.

there is a letter $b\in\operatorname{Alpha}(L)$ such that no word in $L$ begins with $b$ and contains more than $k-1$ consecutive occurrences of $b$ in it,

2. 2.

for any $a\in\operatorname{Alpha}(L)$,

 $h(a)=\left\{\begin{array}[]{ll}\lambda&\textrm{if }a=b\\ a&\textrm{otherwise.}\end{array}\right.$

Here, $\operatorname{Alpha}(L)$ is the set of all letters in $\Sigma$ that occur in words of $L$.

It is easy to see that any $k$-restricted homomorphism on $L$ is a $k$-linear erasing on $L$, for if $u\in L$ is a non-empty word, then we may write $u=v_{1}b^{m_{1}}v_{2}b^{m_{2}}\cdots v_{n}b^{m_{n}}$, where each $0, and each $v_{i}$ is a non-empty word not containing any occurrences of $b$. Then

 $|u|=|v_{1}\cdots v_{n-1}|+\sum_{i=1}^{n}m_{i}\leq|h(u)|+n(k-1)\leq|h(u)|+(k-1)% |h(u)|=k|h(u)|.$

Note that $n\leq|h(u)|$ since $1\leq|v_{i}|$ for each $i=1,\ldots,n$. A $k$-linear erasing is in general not a $k$-restricted homomorphism, an example of which is the following: $L=\{a,ab\}^{*}$ and $h:\{a,b\}\to\{a,b\}$ given by $h(a)=a^{2}$ and $h(b)=\lambda$. Then $h$ is a $1$-linear erasing, but not a $1$-restricted homomorphism, on $L$.

A family $\mathscr{F}$ of languages is said to be closed under restricted homomorphism if for every $L\in\mathscr{F}$, and every $k$-restricted homomorphism $h$ on $L$, $h(L)\in\mathscr{F}$. By the previous paragraph, we see that if $\mathscr{F}$ is closed under linear erasing, it is closed under restricted homomorphism. The converse of this is not necessarily true.

## References

• 1 A. Salomaa, , Academic Press, New York (1973).
Title restricted homomorphism RestrictedHomomorphism 2013-03-22 18:59:11 2013-03-22 18:59:11 CWoo (3771) CWoo (3771) 7 CWoo (3771) Definition msc 68Q45 $k$-restricted homomorphism k-restricted homomorphism LinearErasing