ML Anthology

Stochastic Inference of Regular Tree Languages

Rafael C. Carrasco, José Oncina, Jorge Calera-Rubio
MLJ 2001 pp. 185-197
doi:10.1023/A:1010836331703 /mlj/2001/carrasco2001mlj-stochastic/

Abstract

We generalize a former algorithm for regular language identification from stochastic samples to the case of tree languages. It can also be used to identify context-free languages when structural information about the strings is available. The procedure identifies equivalent subtrees in the sample and outputs the hypothesis in linear time with the number of examples. The results are evaluated with a method that computes efficiently the relative entropy between the target grammar and the inferred one.

PDF MLJ Semantic Scholar

Cite

Text

Carrasco et al. "Stochastic Inference of Regular Tree Languages." Machine Learning, 2001. doi:10.1023/A:1010836331703

Markdown

[Carrasco et al. "Stochastic Inference of Regular Tree Languages." Machine Learning, 2001.](https://mlanthology.org/mlj/2001/carrasco2001mlj-stochastic/) doi:10.1023/A:1010836331703

BibTeX

@article{carrasco2001mlj-stochastic,
  title     = {{Stochastic Inference of Regular Tree Languages}},
  author    = {Carrasco, Rafael C. and Oncina, José and Calera-Rubio, Jorge},
  journal   = {Machine Learning},
  year      = {2001},
  pages     = {185-197},
  doi       = {10.1023/A:1010836331703},
  volume    = {44},
  url       = {https://mlanthology.org/mlj/2001/carrasco2001mlj-stochastic/}
}