colt04_reidenbach.pdf (206.9 kB)
Download file

On the learnability of E-pattern languages over small alphabets

Download (206.9 kB)
journal contribution
posted on 09.07.2008, 09:02 by Daniel ReidenbachDaniel Reidenbach
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.

History

School

  • Science

Department

  • Computer Science

Citation

REIDENBACH, D., 2004. On the learnability of E-pattern languages over small alphabets. Lecture Notes in Computer Science, 3120, pp. 140-154

Publisher

© Springer-Verlag

Publication date

2004

Notes

This is a journal article. It was published in Lecture Notes in Computer Science [© Springer Verlag] and the definitive version is available at: www.springerlink.com

ISBN

9783540222828

ISSN

0302-9743;1611-3349

Language

en

Usage metrics

Keywords

Exports