Nonlinear Sciences – Cellular Automata and Lattice Gases
Scientific paper
1998-01-17
Nonlinear Sciences
Cellular Automata and Lattice Gases
11 pages in AmsTex, no figures
Scientific paper
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 1) The set of languages, computed in a polynomial time on such LS that all replacing words are not empty, is exactly NP- languages. 2) The set of languages, computed in a polynomial time on arbitrary LS, contains the polynomial hierarchy. 3) 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 $n^a$, 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.
No associations
LandOfFree
Lindenmayer systems as a model of computations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Lindenmayer systems as a model of computations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lindenmayer systems as a model of computations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-224725