From n-grams to trees in Lindenmayer systems
This work addresses a theoretical problem in formal language theory, specifically for researchers studying L-systems, and appears incremental as it builds on existing approaches.
The paper tackles the problem of mapping string admissibility conditions in Lindenmayer systems to local tree admissibility conditions, showing that for a subset of L-systems, it is possible to define a model where different systems satisfy the same constraints.
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 rules are abandoned in favour of conditions over allowable expressions in the language (Pullum, 2019). We will argue that it is possible, for at least a subset of L-systems and the languages they generate, to map string admissibility conditions (the 'Three Laws') to local tree admissibility conditions (cf. Rogers, 1997). This is equivalent to defining a model for those languages. We will work out how to construct structure assuming only superficial constraints on expressions, and define a set of constraints that well-formed expressions of specific L-languages must satisfy. We will see that L-systems that other methods distinguish turn out to satisfy the same model.