Inference of Stochastic Regular Grammars by Massively Parallel Genetic Algorithms
Markus Schwehm, Alexander D Ost · 1995
A genetic approach to the inference of stochastic regular grammars from a given finite set of sample words is presented. The goal of the inference problem is not only to find a grammar that covers the given finite sample, but possibly also the infinite language from which the sample was taken (generalization). We propose two different bitstring representation methods for stochastic regular grammars and have a closer look at the objective function. Due to the large complexity of the problem, a massively parallel implementation of genetic algorithms was used. The algorithm was applied to a workload-modelingproblem. The results are compared with reference methods like the successor-, k-tail- and k-TLSS-method. 1 INTRODUCTION Genetic algorithms have successfully been used as a powerful global optimization method for problems with a large search space and a multimodal or otherwise difficult objective function. One such problem is the construction of a grammar for a (finite or infinite) lan...