When a uniform substitution is applied to a word, the same letter at different positions in the word is transformed everywhere in the same way. Thus, a uniform substitution SH is determined by a set H of homomorphisms. We define recognizable and rational sets of homomorphisms and we prove closure and non-closure properties of the class of languages of the form SH(L), where L is regular and H is recognizable. We also show that in this case (and in more general situations as well) the membership problem for SH(L) is solvable in deterministic polynomial time.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Computer Science(all)