## Algorithmic Learning Theory: 9th International Conference, ALT '98, Otzenhausen, Germany, October 8-10, 1998, ProceedingsThis 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Editors Introduction | 1 |

Scalability Issues in Inductive Logic Programming | 11 |

Learning to Win ProcessControl Games Watching GameMasters | 31 |

Closedness Properties in EXIdentification of Recursive Functions | 46 |

Lower Bounds for the Complexity of Learning HalfSpaces with Membership Queries | 61 |

Cryptographic Limitations on Parallelizing Membership and Equivalence Queries with Applications to Random SelfReductions | 72 |

Learning Unary Output TwoTape Automata from Multiplicity and Equivalence Queries | 87 |

Computational Aspects of Parallel AttributeEfficient Learning | 103 |

Characteristic Sets for Unions of Regular Pattern Languages and Compactness | 220 |

Finding a OneVariable Pattern from Incomplete Data | 234 |

A Fast Algorithm for Discovering Optimal String Patterns in Large Text Databases | 247 |

A Comparison of Identification Criteria for Inductive Inference of Recursive RealValued Functions | 262 |

Predictive Learning Models for Concept Drift | 276 |

Learning with Refutation | 291 |

Comparing the Power of Probabilistic Learning and Oracle Identification Under Monotonicity Constraints | 306 |

Learning Algebraic Structures from Text Using Semantical Knowledge | 321 |

PAC Learning from Positive Statistical Queries | 112 |

Structured WeightBased Prediction Algorithms | 127 |

Learning from Entailment of Logic Programs with Local Variables | 143 |

Logical Aspects of Several BottomUp Fittings | 158 |

Learnability of Translations from Positive Examples | 169 |

Analysis of CaseBased Representability of Boolean Functions by Monotone Theory | 179 |

Learning Languages from Positive Data | 191 |

Synthesizing Learners Tolerating Computable Noisy Data | 205 |

A System for Learning Relations | 336 |

On the Sample Complexity for Neural Trees | 375 |

Learning Subclasses of Monotone DNF on the Uniform Distribution | 385 |

Using Attribute Grammars for Description of Inductive Inference Search Space | 400 |

Towards the Validation of Inductive Learning Systems | 409 |

Consistent Polynomial Identification in the Limit | 424 |

439 | |

### Other editions - View all

### Common terms and phrases

Algorithmic Learning Theory Angluin attribute automata automaton background knowledge boolean function bound case-based complexity Computational Learning Theory Computer Science concept class consider consistent construct contains Corollary deﬁned Deﬁnition EFS’s equivalence queries Ex-learner exists finite formula function f given grammar Hence hypothesis space identify indexed family inductive inference Inductive Logic Programming infinite input integer learnable learner learning algorithm Lemma Lime linear linearly-moded literal Machine Learning MDNF membership queries mind change minimal monotone natural numbers negative examples node Noetherian ring oracle output paper pattern languages polynomial positive data positive examples prediction probabilistic Proof query depth random Read-once recursive functions recursive languages recursive real-valued functions recursively enumerable regular language regular patterns result sample sequence simple clauses Springer-Verlag strategies string subset Suppose symbol target term Theorem tree validation variables VC dimension vector