  We study the classification problems over string data for hypotheses
specified by formulas of monadic second-order logic MSO. The goal is to design
learning algorithms that run in time polynomial in the size of the training
set, independently of or at least sublinear in the size of the whole data set.
We prove negative as well as positive results. If the data set is an
unprocessed string to which our algorithms have local access, then learning in
sublinear time is impossible even for hypotheses definable in a small fragment
of first-order logic. If we allow for a linear time pre-processing of the
string data to build an index data structure, then learning of MSO-definable
hypotheses is possible in time polynomial in the size of the training set,
independently of the size of the whole data set.
