{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,9]],"date-time":"2026-02-09T09:25:21Z","timestamp":1770629121424,"version":"3.49.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/bf00993409","type":"journal-article","created":{"date-parts":[[2005,1,14]],"date-time":"2005-01-14T18:17:14Z","timestamp":1105726634000},"page":"149-185","source":"Crossref","is-referenced-by-count":10,"title":["Learning fallible Deterministic Finite Automata"],"prefix":"10.1007","volume":"18","author":[{"given":"Dana","family":"Ron","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","unstructured":"Alon, N., & Spencer, J. H. (1991).The Probabilistic Method. Wiley Interscience."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/S0019-9958(81)90090-5","volume":"51","author":"D. Angluin","year":"1981","unstructured":"Angluin, D. (1981). A note on the number of queries needed to identify regular languages.Information and Control, 51, 76?87.","journal-title":"Information and Control"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","volume":"75","author":"D. Angluin","year":"1987","unstructured":"Angluin, D. (1987). Learning regular sets from queries and counterexamples.Information and Computation, 75, 87?106.","journal-title":"Information and Computation"},{"key":"CR4","first-page":"147","volume":"9","author":"D. Angluin","year":"1992","unstructured":"Angluin, D., Frazier, M., & Pitt, L. (1992). Learning conjunctions of Horn Clauses.Machine Learning, 9, 147?164.","journal-title":"Machine Learning"},{"key":"CR5","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1145\/138027.138061","volume":"48","author":"D. Angluin","year":"1993","unstructured":"Angluin, D., Hellerstein, L., & Karpinski, M. (1993). Learning read-once formulas with queries.Journal of the Association for Computing Machinery, 48, 185?210.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"CR6","first-page":"343","volume":"2","author":"D. Angluin","year":"1988","unstructured":"Angluin, D., & Laird, P. (1988). Learning from noisy examples.Machine Learning, 2, 343?370.","journal-title":"Machine Learning"},{"key":"CR7","first-page":"7","volume":"14","author":"D. Angluin","year":"1994","unstructured":"Angluin, D., & Slonim, D. (1994). Randomly fallible teachers: Learning monotone DNF with an incomplete membership oracle.Machine Learning, 14, 7?26.","journal-title":"Machine Learning"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"L. Blum","year":"1993","unstructured":"Blum, L., Luby, M., & Rubinfeld, R. (1993). Self-Testing\/Correcting with applications to numerical problems.Journal of Computer and System Sciences, 47, 549?595.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/0020-0190(87)90114-1","volume":"27","author":"E. Blumer","year":"1987","unstructured":"Blumer, E., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1987). Ocearn's Razor.Information Processing Letters, 27, 377?380.","journal-title":"Information Processing Letters"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"Chernoff, H. (1952). A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations.Annals of the Mathematical Statistics, 23, 493?507.","journal-title":"Annals of the Mathematical Statistics"},{"key":"CR11","first-page":"208","volume-title":"Proceedings of the 10th National Conference on Artificial Intelligence","author":"T. Dean","year":"1992","unstructured":"Dean, T., Angluin, D., Basye, K., Engelson, S., Kaelbling, L., Kokkevis, E., & Maron, O. (1992). Inferring finite automata with stochastic output functions and an application to map learning.Proceedings of the 10th National Conference on Artificial Intelligence, (pp. 208?214). San Jose, CA: AAAI Press."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1137\/0221014","volume":"21","author":"P. Fischer","year":"1992","unstructured":"Fischer, P., & Simon, H. (1992). On learning ring-sum-expansions.SIAM Journal on Computing, 21, 181?192.","journal-title":"SIAM Journal on Computing"},{"key":"CR13","first-page":"315","volume-title":"Proceedings of the 25th Annual ACM Symposium on Theory of Computing","author":"Y. Freund","year":"1993","unstructured":"Freund, Y., Kearns, M. J., Ron, D., Rubinfeld, R., Schapire, R. E., & Sellie, L. (1993). Efficient learning of typical finite automata from random walks.Proceedings of the 25th Annual ACM Symposium on Theory of Computing, (pp. 315?324). San-Diego, CA: ACM Press."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1137\/0222047","volume":"22","author":"S. A. Goldman","year":"1993","unstructured":"Goldman, S. A., Kearns, M. J., & Schapire, R. E. (1993). Exact identification of read-once formulas using fixed points of amplification functions.SIAM Journal on Computing, 22, 705?726.","journal-title":"SIAM Journal on Computing"},{"key":"CR15","first-page":"85","volume-title":"Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory","author":"S. A. Goldman","year":"1992","unstructured":"Goldman, S. A., & Mathias, H. D. (1992). Learningk-term DNF formulas with an incomplete membership oracle.Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory, (pp. 85?92). Pittsburgh, PA: Morgan Kaufmann."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1137\/0221019","volume":"21","author":"D. Helmbold","year":"1992","unstructured":"Helmbold, D., Sloan, R., & Warmuth, M. K. (1992). Learning integer lattices.SIAM Journal on Computing, 21, 240?266.","journal-title":"SIAM Journal on Computing"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables.Journal of the American Statistical Association, 58, 13?30.","journal-title":"Journal of the American Statistical Association"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/B978-0-12-417750-5.50022-1","volume-title":"The Theory of Machines and Computations","author":"J. E. Hoperoft","year":"1971","unstructured":"Hoperoft, J. E. (1971). Ann logn algorithm for minimizing the states in a finite automaton.The Theory of Machines and Computations, 189?196. Academic Press, New York."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0016-0032(54)90574-8","volume":"257","author":"D. A. Huffman","year":"1954","unstructured":"Huffman, D. A. (1954). The synthesis of sequential switching circuits.J. Franklin Institute, 257, 161?190, 275?303.","journal-title":"J. Franklin Institute"},{"key":"CR20","unstructured":"Kearns, M. J. (1990).The Computational Complexity of Machine Learning. MIT Press."},{"key":"CR21","first-page":"392","volume-title":"Proceedings of the 25th Annual ACM Symposium on Theory of Computing","author":"M. J. Kearns","year":"1993","unstructured":"Kearns, M. J. (1993). Efficient noise-tolerant learning from statistical queries.Proceedings of the 25th Annual ACM Symposium on Theory of Computing, (pp. 392?401). San-Diego: ACM Press."},{"key":"CR22","doi-asserted-by":"crossref","first-page":"807","DOI":"10.1137\/0222052","volume":"22","author":"M. J. Kearns","year":"1993","unstructured":"Kearns, M. J., & Li, M. (1993). Learning in the presence of malicious errors.Siam Journal on Computing, 22, 807?837.","journal-title":"Siam Journal on Computing"},{"key":"CR23","first-page":"382","volume-title":"Proceedings of the 31st Annual Symposium on Foundations of Computer Science","author":"M. J. Kearns","year":"1990","unstructured":"Kearns, M. J., & Schapire, R. E. (1990) Efficient distribution-free learning of probabilistic concepts.Proceedings of the 31st Annual Symposium on Foundations of Computer Science, (pp. 382?391). St. Louis, MO: IEEE Computer Society Press. To appear inJCSS."},{"key":"CR24","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/174644.174647","volume":"41","author":"M. J. Kearns","year":"1994","unstructured":"Kearns, M. J., & Valiant, L. G. (1994). Cryptographic limitations on learning boolean formulae and finite automata.Journal of the Association for Computing Machinery, 41, 67?95.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"CR25","doi-asserted-by":"crossref","unstructured":"Laird, P. (1988).Learning From Good Data and Bad. Kluwer Academic Publishers.","DOI":"10.1007\/978-1-4613-1685-5"},{"key":"CR26","first-page":"191","volume":"2","author":"R. Lipton","year":"1991","unstructured":"Lipton, R. (1991). New directions in testing.Distributed Computing and Cryptography, DIMACS Series in Discrete Math and Theoretical Computer Science, American Mathematical Society, 2, 191?202.","journal-title":"Distributed Computing and Cryptography, DIMACS Series in Discrete Math and Theoretical Computer Science, American Mathematical Society"},{"key":"CR27","first-page":"129","volume-title":"Gedanken experiments on sequential machines.Automata Studies","author":"E. F. Moore","year":"1956","unstructured":"Moore, E. F. (1956). Gedanken experiments on sequential machines.Automata Studies, 129?153. Princeton Univ. Press, Princeton, N.J."},{"key":"CR28","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1016\/0022-0000(90)90028-J","volume":"41","author":"L. Pitt","year":"1990","unstructured":"Pitt, L., & Warmuth, M. K. (1990). Prediction-preserving reducibility.Journal of Computer and System Sciences, 41, 430?467.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR29","first-page":"78","volume-title":"Proceedings of the 28th IEEE Symposium on Foundations of Computer Science","author":"R. Rivest","year":"1987","unstructured":"Rivest, R., & Schapire, R. E. (1987). Diversity-based inference of finite automata.Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, (pp. 78?87). Los Angeles, CA: IEEE Computer Science Press. To appear inJACM."},{"key":"CR30","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1006\/inco.1993.1021","volume":"103","author":"R. Rivest","year":"1993","unstructured":"Rivest, R., & Schapire, R. E. (1993). Inference of finite automata using homing sequences.Information and Computation, 103, 299?347.","journal-title":"Information and Computation"},{"key":"CR31","first-page":"218","volume-title":"Proceedings of the 6th Annual ACM Workshop on Computational Learning Theory","author":"D. Ron","year":"1993","unstructured":"Ron, D., & Rubinfeld, R. (1993). Learning fallible finite state automata.Proceedings of the 6th Annual ACM Workshop on Computational Learning Theory, (pp. 218?227). Santa-Cruz, CA: Morgan Kaufmann."},{"key":"CR32","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/0020-0190(91)90220-C","volume":"37","author":"Y. Sakakibara","year":"1991","unstructured":"Sakakibara, Y. (1991). On learning from queries and counterexamples in the presence of noise.Information Processing Letters, 37, 279?284.","journal-title":"Information Processing Letters"},{"key":"CR33","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1145\/130385.130418","volume-title":"Proceedings of the 5th Annual Workshop on Computational Learning Theory","author":"Y. Sakakibara","year":"1992","unstructured":"Sakakibara, Y., & Siromoney, R. (1992). A noise model on learning sets of strings.Proceedings of the 5th Annual Workshop on Computational Learning Theory (pp. 295?302). Pittsburgh, PA: Morgan Kaufmann."},{"key":"CR34","unstructured":"Schapire, R. E. (1991).The Design and Analysis of Efficient Learning Algorithms. MIT Press."},{"key":"CR35","first-page":"97","volume-title":"Proceedings of the 1988 Workshop on Computational Learning Theory","author":"G. Shackelford","year":"1988","unstructured":"Shackelford, G., & Volper, D. (1988). Learningk-DNF with noise in the attributes.Proceedings of the 1988 Workshop on Computational Learning Theory, (pp. 97?103). Cambridge, MA: Morgan Kaufmann."},{"key":"CR36","first-page":"91","volume-title":"Proceedings of the 1988 Workshop on Computational Learning Theory","author":"R. H. Sloan","year":"1988","unstructured":"Sloan, R. H. (1988). Types of noise in data for concept learning.Proceedings of the 1988 Workshop on Computational Learning Theory, (pp. 91?96). Cambridge MA: Morgan Kaufmann."},{"key":"CR37","volume-title":"Computational Learning Theory: New Models and Algorithms","author":"R. H. Sloan","year":"1989","unstructured":"Sloan, R. H. (1989).Computational Learning Theory: New Models and Algorithms. Doctoral dissertation, Department of Computer Science, Massachusetts Institute of Technology, Cambridge, MA. Issued as MIT\/LCS\/TR-448."},{"key":"CR38","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. G. Valiant","year":"1984","unstructured":"Valiant, L. G. (1984). A theory of the learnable.Communications of the ACM, 27, 1134?1142.","journal-title":"Communications of the ACM"},{"key":"CR39","first-page":"560","volume-title":"Proceedings of the 9th International Joint Conference on Artificial Intelligence","author":"L. G. Valiant","year":"1985","unstructured":"Valiant, L. G. (1985). Learning disjunctions of conjunctions.Proceedings of the 9th International Joint Conference on Artificial Intelligence, (pp. 560?566). Los Angeles, CA: Morgan Kaufmann."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00993409.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00993409\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00993409","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,4]],"date-time":"2021-07-04T02:07:23Z","timestamp":1625364443000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00993409"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"references-count":39,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[1995]]}},"alternative-id":["BF00993409"],"URL":"https:\/\/doi.org\/10.1007\/bf00993409","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]}}}