A survey on L-system Inference

Abstract

Many algorithms of grammatical inference were developed for several types of grammars. The grammatical inference problem consists of finding, from a set of strings, a grammar that produces all the strings of this set [3]. We are interested here by the inference of particular grammars, noted Lsystems, which are parallel rewriting systems most famously used to model the growth processes of plant development. We present a survey on methods of L-system inference proposed since the creation of this rewriting system by Aristid Lindenmayer in 1968 [15]. The grammatical inference of L-systems has been studied over the past 30 years, and that in relation to several areas of application of produced L-systems. We are interested in looking at this problem from the point of view of a possible use of these methods for an application in biological modeling, particularly in the modeling of plants. In order to provide a better understanding of the research challenges of L-system inference, this article presents a detailed investigation of current state-of-the-art algorithms in L-system inference, with an analysis highlighting their positive and negative points. Open research issues are also discussed, with an objective to spark new research interests in this field.