Learnability of a subclass of extended pattern languages
Andrew Mitchell · 1998
Angluin introduced the class of pattern languages as term languages over strings on a finite alphabet, and showed that the class is identifiable in the limit from texts (positive data).III Angluin's definition of pattern languages, erasing substitutions are disallowed.Extended pattern languages are term languages over strings when erasing substitutions are allowed.The question of identifiability in the limit of extended pattern languages from texts has not been resolved, and is one of the outstanding open problems in inductive inference.However, there are at least two subclasses that are known to be identifiable.Shinohara has shown that the the class of extended pattern languages that can be generated by regulx patterns (these are patterns in which each variable occurs no more than once) is identifiable in the limit from texts.Wright showed that the class of extended pattern languages where the pattern contains at most m distinct variables, for any positive integer rn, is identifiable in the limit from texts.The present paper considers a generalisation of regular patterns where each variable occurring in the pattern occurs exactly rn times for some positive integer m.Such patterns arc referred to as quasi-regular patterns, and for each m, the corresponding class of extended pattern languages is denoted QRP,, .It is shown that for each m, the class QRP,, is identifiable in the limit from texts.The proof employs a sophisticated combinatorial argument for bounding the search space.It is also shown that the class U,QRP, is identifiable in the limit from texts.Pcnnission to n&r digital or hard copies of all or part of this work for personal or classroom USC is granted without fee provided that copies are not made or distributed for prolit or con~tnercial advantage and that copies bear this notice and the full citation on thZ first p"ge.-fo copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or SI fw.