TY - GEN

T1 - DIVERSITY-BASED INFERENCE OF FINITE AUTOMATA.

AU - Rivest, Ronald L.

AU - Schapire, Robert E.

PY - 1987/1/1

Y1 - 1987/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0023595855&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0023595855&partnerID=8YFLogxK

U2 - 10.1109/sfcs.1987.21

DO - 10.1109/sfcs.1987.21

M3 - Conference contribution

AN - SCOPUS:0023595855

SN - 0818608072

SN - 9780818608070

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 78

EP - 87

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - IEEE

ER -