Formal languages defined by uniform substitutions

Jean Camille Birget, Joseph B. Stephen

Research output: Contribution to journalArticle

2 Scopus citations

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 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.

Original languageEnglish (US)
Pages (from-to)243-258
Number of pages16
JournalTheoretical Computer Science
Volume132
Issue number1-2
DOIs
StatePublished - Sep 26 1994
Externally publishedYes

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