Polynomial Time Inductive Inference of Regular Term Tree Languages from Positive Data
Abstract
Term graphs are a kind of hypergraphs such that arbitrary graphs can be put to the place of their hyperedges. Each hyperedge in a term graph is labeled with a variable. A term graph is called regular if each variable attached to a hyperedge does not occur more than once. Let f be a regular term graph. If a regular term graph which is obtained from f by substituting any tree becomes also a tree, f is called a regular term tree. We study polynomial time inductive inference of regular term tree languages. This graph language is an extension of pattern languages of strings. We show that some classes of regular term tree languages of term caterpillars are polynomial time inductive inferable.
Cite
Text
Matsumoto et al. "Polynomial Time Inductive Inference of Regular Term Tree Languages from Positive Data." International Conference on Algorithmic Learning Theory, 1997. doi:10.1007/3-540-63577-7_45Markdown
[Matsumoto et al. "Polynomial Time Inductive Inference of Regular Term Tree Languages from Positive Data." International Conference on Algorithmic Learning Theory, 1997.](https://mlanthology.org/alt/1997/matsumoto1997alt-polynomial/) doi:10.1007/3-540-63577-7_45BibTeX
@inproceedings{matsumoto1997alt-polynomial,
title = {{Polynomial Time Inductive Inference of Regular Term Tree Languages from Positive Data}},
author = {Matsumoto, Satoshi and Hayashi, Yukiko and Shoudai, Takayoshi},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1997},
pages = {212-227},
doi = {10.1007/3-540-63577-7_45},
url = {https://mlanthology.org/alt/1997/matsumoto1997alt-polynomial/}
}