Constructive learning of context-free languages with a subpansive tree

摘要

A subpansive tree is a rooted tree that gives a partial order of nonterminal symbols of a context-free grammar. We formalize subpansive trees as background knowledge of CFGs, and investigate query learning of CFGs with the help of subpansive trees. We show a restricted class of CFGs, which we call hierarchical CFGs, is efficiently learnable, while it is unlikely to be polynomial-time predictable.