RAIRO-Theor. Inf. Appl.
Volume 48, Number 1, January-March 2014Non-Classical Models of Automata and Applications (NCMA 2012)
|Page(s)||127 - 147|
|Published online||28 March 2014|
Conditional Lindenmayer systems with subregular conditions: The non-extended case
Otto-von-Guericke-Universität Magdeburg, Fakultät für
2 Fliederweg 7b, 65527 Niedernhausen, Germany
Received: 2 February 2013
Accepted: 14 March 2014
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.
Mathematics Subject Classification: 68Q42 / 68Q45
Key words: Lindenmayer systems / controlled derivations
© EDP Sciences 2014
Initial download of the metrics may take a while.