restricted homomorphism


Let h be a homomorphismPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath over an alphabet Σ. Let L be a languagePlanetmathPlanetmath over Σ. We say that h is k-restricted on L if

  1. 1.

    there is a letter bAlpha(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 aAlpha(L),

    h(a)={λif a=baotherwise.

Here, Alpha(L) is the set of all letters in Σ 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 uL is a non-empty word, then we may write u=v1bm1v2bm2vnbmn, where each 0<mik-1, and each vi is a non-empty word not containing any occurrences of b. Then

|u|=|v1vn-1|+i=1nmi|h(u)|+n(k-1)|h(u)|+(k-1)|h(u)|=k|h(u)|.

Note that n|h(u)| since 1|vi| for each i=1,,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}{a,b} given by h(a)=a2 and h(b)=λ. Then h is a 1-linear erasing, but not a 1-restricted homomorphism, on L.

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

References

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