Learning Regular Sets with an Incomplete Membership Oracle
Abstract
This paper gives an "efficient" algorithm for learning deterministic finite automata by using an equivalence oracle and an incomplete membership oracle. This solves an open problem that was posed by Angluin and Slonim in 94.
References
[1]
D. Angluin. (1987). Learning Regular Sets from Queries and Counterexamples. Information and Computation, 75:87-106.
[2]
D. Angluin. (1988). Queries and Concept Learning. Machine Learning, 2:319-342.
[3]
D. Angluin. (1990). Negative Results for Equivalence Queries. Machine Learning, 5:121-150.
[4]
D. Angluin and D. K. Slonim. (1994). Randomly Fallible Teachers: Learning Monotone DNF with an Incomplete Membership Oracle. Machine Learning, 14:7-26.
[5]
D. Angluin, M. Kriķis, R. H. Sloan and G. Turán. (1997). Malicious Omissions and Errors in Answers to Membership Queries. Machine Learning, 28:211-255.
[6]
A. Beimel, F. Bergadoano, N.H. Bshouty and E.Kushilevitz. (1996) On the Application of Multiplicity automaton in Learning. FOCS96, 349-358.
[7]
A. Blum, R. Khardon, E. Kushilevitz, L. Pitt and D. Roth. (1994). On Learning Read-k-Satisfy-j DNF. COLT94, 110-117.
[8]
N. H. Bshouty (1997). Simple Learning Algorithms using Divide and Conquer. Computational Complexity, 6:174-194.
[9]
N. H. Bshouty and N. Einon. Learning Monotone DNF from a Teacher that almost does not answer membership queries Manuscript.
[10]
Z. Chen. (1994). A note on learning DNF formulas using Equivalence and Incomplete Membership Queries. AII/ALT, 272-281.
[11]
M. Kearns and L. Valient. (1994). Cryptographic Limitations on Learning Boolean Formulae and Finite automaton. Journal of the Association for Computing Machinery, 41:67-95.
[12]
M. Kearns and U. Vazirani. "An introduction to Computational Learning Theory". MIT Press, 1994.
[13]
E. Kushilevitz. (1996). A Simple Algorithm for Learning O(log n)-Term DNF. COLT96, 266-269.
[14]
R.L. Rivest and R.E. Schapire. (1993). Inference of Finite automaton Using Homing Sequences. Information and Computation, 103(2):299-347.
[15]
R.H. Sloan and G. Turan. (1994). Learning with Queries but Incomplete Information. In Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 237-245.
[16]
S.A. Goldman and H.D. Mathias. (1992). Learning k-term DNF formulas with an incomplete membership oracle. In Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory, 77-84.
- Learning Regular Sets with an Incomplete Membership Oracle
Recommendations
Regular sets over extended tree structures
We investigate notions of decidability and definability for the Monadic Second-Order Logic over labeled tree structures, and its relations with finite automata using oracles to test input prefixes. A general framework is defined allowing to transfer ...
Learning k-term DNF formulas with an incomplete membership oracle
COLT '92: Proceedings of the fifth annual workshop on Computational learning theoryWe consider the problem of learning k-term DNF formulas using equivalence queries and incomplete membership queries as defined by Angluin and Slonim. We demonstrate that this model can be applied to non-monotone classes. Namely, we describe a polynomial-...
Boundary sets of regular and context-free languages
We investigate the descriptional and computational complexity of boundary sets of regular and context-free languages. For a letter a, the right (left, respectively) a-boundary set of a language L consists of the words in L whose a-predecessor or a-...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 16 July 2001
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 03 Jan 2025