{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T19:55:09Z","timestamp":1770753309913,"version":"3.50.0"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540564836","type":"print"},{"value":"9783540475682","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56483-7_22","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:11:32Z","timestamp":1330254692000},"page":"51-73","source":"Crossref","is-referenced-by-count":23,"title":["Inference of finite automata using homing sequences"],"prefix":"10.1007","author":[{"given":"Ronald L.","family":"Rivest","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert E.","family":"Schapire","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,6]]},"reference":[{"key":"5_CR1","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/S0019-9958(78)90683-6","volume":"39","author":"D. Angluin","year":"1978","unstructured":"Angluin, D. On the complexity of minimum inference of regular sets. Information, and Control 39 (1978) 337\u2013350.","journal-title":"Information, and Control"},{"key":"5_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. A note on the number of queries needed to identify regular languages. Information and Control 51 (1981) 76\u201387.","journal-title":"Information and Control"},{"key":"5_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. Learning regular sets from queries and counterexamples. Information and Computation 75 (1987) 87\u2013106.","journal-title":"Information and Computation"},{"key":"5_CR4","unstructured":"Dean, T., Angluin, D., Basye, K., Engelson, S., Kaelbling, L., Kokkevis, E., and Maron, O. Inferring finite automata with stochastic output functions and an application to map learning. In Proceedings Tenth National Conference on Artificial Intelligence (1992) 208\u2013214."},{"key":"5_CR5","unstructured":"Drescher, G. L. Genetic AI\u2014translating Piaget into Lisp. MIT Artificial Intelligence Laboratory Technical Report 890 (1986)."},{"key":"5_CR6","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1016\/0005-1098(72)90033-7","volume":"8","author":"E. M. Gold","year":"1972","unstructured":"Gold, E. M. System identification via state characterization. Automatica 8 (1972) 621\u2013636.","journal-title":"Automatica"},{"key":"5_CR7","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1016\/S0019-9958(78)90562-4","volume":"37","author":"E. M. Gold","year":"1978","unstructured":"Gold, E. M. Complexity of automaton identification from given data. Information and Control 37 (1978) 302\u2013320.","journal-title":"Information and Control"},{"key":"5_CR8","doi-asserted-by":"crossref","unstructured":"Kearns M. and Valiant, L. G. Cryptographic limitations on learning Boolean formulae and finite automata. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing (1989) 433\u2013444. (Also Journal of the Association for Computing Machinery, to appear).","DOI":"10.1145\/73007.73049"},{"key":"5_CR9","unstructured":"Kohavi, Z. Switching and Finite Automata Theory. McGraw-Hill, Second Edition (1978)."},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"Benjamin J. Kuipers and Yung-Tai Byun. A robust, qualitative approach to a spatial learning mobile robot. In SPIE Advances in Intelligent Robotics Systems (1988).","DOI":"10.1117\/12.948951"},{"key":"5_CR11","unstructured":"Mataric, M. J. A distributed model for mobile robot environment-learning and navigation. Massachusetts Institute of Technology Master's thesis (1990). (Also MIT Artificial Intelligence Laboratory Technical Report AI-TR 1228)."},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"Pitt, L. Inductive inference, DFAs, and computational complexity. University of Illinois at Urbana-Champaign Department of Computer Science Technical Report UIUCDCS-R-89-1530 (1989).","DOI":"10.1007\/3-540-51734-0_50"},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"Pitt, L. and Warmuth, M. K. The minimum consistent DFA problem cannot be approximated within any polynomial. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing (1989). (Also University of Illinois at Urbana-Champaign, Department of Computer Science Technical Report UIUCDCS-R-89-1499 and Journal of the Association for Computing Machinery, to appear).","DOI":"10.1145\/73007.73048"},{"issue":"3","key":"5_CR14","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. and Warmuth, M. K. Prediction-preserving reducibility. Journal of Computer and System Sciences 41(3) (1990) 430\u2013467.","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR15","doi-asserted-by":"crossref","unstructured":"Rivest, R. L. and Schapire, R. E. Diversity-based inference of finite automata. In 28th Annual Symposium on Foundations of Computer Science (1987) 78\u201387. (Also Journal of the Association for Computing Machinery, to appear).","DOI":"10.1109\/SFCS.1987.21"},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"Rivest, R. L. and Schapire, R. E. A new approach to unsupervised learning in deterministic environments. In Machine Learning: An Artificial Intelligence Approach, Volume III. Yves Kodratoff and Ryszard Michalski, editors. Morgan Kaufmann (1990) 670\u2013684.","DOI":"10.1016\/B978-0-08-051055-2.50032-8"},{"key":"5_CR17","unstructured":"Schapire, R. E. Diversity-based inference of finite automata. Massachusetts Institute of Technology Master's thesis (1988). (Also MIT Laboratory for Computer Science Technical Report MIT\/LCS\/TR-413)."},{"key":"5_CR18","unstructured":"Schapire, R. E. The Design and Analysis of Efficient Learning Algorithms. MIT Press (1992)."},{"key":"5_CR19","unstructured":"Wilson, S. W. Knowledge growth in an artificial animal. In Proceedings of an International Conference on Genetic Algorithms and their Applications (1985) 16\u201323."}],"container-title":["Lecture Notes in Computer Science","Machine Learning: From Theory to Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56483-7_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:03:54Z","timestamp":1605647034000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56483-7_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540564836","9783540475682"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-56483-7_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993]]}}}