We show that grammar systems with communication by command and with ex
tremely simple rewriting rules (in fact, only relabelings are needed)
are able to generate all recursively enumerable languages. The result
settles several open problems in the area of grammar systems. We also
present the result in a general framework, without referring to gramma
r systems, obtaining a characterization of recursively enumerable lang
uages from a new point of view. (C) 1998 Academic Press.