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