LS is a particular type of computational processes simulating living tissue.
They use an unlimited branching process arising from the simultaneous
substitutions of some words instead of letters in some initial word. This
combines the properties of cellular automata and grammars. It is proved that
- The set of languages, computed in a polynomial time on such LS that all
replacing words are not empty, is exactly NP- languages.
- The set of languages, computed in a polynomial time on arbitrary LS,
contains the polynomial hierarchy.
- The set of languages, computed in a polynomial time on a nondeterministic
version of LS, strictly contains the set of languages, computed in a polynomial
time on Turing Machines with a space complexity na, where a is positive
integer.
In particular, the last two results mean that Lindenmayer systems may be even
more powerful tool of computations than nondeterministic Turing Machine.