### Abstract

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 S_{H} 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 S_{H}(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 S_{H}(L) is solvable in deterministic polynomial time.

Original language | English (US) |
---|---|

Pages (from-to) | 243-258 |

Number of pages | 16 |

Journal | Theoretical Computer Science |

Volume | 132 |

Issue number | 1-2 |

DOIs | |

State | Published - Sep 26 1994 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Formal languages defined by uniform substitutions'. Together they form a unique fingerprint.

## Cite this

Birget, J. C., & Stephen, J. B. (1994). Formal languages defined by uniform substitutions.

*Theoretical Computer Science*,*132*(1-2), 243-258. https://doi.org/10.1016/0304-3975(94)90235-6