|
NeuroCOLT
Technical Report NC-TR-97-034
Algorithms for
Learning Finite Automata from Queries: A Unified View
Josè
Balcazar, Josep Diaz, Ricard Gavalda
Universitat Politècnica de Catalunya
Spain
Osamu
Watanabe
Tokyo Institute of Technology
Japan
Abstract
In this survey we compare several known variants of the algorithm
for learning deterministic finite automata via membership and equivalence
queries. We believe that our presentation makes it easier to understand
what is going on and what the differences between the various algorithms
mean. We also include the comparative analysis of the algorithms,
review some known lower bounds, prove a new one, and discuss the question
of parallelizing this sort of algorithms.
Download Compressed Postscript
|