Learning a Subclass of Regular Patterns in Polynomial Time
Abstract
Presented is an algorithm (for learning a subclass of erasing regular pattern languages) which can be made to run with arbitrarily high probability of success on extended regular languages generated by patterns π of the form x _0 α _1 x _1 ... α _ m x _ m for unknown m but known c , from number of examples polynomial in m (and exponential in c ), where α _1... α _ m are variables and where α _1,..., α _ m are each strings of constants or terminals of length c . This assumes that the algorithm randomly draws samples with natural and plausible assumptions on the distribution. The more general looking case of extended regular patterns which alternate between a variable and fixed length constant strings, beginning and ending with either a variable or a constant string is similarly handled.
Cite
Text
Case et al. "Learning a Subclass of Regular Patterns in Polynomial Time." International Conference on Algorithmic Learning Theory, 2003. doi:10.1007/978-3-540-39624-6_19Markdown
[Case et al. "Learning a Subclass of Regular Patterns in Polynomial Time." International Conference on Algorithmic Learning Theory, 2003.](https://mlanthology.org/alt/2003/case2003alt-learning/) doi:10.1007/978-3-540-39624-6_19BibTeX
@inproceedings{case2003alt-learning,
title = {{Learning a Subclass of Regular Patterns in Polynomial Time}},
author = {Case, John and Jain, Sanjay and Reischuk, Rüdiger and Stephan, Frank and Zeugmann, Thomas},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2003},
pages = {234-246},
doi = {10.1007/978-3-540-39624-6_19},
url = {https://mlanthology.org/alt/2003/case2003alt-learning/}
}