Theoretical Computer Science 313 (2004) 173 – 174

www.elsevier.com/locate/tcsForeword
This special issue contains six of the 21 regular and 3 invited papers presented atthe Twelfth Annual conference on Algorithmic Learning Theory (ALT ’01), which
was held in Washington DC, USA, during November 25–28, 2001. The conference
proceedings, including preliminary versions of these papers, appeared as Lecture Notes
in Arti0cial Intelligence, Vol. 2225 from Springer. Following the conference, authors
were invited to submit full versions of their papers to the special issue. All the papers
were subjected to the standard refereeing procedure of Theoretical Computer Science.
Algorithmic learning theory aims at theoretical study of learning problems and algorithms, and it does so by providing formal models of learning and analyzing complexity of learning problems and performance of learning algorithms in the models set
forth. It provides foundations for such varied branches of arti0cial intelligence as machine learning, inductive logic programming, data mining, natural language processing,bioinformatics and others.
The 0rst paper, an invited paper by Dana Angluin, presents a comprehensive surveyof the state of the art in the so-called query learning model, a 0eld she has initiated.
Major emphasis is put on the number of queries needed to learn a class of concepts.
Work in this area has identi0ed several characterizations of learnability using combinatorial properties of concept classes. Thus the complexity of learning a class can be
determined without directly considering algorithmic issues but purely in terms of suchcharacterizations. The paper puts these results in a single framework clarifying andshowing the relations among them to give a clear picture of the state of the art in thisarea.
The next paper by Kalnishkan et al. concerns the on-line learning model, or more
speci0cally the on-line prediction games. In this framework an iterative game is played
where in each step the learner makes a prediction, observes the true value and su:ers aloss based on these two values and a 0xed loss function. The prediction complexity of asequence gives a lower bound on the loss of any prediction algorithm for the sequenceand can thus be seen as another way to characterize the inherent complexity of strings.
Kalnishkan et al. derive results on the average complexity when the sequence is i.i.d.
Bernoulli and relates this to the information complexity of the sequence. As a result
it is shown that the Kolmogorov complexity does not coincide with the prediction
complexity for the binary game.
The next two papers are in the sub-area generally known as inductive inference,
which follows seminal work by Gold who introduced the model of learning in thelimit. Here 0nite complexity rather than polynomial complexity de0nes the notion ofc 2003 Elsevier B.V. All rights reserved.
0304-3975/$ - see front matter 
doi:10.1016/j.tcs.2003.11.003

174

N. Abe, R. Khardon / Theoretical Computer Science 313 (2004) 173 – 174

feasibility. Jain and Stephan study the problem of learning to separate pairs of disjoint
sets which do not necessarily cover the instance space. Several restrictions on thelearner are studied within this framework, for example: conservative learners who only
abandon hypotheses which were contradicted by data, and set-driven learners whose
hypotheses depend exclusively on the range of the input. The e:ect of these restrictionsand their interaction is extensively studied. The two notions mentioned here are notcomparable if the learner converges on all data sequences.
Zilles studies a notion of meta-learning where a single learning algorithm can learn
several concept classes by being given an index of the class as a parameter. Two scenarios are discussed where the learner either uses a single representation for hypotheses
in all classes or can change the representation with the class. The paper studies thee:ect of restricting the learner, for example to be conservative as described above, on
the learnable classes. Various results are given separating di:erent models. Interestingly, the concept classes used in the separation (i.e. learnable in one setting but notthe other) have 0nite cardinality.
The 0nal two papers study learning problems for formal languages. The problemof learning regular languages has been extensively studied with several representation
schemes. Dennis et al. study learnability of regular languages using a non-deterministic
representation based on residuals—completion languages for pre0xes of words in thelanguage. While the representation is shown not to be polynomially learnable, parameters of the representation are studied empirically and these suggest a new learningalgorithm with desirable properties. Experiments show that the algorithm compares
favorably with other systems.
The class of BFuchi automata de0nes languages over in0nite strings. When modelinglearnability of such languages one is faced with the question of examples of in0nite
size. The paper by de la Higuera and Janodet introduces a model of learning suchlanguages from 0nite pre0xes of examples. While the complete class is not learnablea sub-class is identi0ed and shown learnable in the limit with polynomial update oneach example.
We would like to thank the members of the program committee of ALT’01 and thereviewers for their immense e:orts.
N. AbeIBM Thomas J. Watson Research Center
Yorktown Heights; NY 10598; USA
E-mail address: nabe@us.ibm.com
R. Khardon
Department of Computer Science; Tufts University
Medford; MA 02155; USA
E-mail address: roni@cs.tufts.edu