This volume contains all the papers presented at the Ninth International Con- rence on Algorithmic Learning Theory (ALT'98), held at the European education centre Europ¨aisches Bildungszentrum (ebz) Otzenhausen, Germany, October 8{ 10, 1998. The Conference was sponsored by the Japanese Society for Arti cial Intelligence (JSAI) and the University of Kaiserslautern. Thirty-four papers on all aspects of algorithmic learning theory and related areas were submitted, all electronically. Twenty-six papers were accepted by the program committee based on originality, quality, and relevance to the theory of machine learning. Additionally, three invited talks presented by Akira Maruoka of Tohoku University, Arun Sharma of the University of New South Wales, and Stefan Wrobel from GMD, respectively, were featured at the conference. We would like to express our sincere gratitude to our invited speakers for sharing with us their insights on new and exciting developments in their areas of research. This conference is the ninth in a series of annual meetings established in 1990. The ALT series focuses on all areas related to algorithmic learning theory including (but not limited to): the theory of machine learning, the design and analysis of learning algorithms, computational logic of/for machine discovery, inductive inference of recursive functions and recursively enumerable languages, learning via queries, learning by arti cial and biological neural networks, pattern recognition, learning by analogy, statistical learning, Bayesian/MDL estimation, inductive logic programming, robotics, application of learning to databases, and gene analyses.

InhaltsangabeTable of Contents Editors'Introduction M.M. Richter, C.H. Smith, R. Wiehagen, and T. Zeugmann Inductive Logic Programming and Data Mining Scalability Issues in Inductive Logic Programming (Invited Lecture) S. Wrobel Inductive Inference Learning to Win Process-Control Games Watching Game-Masters J. Case, M. Ott, A. Sharma, and F. Stephan Closedness Properties in EX-identification of Recursive Functions K. Apsitis, R. Freivalds, R. Simanovskis, and J. Smotrovs Learning via Queries Lower Bounds for the Complexity of Learning Half-Spaces with Membership Queries V.N. Shevchenko, and N.Yu. Zolotykh Cryptographic Limitations on Parallelizing Membership and Equivalence Queries with Applications to Random Self-Reductions M. Fischlin Learning Unary Output Two-Tape Automata from Multiplicity and Equivalence Queries G. Melideo, and S. Varricchio Computational Aspects of Parallel Attribute-Efficient Learning P. Damaschke PAC Learning from Positive Statistical Queries F. Denis Prediction Algorithms Structured Weight-Based Prediction Algorithms (Invited Lecture) A. Maruoka, and E. Takimoto Inductive Logic Programming Learning from Entailment of Logic Programs with Local Variables M.K.R. Krishna Rao, and A. Sattar Logical Aspects of Several Bottom-Up Fittings A. Yamamoto Learnability of Translations from Positive Examples N. Sugimoto Analysis of Case-Based Representability of Boolean Functions by Monotone Theory K. Satoh Learning Formal Languages Locality, Reversibility, and Beyond: Learning Languages from Positive Data T. Head, S. Kobayashi, and T. Yokomori Synthesizing Learners Tolerating Computable Noisy Data J. Case, and S. Jain Characteristic Sets for Unions of Regular Pattern Languages and Compactness M. Sato, Y. Mukouchi, and D. Zheng Finding a One-Variable Pattern from Incomplete Data H. Sakamoto A Fast Algorithm for Discovering Optimal String Patterns in Large Text Databases H. Arimura, A. Wataki, R. Fujino, and S. Arikawa Inductive Inference A Comparison of IdentificationCriteria for Inductive Inference of Recursive Real-Valued Functions E. Hirowatari, and S. Arikawa Predictive Learning Models for Concept Drift J. Case, S. Jain, S. Kaufmann, A. Sharma, and F. Stephan Learning with Refutation S. Jain Comparing the Power of Probabilistic Learning and Oracle Identification under Monotonicity Constraints L. Meyer Learning Algebraic Structures from Text Using Semantical Knowledge F. Stephan and Y. Ventsov Inductive Logic Programming Lime: A System for Learning Relations (Invited Lecture) E. McCreath, and A. Sharma Miscellaneous On the Sample Complexity for Neural Trees M. Schmitt Learning Sub-Classes of Monotone DNF on the Uniform Distribution K. Verbeurgt Using Attribute Grammars for Description of Inductive Inference Search Space U. Sarkans, and J. Barzdins Towards the Validation of Inductive Learning Systems G. Grieser, K.P. Jantke, and S. Lange Consistent Polynomial Identification in the Limit W. Stein Author Index

Table of Contents Editors''Introduction M.M. Richter, C.H. Smith, R. Wiehagen, and T. Zeugmann Inductive Logic Programming and Data Mining Scalability Issues in Inductive Logic Programming (Invited Lecture) S. Wrobel Inductive Inference Learning to Win Process-Control Games Watching Game-Masters J. Case, M. Ott, A. Sharma, and F. Stephan Closedness Properties in EX-identification of Recursive Functions K. Apsitis, R. Freivalds, R. Simanovskis, and J. Smotrovs Learning via Queries Lower Bounds for the Complexity of Learning Half-Spaces with Membership Queries V.N. Shevchenko, and N.Yu. Zolotykh Cryptographic Limitations on Parallelizing Membership and Equivalence Queries with Applications to Random Self-Reductions M. Fischlin Learning Unary Output Two-Tape Automata from Multiplicity and Equivalence Queries G. Melideo, and S. Varricchio Computational Aspects of Parallel Attribute-Efficient Learning P. Damaschke PAC Learning from Positive Statistical Queries F. Denis Prediction Algorithms Structured Weight-Based Prediction Algorithms (Invited Lecture) A. Maruoka, and E. Takimoto Inductive Logic Programming Learning from Entailment of Logic Programs with Local Variables M.K.R. Krishna Rao, and A. Sattar Logical Aspects of Several Bottom-Up Fittings A. Yamamoto Learnability of Translations from Positive Examples N. Sugimoto Analysis of Case-Based Representability of Boolean Functions by Monotone Theory K. Satoh Learning Formal Languages Locality, Reversibility, and Beyond: Learning Languages from Positive Data T. Head, S. Kobayashi, and T. Yokomori Synthesizing Learners Tolerating Computable Noisy Data J. Case, and S. Jain Characteristic Sets for Unions of Regular Pattern Languages and Compactness M. Sato, Y. Mukouchi, and D. Zheng Finding a One-Variable Pattern from Incomplete Data H. Sakamoto A Fast Algorithm for Discovering Optimal String Patterns in Large Text Databases H. Arimura, A. Wataki, R. Fujino, and S. Arikawa Inductive Inference A Comparison of Identification Criteria for Inductive Inference of Recursive Real-Valued Functions E. Hirowatari, and S. Arikawa Predictive Learning Models for Concept Drift J. Case, S. Jain, S. Kaufmann, A. Sharma, and F. Stephan Learning with Refutation S. Jain Comparing the Power of Probabilistic Learning and Oracle Identification under Monotonicity Constraints L. Meyer Learning Algebraic Structures from Text Using Semantical Knowledge F. Stephan and Y. Ventsov Inductive Logic Programming Lime: A System for Learning Relations (Invited Lecture) E. McCreath, and A. Sharma Miscellaneous On the Sample Complexity for Neural Trees M. Schmitt Learning Sub-Classes of Monotone DNF on the Uniform Distribution K. Verbeurgt Using Attribute Grammars for Description of Inductive Inference Search Space U. Sarkans, and J. Barzdins Towards the Validation of Inductive Learning Systems G. Grieser, K.P. Jantke, and S. Lange Consistent Polynomial Identification in the Limit W. Stein Author Index