linear erasing

It is well-known that, among all of the language families in the Chomsky hierarchy, the family $𝒮$ of context-sensitive languages is the only one that is not closed under arbitrary homomorphisms. Nevertheless, $𝒮$ is shown to be closed under a more restricted class of homomorphisms, namely the $\lambda$-free homomorphisms. Question: can we enlarge this class of homomorphisms so that $𝒮$ is still closed under the larger class? The answer is yes.

Definition. Let $L$ be a language over an alphabet $\mathrm{\Sigma }$, $h$ a homomorphism over $\mathrm{\Sigma }$, and $k$ a non-negative integer. $h$ is said to be a $k$-linear erasing on $L$ if for any word $u\in L$, we have

$$|u|\le k|h(u)|,$$

where $|u|$ stands for the length of $u$.

It is clear that if $h$ is a $k$-linear erasing on $L$, then it is a $m$-linear erasing for any $m\ge k$. Also, if $h$ is a $0$-linear erasing on $L$, then $L$ is either $\{\lambda \}$, or the empty set $\mathrm{\varnothing }$. In addition, if $h$ is a $k$-linear erasing on $L$, and $L^{\prime }\subseteq L$, then it is a $k$-linear erasing on $L^{\prime }$. Consequently, any $\lambda$-free homomorphism is a $k$-linear erasing on any $L$ over $\mathrm{\Sigma }$, for any $k\ge 1$.

However, the notion of linear erasing is language dependent. For example, let $\mathrm{\Sigma }=\{a,b,c\}$. Let $L_1=\{a^n{b}^n\mid n\ge 0\}$ and $L_2=\{a^n{c}^n\mid n\ge 0\}$. Suppose $h$ is the homomorphism on ${\mathrm{\Sigma }}^{*}$ with $h(a)=\lambda$, $h(b)=b^2$ and $h(c)=c$. Then $h$ is a $1$-linear erasing on $L_1$, and a $2$-linear erasing on $L_2$.

Definition Let $ℒ$ be a family of languages over $\mathrm{\Sigma }$. Then $ℒ$ is said to be closed under linear erasing if for any $L\in ℒ$, and any homomorphism $h$ which is a $k$-linear erasing on $L$ for some $k\ge 0$, then $h(L)\in ℒ$.

Clearly, if $ℒ$ is closed under homomorphism, it is closed under linear erasing, and thus the families of regular (http://planetmath.org/RegularLanguage), context-free, and type-0 languages are all closed under linear erasing. We also have the following:

Theorem 1.

The family $\mathrm{S}$ of context-sensitive languages is closed under linear erasing.

Remark. The theorem above can be generalized. Call a substitution $s$ over $\mathrm{\Sigma }$ a $k$-linear erasing on a language $L$ if $|u|\le k|v|$ for any $v\in s(u)$. If $L$ is context-sensitive such that $s(u)$ is context-sensitive for each $u\in L$, then $s(L)$ is context-sensitive provided that $s$ is a $k$-linear erasing on $L$.

Title	linear erasing
Canonical name	LinearErasing
Date of creation	2013-03-22 18:58:54
Last modified on	2013-03-22 18:58:54
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	8
Author	CWoo (3771)
Entry type	Definition
Classification	msc 68Q70
Synonym	limited erasing
Related topic	RestrictedHomomorphism