Content area
A pattern is a concatenation of variable symbols and constant symbols. The language of a pattern is the set of strings generated by replacing the variables of the pattern with all possible strings. Patterns and pattern languages, introduced by Angluin, have attracted much attention in the past 35 years.
In this thesis, we study learning the class of erasing pattern languages within three models of learning: classic teaching, recursive teaching, and query learning with shortest additional information. In the first model, a teacher chooses helpful examples to help the learner in the process of learning. We measure the complexity of a pattern language in this model by the teaching dimension parameter. In the second model, the teacher and learner cooperate to minimize the number of examples needed for learning the target and the complexity measure for this model is called recursive teaching dimension. In the last model, the learner requests information about the target language. We consider the number of queries asked by an optimal learner for identifying the target as the measure of complexity.
We investigate the learnability of various classes of erasing pattern languages like one-variable, regular, constant-free, non-cross, and arbitrary erasing pattern languages. Our results show that teaching is very inefficient in the sense that the teaching dimension is unbounded. Also, we found that while in some cases recursive teaching is much more efficient than teaching, in other cases, the classes of erasing pattern languages are not learnable with recursive teaching. For learning classes of erasing pattern languages with queries, we found that giving the shortest string as an initial example improves the process of learning for some classes of erasing pattern languages like one-variable pattern languages, while for the classes of patterns which contain only constant-free patterns it does not help at all.