A model for a Lindenmayer reconstruction algorithm
This addresses a theoretical problem in formal language theory for researchers studying Lindenmayer systems, but it is incremental as it focuses on a single grammar.
The paper tackles the problem of determining if an input string belongs to the set generated by the Fibonacci grammar and reconstructing its previous generation, resulting in an automaton that achieves this for the specific Lindenmayer system.
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 can generate (in other words, if s corresponds to a generation of the grammar) and, if so, (ii) reconstructing the previous generation.