TY - JOUR

T1 - Closure properties of certain classes of languages under generalized morphic replication

AU - Fang, Z.

AU - Deogun, J. S.

PY - 1988/8/1

Y1 - 1988/8/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=0024064031&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024064031&partnerID=8YFLogxK

U2 - 10.1093/comjnl/31.4.325

DO - 10.1093/comjnl/31.4.325

M3 - Article

AN - SCOPUS:0024064031

VL - 31

SP - 325

EP - 329

JO - Computer Journal

JF - Computer Journal

SN - 0010-4620

IS - 4

ER -