TY - GEN
T1 - Algorithms for inferring context-sensitive L-systems
AU - McQuillan, Ian
AU - Bernard, Jason
AU - Prusinkiewicz, Przemyslaw
N1 - Publisher Copyright:
© 2018, Springer International Publishing AG, part of Springer Nature.
PY - 2018
Y1 - 2018
N2 - 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 alphabet 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.
AB - 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 alphabet 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.
UR - https://www.scopus.com/pages/publications/85049029769
U2 - 10.1007/978-3-319-92435-9_9
DO - 10.1007/978-3-319-92435-9_9
M3 - Published Conference contribution
AN - SCOPUS:85049029769
SN - 9783319924342
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 117
EP - 130
BT - Unconventional Computation and Natural Computation - 17th International Conference, UCNC 2018, Proceedings
A2 - Stepney, Susan
A2 - Verlan, Sergey
T2 - 17th International Conference on Unconventional Computation and Natural Computation, UCNC 2018
Y2 - 25 June 2018 through 29 June 2018
ER -