Inductive inference of lindenmayer systems: algorithms and computational complexity
Date
2025-06-10
Authors
Duffy, Christopher
Hillis, Sam
Khan, Umer
McQuillan, Ian
Shan, Sonja Linghui
Journal Title
Journal ISSN
Volume Title
Publisher
Springer
ORCID
Type
Article
Degree Level
Abstract
Lindenmayer systems (L-systems) are string rewriting systems that can model and be used to create simulations of processes with inherent parallelism and self-similarity. Inference of L-systems involves the automated learning of these models/grammars from data; and inductive inference involves learning an L-system from a sequence of strings initially generated by an unknown L-system. This paper studies the computational complexity of inductive inference of a variety of different types of context-free L-systems (deterministic or nondeterministic, tabled or not, and allowing erasing or not). Because this inference is sometimes trivial for nondeterministic L-systems, it is more useful to find the smallest L-system that can generate the sequence of strings, in terms of either the number of rewriting rules, or (when there are tables), the number of tables. For all of the types of L-systems studied, finding an L-system with the smallest number of rewriting rules is NP--complete. However, in all cases, if the number of rewriting rules is fixed, then finding an L-system of any type studied, or finding the smallest L-systems in terms of the number of rewriting rules, or the smallest in terms of the number of tables, can always be done in polynomial time.
Description
This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/s11047-025-10024-x
Keywords
Lindenmayer Systems, Computational Complexity, Formal Languages and Automata Theory, Plant Simulations, Algorithmic Complexity, Algorithms, Complexity, Linear Logic
Citation
Duffy, C., Hillis, S., Khan, U. et al. Inductive inference of lindenmayer systems: algorithms and computational complexity. Nat Comput (2025). https://doi.org/10.1007/s11047-025-10024-x
Degree
Department
Program
Advisor
Committee
Part Of
item.page.relation.ispartofseries
DOI
https://doi.org/10.1007/s11047-025-10024-x