Optimal L-Systems for Stochastic L-system Inference Problems
This addresses a specific open problem in stochastic L-system inference for researchers in formal languages and machine learning, but it is incremental as it builds on existing L-system theory.
The paper tackles the problem of inferring optimal stochastic L-systems from a given sequence of strings, presenting two theorems and an algorithm that maximize the probability of generating the sequence, enabling their use as machine learning models with only positive training data.
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 generating a given sequence of strings. The first theorem delineates a method for crafting a stochastic L-system that has the maximum probability of a derivation producing a given sequence of words through a single derivation (noting that multiple derivations may generate the same sequence). Furthermore, the second theorem determines the stochastic L-systems with the highest probability of producing a given sequence of words with multiple possible derivations. From these, we introduce an algorithm to infer an optimal stochastic L-system from a given sequence. This algorithm incorporates advanced optimization techniques, such as interior point methods, to ensure the creation of a stochastic L-system that maximizes the probability of generating the given sequence (allowing for multiple derivations). This allows for the use of stochastic L-systems as a model for machine learning using only positive data for training.