nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Algorithms for Inferring Context-Sensitive L-Systems

verfasst von : Ian McQuillan, Jason Bernard, Przemyslaw Prusinkiewicz

Erschienen in: Unconventional Computation and Natural Computation

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel An FPGA Implementation of a Distributed Virtual Machine

Nächstes Kapitel Reaction Mining for Reaction Systems

Rozenberg, G., Salomaa, A.: The Mathematical Theory of L Systems. Academic Press Inc., New York (1980)MATH

Prusinkiewicz, P., Lindenmayer, A.: The Algorithmic Beauty of Plants. Springer, New York (1990). https://doi.org/10.1007/978-1-4613-8476-2CrossRefMATH

Prusinkiewicz, P.: Graphical applications of L-systems. In: Proceedings of Graphics Interface 1986/Vision Interface 1986, pp. 247–253 (1986)

Prusinkiewicz, P.: Designing and growing virtual plants with L-systems. In: Proceedings of the XXVI International Horticultural Congress, vol. 630, pp. 15–28. Acta Horticulturae (2004)

Prusinkiewicz, P., Mündermann, L., Karwowski, R., Lane, B.: The use of positional information in the modeling of plants. In: Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 2001, pp. 289–300. ACM (2001)

Ben-Naoum, F.: A survey on L-system inference. INFOCOMP J. Comput. Sci. 8(3), 29–39 (2009)

Runqiang, B., Chen, P., Burrage, K., Hanan, J., Room, P., Belward, J.: Derivation of L-system models from measurements of biological branching structures using genetic algorithms. In: Hendtlass, T., Ali, M. (eds.) IEA/AIE 2002. LNCS (LNAI), vol. 2358, pp. 514–524. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-48035-8_50CrossRef

Sirault, X., Fripp, J., Paproki, A., Kuffner, P., Nguyen, C., Li, R., Daily, H., Guo, J., Furbank, R.: Plantscan\(^\text{TM}\): a three-dimensional phenotyping platform for capturing the structural dynamic of plant development and growth. In: 7th International Conference on Functional-Structural Plant Models, pp. 45–48 (2013)

Doucet, P.G.: The syntactic inference problem for dol-sequences. In: Rozenberg, G., Salomaa, A. (eds.) L Systems. LNCS, vol. 15, pp. 146–161. Springer, Heidelberg (1974). https://doi.org/10.1007/3-540-06867-8_12CrossRef

10.

Nakano, R., Yamada, N.: Number theory-based induction of deterministic context-free L-system grammar. In: International Conference on Knowledge Discovery and Information Retrieval, SCITEPRESS, pp. 194–199 (2010)

11.

Jürgensen, H., Lindenmayer, A.: Inference algorithms for developmental systems with cell lineages. Bull. Math. Biol. 49(1), 93–123 (1987)MathSciNetCrossRef

12.

Feliciangeli, H., Herman, G.T.: Algorithms for producing grammars from sample derivations: a common problem of formal language theory and developmental biology. J. Comput. Syst. Sci. 7(1), 97–118 (1973)MathSciNetCrossRef

13.

Nevill-Manning, C.G., Witten, I.H.: Identifying hierarchical structure in sequences: a linear-time algorithm. J. Artif. Intell. Res. 7(1), 67–82 (1997)MATH

14.

Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2006). https://doi.org/10.1007/3-540-29953-XCrossRefMATH

15.

Herman, G.T., Rozenberg, G.: Developmental Systems and Languages. North-Holland Publishing Company, Oxford (1975)MATH

16.

Schrijver, A.: Theory of Linear and Integer Programming. Wiley, New York (1986)MATH

17.

Bunch, J.R., Hopcroft, J.E.: Triangular factorization and inversion by fast matrix multiplication. Math. Comput. 28(125), 231–236 (1974)MathSciNetCrossRef

18.

Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9(3), 251–280 (1990). Computational algebraic complexity editorialMathSciNetCrossRef

Titel: Algorithms for Inferring Context-Sensitive L-Systems
verfasst von: Ian McQuillan
Jason Bernard
Przemyslaw Prusinkiewicz
Verlag: Springer International Publishing
Buch: Unconventional Computation and Natural Computation
Print ISBN: 978-3-319-92434-2

Electronic ISBN: 978-3-319-92435-9

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-92435-9_9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner