TY - GEN
T1 - Inductive inference, DFAs, and computational complexity
AU - Pitt, Leonard
N1 - Funding Information:
The rest of this paper is organized as follows. Section 2 contains basic definitions that will be used throughout the paper. Section 3 begins by reviewing the definitions of identification in the limit due to Gold [26], and discusses the problem of augmenting the definition so as to incorporate a notion of computational efficiency. Various definitions are presented, and results of Angluin [4, 7] are summarized, showing that there is no polynomial time algorithm for exactly identifying the class of DFAs from examples alone. In Section 4 the "distribution-free" inference model of Valiant [58], and generalizations of this model are considered. The results of Pitt and *Supported in part by NSF grant IRI-8809570, and by the Department of Computer Science, Universityo f l]linois at Urbana-Charnpaign.
Publisher Copyright:
© 1989, Springer-Verlag.
PY - 1989
Y1 - 1989
N2 - This paper surveys recent results concerning the inference of deterministic finite automata (DFAs). The results discussed determine the extent to which DFAs can be feasibly inferred, and highlight a number of interesting approaches in computational learning theory.
AB - This paper surveys recent results concerning the inference of deterministic finite automata (DFAs). The results discussed determine the extent to which DFAs can be feasibly inferred, and highlight a number of interesting approaches in computational learning theory.
UR - http://www.scopus.com/inward/record.url?scp=85037549689&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85037549689&partnerID=8YFLogxK
U2 - 10.1007/3-540-51734-0_50
DO - 10.1007/3-540-51734-0_50
M3 - Conference contribution
AN - SCOPUS:85037549689
SN - 9783540517344
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 18
EP - 44
BT - Analogical and Inductive Inference - International Workshop, All 1989, Proceedings
A2 - Jantke, Klaus P.
PB - Springer
T2 - 2nd International Workshop on Analogical and Inductive Inference, AII 1989
Y2 - 1 October 1989 through 6 October 1989
ER -