Lehrstuhl Mathematik & InformatikOn the Teaching Complexity of Linear Sets
Abstract. Linear sets are the building blocks of semilinear sets, which are in turn closely connected to automata theory and formal languages. Prior work has investigated the learnability of linear sets and semilinear sets in three models – Valiant's PAC-learning model, Gold's learning in the limit model, and Angluin's query learning model. This paper considers teacher–learner models of learning families of linear sets, in which a benevolent teacher presents a set of labelled examples to the learner. First, we study the classical teaching model, in which a teacher must successfully teach any consistent learner. Second, we will apply a generalisation of the recently introduced recursive teaching model to several infinite classes of linear sets, and show that thus the maximum sample complexity of teaching these classes can be drastically reduced compared to classical teaching. To this end, a major focus of the paper will be on determining two relevant teaching parameters, the teaching dimension and recursive teaching dimension, for various families of linear sets.