You are here
Home ›restricted homomorphism
Primary tabs
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 ,
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).
Mathematics Subject Classification
68Q45 Formal languages and automata- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)
- Other useful stuff
Recent Activity
new correction: typo? by Filipe
May 22
new question: Linear Algebra Combination Problem! by Aleph Zero
new question: Computation of $\varphi(2000)$ by unlord
May 21
new question: pure subgroups by lvoyster
new correction: Typo in M\"obius function? by Aleph Zero
new collection: analytic number theory by Aleph Zero
May 20
new question: Taylor's Series Query! by unlord
new question: Laplace transform by J
new question: Residue Calculus by J
May 19
new Education: Project: PlanetMath Outlines Series by unlord


