A non-learnable class of E-pattern languages

Author: Daniel Reidenbach

Source: Theoretical Computer Science Vol. 350, Issue 1, January 2006, pp. 91-102
(Special Issue Algorithmic Learning Theory (ALT 2002)).

Abstract. We investigate the inferrability of E-pattern languages (also known as extended or erasing pattern languages) from positive data in Gold's learning model. As the main result, our analysis yields a negative outcome for the full class of E-pattern languages—and even for the subclass of terminal-free E-pattern languages—if the corresponding terminal alphabet consists of exactly two distinct letters. Furthermore, we present a positive result for a manifest subclass of terminal-free E-pattern languages. We point out that the considered problems are closely related to fundamental questions concerning the nondeterminism of E-pattern languages.

Keywords: Pattern languages; Inductive inference; Learning theory

©Copyright 2005 Elsevier Science B.V.