PAC-Learning Unambiguous NTS Languages


Authors

Clark, Alexander

Year

2006

Abstract

Non-terminally separated (NTS) languages are a subclass of deterministic context free languages where there is a stable relationship between the substrings of the language and the non-terminals of the grammar. We show that when the distribution of samples is generated by a PCFG, based on the same grammar as the target language, the class of unambiguous NTS languages is PAC-learnable from positive data alone, with polynomial bounds on data and computation.

local copy of pdf

citation in bibtex

comments powered by Disqus