Patterns provide a concise, syntactic way of describing a set of strings, but their expressive power comes at a price: a number of fundamental decision problems concerning (erasing) pattern languages, such as the membership problem and inclusion problem, are known to be NP-complete or even undecidable, while the decidability of the equivalence problem is still open; in learning theory, the class of pattern languages is unlearnable in models such as the distribution-free (PAC) framework (if P/poly ≠ NP/poly). Much work on the algorithmic learning of pattern languages has thus focussed on interesting subclasses of patterns for which positive learnability results may be achieved. A natural restriction on a pattern is a bound on its variable frequency - the maximum number m such that some variable occurs exactly m times in the pattern. This paper examines the effect of limiting the variable frequency of all patterns belonging to a class ∏ on the worst-case minimum number of labelled examples needed to uniquely identify any pattern of II in cooperative teaching-learning models. Two such models, the teaching dimension model as well as the preference-based teaching model, will be considered.
展开▼
