Towards a classification of Lindenmayer systems
In this paper we will attempt to classify Lindenmayer systems based on properties of sets of rules and the kind of strings those rules generate. This classification will be referred to as a parametrization of the L-space: the L-space is the phase space in which all possible L-developments are represented. This space is infinite, because there is no halting algorithm for L-grammars; but it is also subjected to hard conditions, because there are grammars and developments which are not possible states of an L-system: a very well-known example is the space of normal grammars. Just as the space of normal grammars is parametrized into Regular, Context-Free, Context-Sensitive, and Unrestricted (with proper containment relations holding among them; see Chomsky, 1959: Theorem 1), we contend here that the L-space is a very rich landscape of grammars which cluster into kinds that are not mutually translatable.
Code (0)
등록된 구현이 없습니다.
Tasks
ClassificationGeneral ClassificationSimilar Papers 제목 키워드 기반
From n-grams to trees in Lindenmayer systems
In this paper we present two approaches to Lindenmayer systems: the rule-based (or generative) approach, which focuses on L-systems as Thue rewriting systems and a constraint-based (or model-theoretic) approach, in which…
A model for a Lindenmayer reconstruction algorithm
Given an input string s and a specific Lindenmayer system (the so-called Fibonacci grammar), we define an automaton which is capable of (i) determining whether s belongs to the set of strings that the Fibonacci grammar c…
modelTechniques for Inferring Context-Free Lindenmayer Systems With Genetic Algorithm
Lindenmayer systems (L-systems) are a formal grammar system, where the most notable feature is a set of rewriting rules that are used to replace every symbol in a string in parallel; by repeating this process, a sequence…
New Techniques for Inferring L-Systems Using Genetic Algorithm
Lindenmayer systems (L-systems) are a formal grammar system that iteratively rewrites all symbols of a string, in parallel. When visualized with a graphical interpretation, the images have self-similar shapes that appear…
Optimal L-Systems for Stochastic L-system Inference Problems
This paper presents two novel theorems that address two open problems in stochastic Lindenmayer-system (L-system) inference, specifically focusing on the construction of an optimal stochastic L-system capable of generati…