Non incremental inference of 0L-systems with positive sample

Abstract:

Many algorithms of grammatical inference were developed for several types of grammars (Adriaans, Fernau and Van Zaanen, 2002). The inference problem consists of finding, from a set of strings, a grammar that produces all the strings of this set (Miclet and Cornuéjols, 2002). We are interested here by the inference of a particular class of L-systems, noted the 0L-systems (Yokomori, 1992). We present a heuristic algorithm, which only uses positive sample corresponding to either independent or developmental biological structures. The positive sample noted I + is the set of all strings that the inferred 0L-system must produce. It is a non-incremental algorithm in the sense that the positive sample becomes unchanged (new strings cannot be added progressively) (Miclet and Cornuéjols, 2002). Biological motivation Developmental biology and inference: The problem of inductive inference has in recent years been extensively investigated. It has particular significance for developmental languages in which the description of the developmental stages of an organism is formally defined as a series of strings of symbols. The problem is to devise developmental rules which transform the strings of symbols in a way consistent with observations for a particular species. In this sense, there is an overlap between model building in developmental biology and the grammatical inference problem. This problem enters the realm of developmental biology in the following way. The biologist interested in a particular plant is confronted with a large number of experimental observations. His task is to explain on the basis of such experimental results the way in which the particular plant develops (Feliciangeli, Gabor and Herman, 1973). Studying self-similarities in plant structures: In the growth processes of many living organisms, especially plants, regularly repeated appearances of closely related biological structures are readily noticeable. This phenomenon of self-similarity has been tentatively captured by several botanical notions (Prusinkiewicz 2004), (Ferraro, Godin, and Prusinkiewicz, 2005). Our main objective is to use the grammatical inference in the detection of this self-similarity from a symbolic representation of a tree structure in development, or from several tree structures corresponding to different varieties in the aim to compare them. Complementary arguments for such a biological motivation, as well as some similar problems, are discussed in (Herman and Walker, 1972).