### Diversity-based inference of finite automataDiversity-based inference of finite automata

Access Restriction
Subscribed

 Author Rivest, Ronald L. ♦ Schapire, Robert E. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1994 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Diversity-based representation ♦ Finite automata ♦ Inductive inference ♦ Learning theory ♦ Permutation automata Abstract We present new procedures for inferring the structure of a finite-state automaton (FSA) from its input/output behavior, using access to the automaton to perform experiments.Our procedures use a new representation for finite automata, based on the notion of equivalence between $\textit{tests}.$ We call the number of such equivalence classes the $\textit{diversity}$ of the automaton; the diversity may be as small as the logarithm of the number of states of the automaton. For the special class of permutation automata, we describe an inference procedure that runs in time polynomial in the diversity and log(1/δ), where δ is a given upper bound on the probability that our procedure returns an incorrect result. (Since our procedure uses randomization to perform experiments, there is a certain controllable chance that it will return an erroneous result.) We also discuss techniques for handling more general automata.We present evidence for the practical efficiency of our approach. For example, our procedure is able to infer the structure of an automaton based on Rubik's Cube (which has approximately 1019 states) in about 2 minutes on a DEC MicroVax. This automaton is many orders of magnitude larger than possible with previous techniques, which would require time proportional at least to the number of global states. (Note that in this example, only a small fraction (10-14) of the global states were even visited.)Finally, we present a new procedure for inferring automata of a special type in which the global state is composed of a vector of binary local state variables, all of which are observable (or $\textit{visible})$ to the experimenter. Our inference procedure runs provably in time polynomial in the size of this vector (which happens to be the diversity of the automaton), even though the global state space may be exponentially larger. The procedure plans and executes experiments on the unknown automaton; we show that the number of input symbols given to the automaton during this process is (to within a constant factor) the best possible. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1994-05-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 41 Issue Number 3 Page Count 35 Starting Page 555 Ending Page 589

#### Open content in new tab

Source: ACM Digital Library