Inference of even linear grammars and its application to picture description languages

摘要

A constructive method for the inference of Even Linear Grammars from positive samples is proposed. It is shown through examples that the method correctly infers many languages. The method infers in the limit a grammar with an infinite number of rules and nonterminals when the samples are from some non-even linear language as illustrated through two examples. One of the main advantages of the method is that it can be adapted for on-line inference. The proposed method is employed to infer grammars for some pictures represented in PDL and it is shown that the method can be used in a hierarchical manner to infer grammars for more complex pictures.