A randomised inference algorithm for regular tree languages

作者：Hogberg Johanna^*

来源：Natural Language Engineering, 2011, 17(2): 203-219.

DOI：10.1017/S1351324911000064

We present a randomised inference algorithm for regular tree languages. The algorithm takes as input two disjoint finite nonempty sets of trees P and and outputs a nondeterministic finite tree automaton that accepts every tree in P and rejects every tree in N. The output automaton typically represents a nontrivial generalisation of the examples given in P and To obtain compact output automata, we use a heuristics similar to bisimulation minimisation. The algorithm has time complexity of O(n(N) .n(P)(2)), where and n(N) are n(P) the size of N and P, respectively. Experiments are conducted on a prototype implementation, and the empirical results appear to second the theoretical results.

• 出版日期2011-4