Algorithmic Learning Theory: 8th International Workshop, ALT ’97 Sendai, Japan, October 6–8, 1997 Proceedings

Manuel Blum (auth.), Ming Li, Akira Maruoka (eds.)3540635777, 9783540635772

This book constitutes the refereed proceedings of the 8th International Workshop on Algorithmic Learning Theory, ALT’97, held in Sendai, Japan, in October 1997.
The volume presents 26 revised full papers selected from 42 submissions. Also included are three invited papers by leading researchers. Among the topics addressed are PAC learning, learning algorithms, inductive learning, inductive inference, learning from examples, game-theoretical aspects, decision procedures, language learning, neural algorithms, and various other aspects of computational learning theory.

---

Table of contents :
Program error detection/correction: Turning PAC learning into Perfect learning….Pages 1-1
Team learning as a game….Pages 2-17
Inferability of recursive real-valued functions….Pages 18-31
Learning of R.E. Languages from good examples….Pages 32-47
Identifiability of subspaces and homomorphic images of zero-reversible languages….Pages 48-61
On exploiting knowledge and concept use in learning theory….Pages 62-84
Partial occam’s razor and its applications….Pages 85-99
Derandomized learning of boolean functions….Pages 100-115
Learning DFA from simple examples….Pages 116-131
PAC learning under helpful distributions….Pages 132-145
PAC learning using Nadaraya-Watson estimator based on orthonormal systems….Pages 146-160
Monotone extensions of boolean data sets….Pages 161-175
Classical Brouwer-Heyting-Kolmogorov interpretation….Pages 176-196
Inferring a system from examples with time passage….Pages 197-211
Polynomial time inductive inference of regular term tree languages from positive data….Pages 212-227
Synthesizing noise-tolerant language learners….Pages 228-243
Effects of Kolmogorov complexity present in inductive inference as well….Pages 244-259
Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries….Pages 260-276
Exact learning via teaching assistants (Extended abstract)….Pages 277-290
An efficient exact learning algorithm for ordered binary decision diagrams….Pages 291-306
Probability theory for the Brier game….Pages 307-322
Learning and revising theories in noisy domains….Pages 323-338
A note on a scale-sensitive dimension of linear bounded functionals in Banach Spaces….Pages 339-351
On the relevance of time in neural computation and learning….Pages 352-363
A simple algorithm for predicting nearly as well as the best pruning labeled with the best prediction values of a decision tree….Pages 364-384
Learning disjunctions of features….Pages 385-400
Learning simple deterministic finite-memory automata….Pages 401-415
Learning acyclic first-order horn sentences from entailment….Pages 416-431
On learning disjunctions of zero-one threshold functions with queries….Pages 432-445
….Pages 446-460