DIVERSITY-BASED INFERENCE OF FINITE AUTOMATA.

Ronald L. Rivest, Robert E. Schapire

Research output: Chapter in Book/Report/Conference proceedingConference contribution

25 Scopus citations

Abstract

A novel procedure is presented for inferring the structure of a finite-state automaton (FSA) from its input/output behavior, using access to the automaton to perform experiments. The procedure uses a novel representation for FSAs that is based on the notion of equivalence between tests. The number of such equivalence classes is called the diversity of the automaton; the diversity may be as small as the logarithm of the number of states of the automaton. The size of the representation of the FSA, and the running time of the procedure is polynomial in the diversity and ln(1/ epsilon ), where epsilon is a given upper bound on the probability that the procedure returns an incorrect result. Some evidence for the practical efficiency of the approach is presented.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherIEEE
Pages78-87
Number of pages10
ISBN (Print)0818608072, 9780818608070
DOIs
StatePublished - Jan 1 1987
Externally publishedYes

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'DIVERSITY-BASED INFERENCE OF FINITE AUTOMATA.'. Together they form a unique fingerprint.

Cite this