The Use of Tree Derivatives and a Sample Support Parameter for Inferring Tree Systems

Tree systems have been studied in the theoretical setting as an extension of finite automata. They have been found useful in the practical domain when applied to syntactic pattern recognition. The practical applications of tree systems have motivated the examination of inference techniques for tree grammars and tree automata. In this paper we present a tree automaton inference algorithm which incorporates three concepts-tree derivatives, grammatical expansion, and inferential strength. Tree derivatives are used for comparing tree forms. Grammatical expansion is a feedback mechanism which effectively enlarges the user sample. An inferential strength parameter is input by the user to indicate the amount of support required from the sample for inferences. The algorithm is also applied for inferring finite-state machines. Finally, we address an open problem posed by Joshi and Levy by demonstrating the use of our algorithm for the design of programming languages.