Efficient Learning of Semi-Structured Data from Queries
Abstract
This paper studies the polynomial-time learnability of the classes of ordered gapped tree patterns (OGT) and ordered gapped forests (OGF) under the into-matching semantics in the query learning model of Angluin. The class OGT is a model of semi-structured database query languages, and a generalization of both the class of ordered/unordered tree pattern languages and the class of non-erasing regular pattern languages. First, we present a polynomial time learning algorithm for μ - OGT, the subclass of OGT without repeated tree variables, using equivalence queries and membership queries. By extending this algorithm, we present polynomial time learning algorithms for the classes μ -OGF of forests without repeated variables and OGT of trees with repeated variables using equivalence queries and subset queries. We also give representation-independent hardness results which indicate that both of equivalence and membership queries are necessary to learn μ -OGT.
Cite
Text
Arimura et al. "Efficient Learning of Semi-Structured Data from Queries." International Conference on Algorithmic Learning Theory, 2001. doi:10.1007/3-540-45583-3_24Markdown
[Arimura et al. "Efficient Learning of Semi-Structured Data from Queries." International Conference on Algorithmic Learning Theory, 2001.](https://mlanthology.org/alt/2001/arimura2001alt-efficient/) doi:10.1007/3-540-45583-3_24BibTeX
@inproceedings{arimura2001alt-efficient,
title = {{Efficient Learning of Semi-Structured Data from Queries}},
author = {Arimura, Hiroki and Sakamoto, Hiroshi and Arikawa, Setsuo},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2001},
pages = {315-331},
doi = {10.1007/3-540-45583-3_24},
url = {https://mlanthology.org/alt/2001/arimura2001alt-efficient/}
}