Polynomial Time Learnabilities of Tree Patterns with Internal Structured Variables from Queries (New Aspects of Theoretical Computer Science)
Satoshi Matsumoto, Yusuke Suzuki, Takayoshi Shoudai, Tomoyuki Uchida, Tetsuhiro Miyahara · Kyoto University Research Information Repository (Kyoto University) · 2003
We give the polynomial time learnabilities of two classes of ordered tree patterns with internal structured variables, in the query learning model of Angluin (1988).An ordered tree pattern with internal structured variables, called aterm tree, is arooted tree pattern which consists of tree structures, ordered children and internal structured variables.A term tree is suited for representing structural features in semistructured or tree structured data such as $\mathrm{H}\mathrm{T}\mathrm{M}\mathrm{L}/\mathrm{X}\mathrm{M}\mathrm{L}$ files.We show the polynomial time learnabilities of two classes of term trees using membership and restricted subset queries and one positive example.