DIVERSITY-BASED INFERENCE OF FINITE AUTOMATA.

Ronald L. Rivest; Robert E. Schapire

doi:10.1109/sfcs.1987.21

DIVERSITY-BASED INFERENCE OF FINITE AUTOMATA.

Ronald L. Rivest, Robert E. Schapire

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Annual Symposium on Foundations of Computer Science (Proceedings)
Publisher	IEEE
Pages	78-87
Number of pages	10
ISBN (Print)	0818608072, 9780818608070
DOIs	https://doi.org/10.1109/sfcs.1987.21
State	Published - 1987
Externally published	Yes

Publication series

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

All Science Journal Classification (ASJC) codes

Hardware and Architecture

Access to Document

10.1109/sfcs.1987.21

Cite this

@inproceedings{710786a0741a46beac93c3d9d3368ddc,

title = "DIVERSITY-BASED INFERENCE OF FINITE AUTOMATA.",

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.",

author = "Rivest, {Ronald L.} and Schapire, {Robert E.}",

year = "1987",

doi = "10.1109/sfcs.1987.21",

language = "English (US)",

isbn = "0818608072",

series = "Annual Symposium on Foundations of Computer Science (Proceedings)",

publisher = "IEEE",

pages = "78--87",

booktitle = "Annual Symposium on Foundations of Computer Science (Proceedings)",

}

TY - GEN

T1 - DIVERSITY-BASED INFERENCE OF FINITE AUTOMATA.

AU - Rivest, Ronald L.

AU - Schapire, Robert E.

PY - 1987

Y1 - 1987

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 -

DIVERSITY-BASED INFERENCE OF FINITE AUTOMATA.

Abstract

Publication series

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this