The complexity of the emptiness problem for E0L systems. (English) Zbl 0769.68064

Lindenmayer systems. Impacts on theoretical computer science, computer graphics, and developmental biology, 167-175 (1992).
Summary: [For the entire collection see Zbl 0755.00005.]
The emptiness problem for EOL systems is shown to be computationally equivalent to the word problem of RPAC automata which are augmented with a LOGSPACE working tape and a two-way input head.


68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity


Zbl 0755.00005