CLOSURE PROPERTY OF CERTAIN CLASSES OF LANGUAGES ENDER BI-LANGUAGE FORM
Zhou Fang · Chinese Journal of Computers · 1982
Let H be a language over alphabet Ω and L a language over alphabet Σ, each symbol in Ω being a homomorphism or an anti-homomorphism on L. The set H(L) = {X(w)\Xe.H, WeL} is said to be a bi-language form. In this paper it is shown that the class of language accepted in real time by nondeterministic reversal-bounded multitape Turing machines, NP and the class of the recursively enumerable sets are closed under bi-language form operations when the homomorphisms are linear-erasing, polynomial-erasing and arbitrary respectively.