restricted homomorphism

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

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

2. for any $a\in \mathrm{Alpha}(L)$,

Here, $\mathrm{Alpha}(L)$ is the set of all letters in $\mathrm{\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}\mathrm{\cdots }{v}_n{b}^{m_n}$, where each , and each $v_i$ is a non-empty word not containing any occurrences of $b$. Then

$$|u|=|v_1\mathrm{\cdots }{v}_{n-1}|+\sum _{i=1}^n{m}_i\le |h(u)|+n(k-1)\le |h(u)|+(k-1)|h(u)|=k|h(u)|.$$

Note that $n\le |h(u)|$ since $1\le |v_i|$ for each $i=1,\mathrm{\dots },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 $ℱ$ of languages is said to be closed under restricted homomorphism if for every $L\in ℱ$, and every $k$-restricted homomorphism $h$ on $L$, $h(L)\in ℱ$. 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.

Title	restricted homomorphism
Canonical name	RestrictedHomomorphism
Date of creation	2013-03-22 18:59:11
Last modified on	2013-03-22 18:59:11
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	7
Author	CWoo (3771)
Entry type	Definition
Classification	msc 68Q45
Synonym	$k$-restricted homomorphism
Synonym	k-restricted homomorphism
Related topic	LinearErasing