THE INFERENCE OF TREE-LANGUAGES FROM FINITE SAMPLES - AN ALGEBRAIC APPROACH

The theory presented in this paper is intended as a mathematical basis for the understanding of methods of inferring tree languages from fin ite samples. Many such methods given in the literature involve, at lea st implicitly, the construction of some kind of a nondeterministic quo tient recognizer. We define and study in a general form such quotients of algebras and tree recognizers. Some abstract families of inference algorithms are considered, and methods presented in the literature ar e discussed in relation to these. Since strings may be regarded as una ry trees, the results of the paper apply also to string languages.