Closure properties of certain classes of languages under generalized morphic replication

Z. Fang, J. S. Deogun

Research output: Contribution to journalArticlepeer-review


In this paper a new language operator, a generalized morphic replication, is introduced. Let Ω be a finite set of morphisms and reversal morphisms from ∑* into Δ*, and ω be in Ω*. A morphic replicator is defined as follows: for each x in ∑* define ω(x) to be h1(x) ... hm(x), where |ω| = m and ω = h1 ... hm. A generalized morphic replication extends ω to languages by ω(L) = {ω(x): x is in L} and to sets W of morphic replicators, where W ⊆ Ω*, W(x) = {ω(x): ω is in W} and W(L) = UW(x), where the union is taken over all x in L.It is shown that the class of languages accepted in real time by a non-deterministic reversal-bounded multitape Turing machine, the class of NP, and the class of the recursively enumerable sets, are all closed under the generalized morphic replication when the morphisms and the reversal morphisms are, respectively, linear-erasing, polynomial-erasing, and arbitrary.

Original languageEnglish (US)
Pages (from-to)325-329
Number of pages5
JournalComputer Journal
Issue number4
StatePublished - Aug 1988

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'Closure properties of certain classes of languages under generalized morphic replication'. Together they form a unique fingerprint.

Cite this