Characterizations of Recursively Enumerable Languages by Using Copy Languages
Gheorghe Pǎun, Arto K. Salomaa · 1997
We give characterizations of recursively enumerable languages starting from copy languages, that is languages of the form fxx j x 2 Lg, where L is a regular language and x is the barred version of x. One characterization uses an intersection of morphic images of two copy languages, the other one uses a quotient of morphic images of two copy languages. As a consequence, we find similar characterizations of recursively enumerable languages starting from languages generated by (non-returning non-centralized) parallel communicating grammar systems with right-linear rules.