Reidenbach, Daniel On the learnability of E-pattern languages over small alphabets 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. untagged;Information and Computing Sciences not elsewhere classified 2008-07-09
    https://repository.lboro.ac.uk/articles/journal_contribution/On_the_learnability_of_E-pattern_languages_over_small_alphabets/9402731