Lindenmayer systems (L-systems) are parallel string rewriting systems (grammars). By attaching a graphical interpretation to the symbols in the derived strings, they can be applied to create simulations of temporal processes, and have been especially successful in the modeling of plants. With the objective of automatically inferring L-system models in mind, here we study the inductive inference problem: the inference of models from observed strings. Exact algorithms are given for inferring L-systems that can generate input strings for both deterministic context-free and deterministic context-sensitive L-systems. The algorithms run in polynomial time assuming a fixed number of alpha-bet symbols and fixed context size. Furthermore, if a specific matrix calculated from the input words is invertible, then a context-sensitive L-system can be automatically created (if it exists) in polynomial time without assuming any fixed parameters.
展开▼
