Inference of tree grammars using negative samples

摘要

This paper considers the problem of grammatical inference of tree grammars as a general problem. It is shown that the problem does not have a unique solution, and that there is a very large number of solutions. It is also shown that all inference algorithms must have the same logical structure, and that all proposed inference algorithms are, in this way, equivalent and equally correct. The paper reviews the use of negative samples in the process of grammatical inference, and emphasizes the fact that negative samples are needed to narrow down the large number of valid solutions, and to guarantee the convergence of any inference algorithm. To accomplish these purposes, an algorithm is presented to modify an inferred grammar so that it does not recognize any tree from a given negative sample. Furthermore, all the results are applicable to tree languages in which any symbol may appear in a tree with an arbitrary number of descendants.