ML Anthology

Inferring Deterministic Linear Languages

Colin de la Higuera, José Oncina
COLT 2002 pp. 185-200
doi:10.1007/3-540-45435-7_13 /colt/2002/delahiguera2002colt-inferring/

Abstract

Linearity and determinism seem to be two essential conditions for polynomial language learning to be possible. We compare several definitions of deterministic linear grammars, and for a reasonable definition prove the existence of a canonical normal form. This enables us to obtain positive learning results in case of polynomial learning from a given set of both positive and negative examples. The resulting class is the largest one for which this type of results has been obtained so far.

PDF COLT Semantic Scholar

Cite

Text

de la Higuera and Oncina. "Inferring Deterministic Linear Languages." Annual Conference on Computational Learning Theory, 2002. doi:10.1007/3-540-45435-7_13

Markdown

[de la Higuera and Oncina. "Inferring Deterministic Linear Languages." Annual Conference on Computational Learning Theory, 2002.](https://mlanthology.org/colt/2002/delahiguera2002colt-inferring/) doi:10.1007/3-540-45435-7_13

BibTeX

@inproceedings{delahiguera2002colt-inferring,
  title     = {{Inferring Deterministic Linear Languages}},
  author    = {de la Higuera, Colin and Oncina, José},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {2002},
  pages     = {185-200},
  doi       = {10.1007/3-540-45435-7_13},
  url       = {https://mlanthology.org/colt/2002/delahiguera2002colt-inferring/}
}