On the Learnability of E-Pattern Languages over Small Alphabets
Abstract
This paper deals with two well discussed, but largely open problems on E-pattern languages, also known as extended or erasing pattern languages: primarily, the learnability in Gold’s learning model and, secondarily, the decidability of the equivalence. As the main result, we show that the full class of E-pattern languages is not inferrable from positive data if the corresponding terminal alphabet consists of exactly three or of exactly four letters – an insight that remarkably contrasts with the recent positive finding on the learnability of the subclass of terminal-free E-pattern languages for these alphabets. As a side-effect of our reasoning thereon, we reveal some particular example patterns that disprove a conjecture of Ohlebusch and Ukkonen ( Theoretical Computer Science 186, 1997) on the decidability of the equivalence of E-pattern languages.
Cite
Text
Reidenbach. "On the Learnability of E-Pattern Languages over Small Alphabets." Annual Conference on Computational Learning Theory, 2004. doi:10.1007/978-3-540-27819-1_10Markdown
[Reidenbach. "On the Learnability of E-Pattern Languages over Small Alphabets." Annual Conference on Computational Learning Theory, 2004.](https://mlanthology.org/colt/2004/reidenbach2004colt-learnability/) doi:10.1007/978-3-540-27819-1_10BibTeX
@inproceedings{reidenbach2004colt-learnability,
title = {{On the Learnability of E-Pattern Languages over Small Alphabets}},
author = {Reidenbach, Daniel},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2004},
pages = {140-154},
doi = {10.1007/978-3-540-27819-1_10},
url = {https://mlanthology.org/colt/2004/reidenbach2004colt-learnability/}
}