Theoretical Computer Science 241 (2000) 1–2

www.elsevier.com/locate/tcs

PrefaceThis special volume contains the revised and expanded version of nine of the 28papers presented at the Seventh International Workshop on Algorithmic Learning Theory (ALT ’96) held in Sydney during October 23–25, 1996. The workshop proceedings
appeared as Lecture Notes in Artiÿcial Intelligence, Volume 1160. All the papers included in this volume were subjected to the standard refereeing process of this journal.
The ÿeld of algorithmic learning theory covers a number of di erent areas and thepapers selected represent this diversity. Of the nine papers included, one is about thetheoretical foundation of genetic programming, four are on concrete learning models,
and the remaining four are on various topics in inductive inference.
The paper by VitÃanyi introduces a novel approach to proving convergence resultsin genetic programming. He proposes a notion of highly probable ÿtness optimization
through evolutionary runs on small size populations and deploys recent results about
rapidly mixing Markov chains to show that under suitable conditions, the proposed
method eciently ÿnds optimal programs with probability almost 1.
The paper by Long addresses the complexity of learning smooth functions on thereals. He derives a nice tight best-possible bound on the worst-case sum of absolute
prediction errors in the mistake-bound learning model adapted for continuous-valued
functions. Takimoto, Sakai, and Maruoka propose a new kind of decomposition involving exclusive-or expansion based on monotone DNF formulas, and employ it toinvestigate learnability of DNF formulas in Angluin’s query learning model. Arvindand Vinodchandran propose the notion of teaching assistants to develop a more ÿnegrained version of the exact learning model, and apply this machinery to analyze thecomplexity of learning permutation groups and linear spaces over ÿnite ÿelds. Thepaper by Nakamura gives ecient algorithms in the exact learning model for learnability of bounded-width ordered binary decision diagrams when no ordering of thevariables is given and learning involves equivalence queries and membership queries.
Of the four papers in inductive inference, two investigate models of learnability
and the other two give learnability results for concrete classes. The paper by Case,
Jain, and Stephan investigates the impact of noise on vacillatory and behaviorally
correct identiÿcation in the limit of languages from both texts (positive data only) andinformants (positive and negative data). Another recent model is that of learning byerasing. In this model, a machine learns by eliminating potential hypotheses from aspace of hypotheses, thereby converging to the least hypothesis never eliminated whichis also a solution to the underlying learning problem. This model is extensively
0304-3975/00/$ - see front matter c 2000 Elsevier Science B.V. All rights reserved.
PII: S 0 3 0 4 - 3 9 7 5 ( 9 9 ) 0 0 2 6 2 - 5

2Preface / Theoretical Computer Science 241 (2000) 1–2

investigated in the paper by Jain, Kinber, Lange, Wiehagen, and Zeugmann from several
di erent angles. The paper by Shinohara and Arimura surveys the issues involved inlearnability of unbounded unions of nonerasing pattern languages — a representation
scheme with applications in genome informatics. The authors show that this problem
has connections to the learnability of erasing pattern languages from positive data, andderive conditions under which unbounded unions of pattern languages become learnablefrom positive data. The ÿnal paper by Krishna Rao describes a very large class of logic
programs that is learnable in the limit from only positive facts. This paper should beof interest to researchers in inductive logic programming.
The editor wishes to thank the members of the program committee of ALT ’96
for helping to select the papers for this volume. The editor also wishes to express
his sincere gratitude to all the reviewers for their excellent e ort. Finally, the helpof Setsuo Arikawa and Osamu Watanabe in the preparation of this volume is greatlyappreciated.
Arun Sharma
School of Computer Science and Engineering, University of New South Wales,
Sydney, NSW 2052, Australia
E-mail address: arun@cse.unsw.edu.au (A. Sharma)