Remarks on accepting parallel systems

Abstract

We investigate three parallel rewriting mechanisms (Lindenmayer systems, uniformly limited Linden-mayer systems and limited Lindenmayer systems) combined with the extension mechanism considered as accepting devices, in contrast with the usual generating mode. Generally speaking, the accepting mode is at least as powerful as the generating mode, but mostly the accepting mode is just as powerful as the generating mode. Contrary to this, in case of 11ET0L systems, we even obtain a new characterization of the enumerable languages. Moreover, we show that uniformly limited propagating systems can be simulated by programmed grammars without erasing and without appearance checking, hence improving a result in [18]. Furthermore, we briefly discuss the degree of nondeterminism and the degree of synchronization for these devices.

Keywords:

• Formal languages
• parallel rewriting
• accepting and generating rewriting systems