Conditional Lindenmayer systems with subregular conditions: The non-extended case

¹ Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik, PSF 4120, 39016 Magdeburg, Germany
dassow@iws.cs.uni-magdeburg.de
² Fliederweg 7b, 65527 Niedernhausen, Germany

Received: 2 February 2013
Accepted: 14 March 2014

Abstract

We consider conditional tabled Lindenmayer sytems without interaction, where each table is associated with a regular set and a table can only be applied to a sentential form which is contained in its associated regular set. We study the effect to the generative power, if we use instead of arbitrary regular languages only finite, nilpotent, monoidal, combinational, definite, ordered, union-free, star-free, strictly locally testable, commutative regular, circular regular, and suffix-closed regular languages. Essentially, we prove that the hierarchy of language families obtained from conditional Lindenmayer systems with subregular conditions is almost identical to the hierarchy of families of subregular languages.