{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T06:00:13Z","timestamp":1789711213062,"version":"4.0.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1997,4,1]],"date-time":"1997-04-01T00:00:00Z","timestamp":859852800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1997,4,1]],"date-time":"1997-04-01T00:00:00Z","timestamp":859852800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Machine Learning"],"published-print":{"date-parts":[[1997,4]]},"DOI":"10.1023\/a:1007348927491","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T04:48:21Z","timestamp":1040532501000},"page":"69-96","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Exactly Learning Automata of Small Cover Time"],"prefix":"10.1007","volume":"27","author":[{"given":"Dana","family":"Ron","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"130972_CR1","doi-asserted-by":"crossref","unstructured":"Aleliunas, R., & Karp, R. M., & Lipton, R. J., & Lov\u00e1sz, L., & Rackoff, C. (1979). Random walks, universal traversal sequences, and the complexity of maze problems. In Proceedings of the Twentieth Annual Symposium on Foundations of Computer Science (pp. 218-223).","DOI":"10.1109\/SFCS.1979.34"},{"key":"130972_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":"130972_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 counter examples. Information and Computation, 75,87-106.","journal-title":"Information and Computation"},{"key":"130972_CR4","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1023\/A:1022692615781","volume":"5","author":"D. Angluin","year":"1990","unstructured":"Angluin D. (1990). Negative results for equivalence queries. Machine Learning, 5,121-150.","journal-title":"Machine Learning"},{"key":"130972_CR5","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1023\/A:1022873112823","volume":"2","author":"D. Angluin","year":"1988","unstructured":"Angluin, D., & and Laird, P. (1988). Learning from noisy examples. Machine Learning, 2,343-370.","journal-title":"Machine Learning"},{"key":"130972_CR6","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1145\/356914.356918","volume":"15","author":"D. Angluin","year":"1983","unstructured":"Angluin. D., & Smith, C. H. (1983). Inductive inference: Theory and methods. Computing Surveys, 15,237-269.","journal-title":"Computing Surveys"},{"key":"130972_CR7","doi-asserted-by":"crossref","unstructured":"Bender, M., & Slonim, D. (1994). The power of team exploration: Two robots can learn unlabeled directed graphs. In Proceedings of the Thirty Fifth Annual Symposium on Foundations of Computer Science (pp. 75-85).","DOI":"10.1109\/SFCS.1994.365703"},{"key":"130972_CR8","doi-asserted-by":"crossref","unstructured":"Bergando, F., & Varricchio, S. (1994). Learning behaviors of automata from multiplicity and equivalnece queries. In Algorithms and complexity, Proceedings of the 2nd Italian conference (pp. 54-62). To appear in Siam J. of Computing.","DOI":"10.1007\/3-540-57811-0_6"},{"key":"130972_CR9","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1023\/A:1022874607797","volume":"18","author":"T. Dean","year":"1995","unstructured":"Dean, T., & Angluin, D., & Basye, K., & Engelson, S., & Kaelbling, L., & Kokkevis, D., & Maron, O. (1995). Inferring finite automata with stochastic output functions and an application to map learning. Machine Learning, 18,81-108.","journal-title":"Machine Learning"},{"key":"130972_CR10","doi-asserted-by":"crossref","unstructured":"Erg\u00fcn, F., & Ravikumar, S., & Rubinfeld, R. (1995). On learning bounded-width branching programs. In Proceedings of the Eighth Annual ACM Conference on Computational Learning Theory (pp. 361-368).","DOI":"10.1145\/225298.225342"},{"key":"130972_CR11","doi-asserted-by":"crossref","unstructured":"Fortnow, L., & Whang, D. (1994). Optimality and domination in repeated games with bounded players. In The 25th Annual ACM Symposium on Theory of Computing, (pp. 741-749).","DOI":"10.1145\/195058.195448"},{"key":"130972_CR12","doi-asserted-by":"crossref","unstructured":"Frazier, M., & Goldman, S., & Mishra, N., & Pitt, L. (1994). Learning from a consistently ignorant teacher. In Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory (pp. 328-339). To appear in Journal of Computer Systems Science.","DOI":"10.1145\/180139.181170"},{"key":"130972_CR13","doi-asserted-by":"crossref","unstructured":"Freund, Y., & Kearns, M., & Mansour, Y., & Ron, D., & Rubinfeld, R., & Schapire, R. (1995). Efficient algorithms for learning to play repeated games against computationally bounded adversaries. In Proceedings of the Thirty Seventh Annual Symposium on Foundations of Computer Science (pp 332-341).","DOI":"10.1109\/SFCS.1995.492489"},{"key":"130972_CR14","doi-asserted-by":"crossref","unstructured":"Freund, Y., & Kearns, M., & Ron, D., & Rubinfeld, R., & Schapire, R., & Sellie, R. (1993). Efficient learning of typical finite automata from random walks. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (pp. 315-324).","DOI":"10.1145\/167088.167191"},{"key":"130972_CR15","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/0899-8256(89)90009-2","volume":"1","author":"I. Gilboa","year":"1989","unstructured":"Gilboa, I., & and Samet, D. (1989). Bounded versus unbounded rationality: The tyranny of the weak. Games and Economic Behavior, 1,213-221.","journal-title":"Games and Economic Behavior"},{"key":"130972_CR16","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":"130972_CR17","unstructured":"Ibarra, O., & Jiang, T. (1988). Learning regular languaages from counterexamples. In Proceedings of the 1988 Workshop on Computational Learning Theory, (pp. 371-385)."},{"key":"130972_CR18","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/174644.174647","volume":"41","author":"M. Kearns","year":"1994","unstructured":"Kearns, M. & Valiant, L. (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":"130972_CR19","unstructured":"Kohavi, Z. (1978). Switching and Finite Automata Theory. McGraw-Hill, second edition."},{"key":"130972_CR20","unstructured":"Li, M., & Vazirani, U. (1988). On the learnability of finite automata. In Proceedings of the 1988 Workshop on Computational Learning Theory, (pp. 359-370)."},{"key":"130972_CR21","doi-asserted-by":"crossref","unstructured":"Motwani, R., & Raghavan, P. (1995). Randomized Algorithms. Cambridge University Press, first edition.","DOI":"10.1017\/CBO9780511814075"},{"key":"130972_CR22","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1006\/inco.1993.1021","volume":"103","author":"R. Rivest","year":"1993","unstructured":"Rivest, R., & Schapire, R. (1993). Inference of finite automata using homing sequences. Information and Computation, 103,299-347.","journal-title":"Information and Computation"},{"key":"130972_CR23","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/176584.176589","volume":"43","author":"R. Rivest","year":"1994","unstructured":"Rivest, R., & Schapire, R. (1994). Diversity-based inference of finite automata. Journal of the Association for Computing Machinery, 43,555-589.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"130972_CR24","unstructured":"Rivest, R., & Zuckermann, D. (1992). Private communication."},{"key":"130972_CR25","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1023\/A:1022899313248","volume":"18","author":"D. Ron","year":"1995","unstructured":"Ron, D., & Rubinfeld, R. (1995). Learning fallible finite state automata. Machine Learning, 18,149-185.","journal-title":"Machine Learning"},{"key":"130972_CR26","doi-asserted-by":"publisher","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 couterexamples in the presence of noise. Information Processing Letters, 37,279-284.","journal-title":"Information Processing Letters"},{"key":"130972_CR27","unstructured":"Schapire, R., & Warmuth, M. (1990). Presented at COLT90 rump session, 1990."},{"key":"130972_CR28","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0890-5401(89)90067-9","volume":"82","author":"A. Sinclair","year":"1989","unstructured":"Sinclair, A., & Jerrum, M. (1989) Approximate counting, uniform generation, and rapidly mixing Markov chains. Information and Computation, 82,93-13.","journal-title":"Information and Computation"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1007348927491.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1007348927491\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1007348927491.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,10]],"date-time":"2025-07-10T11:30:27Z","timestamp":1752147027000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1007348927491"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,4]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1997,4]]}},"alternative-id":["130972"],"URL":"https:\/\/doi.org\/10.1023\/a:1007348927491","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,4]]},"assertion":[{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}