{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:08:24Z","timestamp":1760202504303},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","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,1]]},"DOI":"10.1007\/bf00993822","type":"journal-article","created":{"date-parts":[[2005,1,9]],"date-time":"2005-01-09T17:18:54Z","timestamp":1105291134000},"page":"81-108","source":"Crossref","is-referenced-by-count":10,"title":["Inferring finite automata with stochastic output functions and an application to map learning"],"prefix":"10.1007","volume":"18","author":[{"given":"Thomas","family":"Dean","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dana","family":"Angluin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kenneth","family":"Basye","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sean","family":"Engelson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leslie","family":"Kaelbling","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evangelos","family":"Kokkevis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oded","family":"Maron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"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. (1978). On the complexity of minimum inference of regular sets.Information and Control 39:337?350.","journal-title":"Information and Control"},{"key":"CR2","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":"CR3","doi-asserted-by":"crossref","unstructured":"Aslam, J.A., & Rivest, R.L. (1990). Inferring graphs from walks. InProceedings COLT-88.","DOI":"10.1016\/B978-1-55860-146-8.50031-X"},{"key":"CR4","unstructured":"Bachrach, J.R. (1992). Connectionist modeling and control of finite state environments. Technical Report 92-6, University of Massachusetts at Amherst Department of Computer and Information Science."},{"key":"CR5","unstructured":"Basye, K., & Dean, T. (1989). Map learning with indistinguishable locations. InProceedings of the Fifth Workshop on Uncertainty in AI. 7?13."},{"key":"CR6","first-page":"663","volume":"IJCAII","author":"K. Basye","year":"1989","unstructured":"Basye, K., Dean, T., & Vitter, J.S. (1989). Coping with uncertainty in map learning. InProceedings IJCAI 11. IJCAII, 663?668.","journal-title":"Proceedings IJCAI 11"},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"Basye, K., Dean, T., & Kaelbling, L. (to appear). Learning dynamics: System identification for perceptually challenged agents.Artificial Intelligence.","DOI":"10.1016\/0004-3702(94)00023-T"},{"key":"CR8","series-title":"Technical report","volume-title":"A framework for map construction","author":"K. Basye","year":"1992","unstructured":"Basye, K. (1992). A framework for map construction. Technical report, Brown University Department of Computer Science, Providence, RI."},{"key":"CR9","first-page":"1010","volume":"AAAI","author":"T. Dean","year":"1990","unstructured":"Dean, T., Basye, K., Chekaluk, R., Hyun, S., Lejter, M., & Randazza, M. (1990). Coping with uncertainty in a control system for navigation and exploration. InProceedings AAAI-90. AAAI. 1010?1015.","journal-title":"Proceedings AAAI-90"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"Donald, B., & Jennings, J. (1991). Sensor interpretation and task-directed planning using perceptual equivalence classes. Technical Report CU-CS-TR, Cornell University Computer Science Department.","DOI":"10.1109\/ROBOT.1991.131977"},{"key":"CR11","unstructured":"Dudek, G., Jenkins, M., Milios, E., & Wilkes, D. (1988). Robotic exploration as graph construction. Technical Report RBCV-TR-88-23, University of Toronto."},{"key":"CR12","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. (1972). System identification via state characterization.Automatica 8:621?636.","journal-title":"Automatica"},{"key":"CR13","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. (1978). Complexity of automation identification from given sets.Information and Control 37:302?320.","journal-title":"Information and Control"},{"key":"CR14","volume-title":"Adaptive Filtering Prediction and Control","author":"G.C. Goodwin","year":"1984","unstructured":"Goodwin, G.C., & Sin, K.S. (1984).Adaptive Filtering Prediction and Control. Prentice-Hall, Englewood Cliffs, New Jersey."},{"key":"CR15","unstructured":"Kaelbling, L., Basye, K., Dean, T., Kokkevis, E., & Maron, O. (1992). Robot map-learning as learning labeled graphs from noisy data. Technical Report CS-92-15, Brown University Department of Computer Science."},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"Kearns, M., & Valiant, L.G. (1989). Cryptographic limitations on learning boolean functions and finite automata. InProceedings of the Twenty First Annual ACM Symposium on Theoretical Computing. 433?444.","DOI":"10.1145\/73007.73049"},{"key":"CR17","first-page":"774","volume":"AAAI","author":"B.J. Kuipers","year":"1988","unstructured":"Kuipers, B.J., & Byun, Y.-T. (1988). A robust, qualitative method for robot spatial reasoning. InProceedings AAAI-88. AAAI. 774?779.","journal-title":"Proceedings AAAI-88"},{"key":"CR18","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1207\/s15516709cog0202_3","volume":"2","author":"B. Kuipers","year":"1978","unstructured":"Kuipers, B. (1978). Modeling spatial knowledge.Cognitive Science 2:129?153.","journal-title":"Cognitive Science"},{"issue":"4","key":"CR19","doi-asserted-by":"crossref","first-page":"1035","DOI":"10.1002\/j.1538-7305.1983.tb03114.x","volume":"62","author":"S.E. Levinson","year":"1983","unstructured":"Levinson, S.E., Rabiner, L.R., & Sondhi, M.M. (1983). An introduction to the application of the theory of probabilistic functions of a Markov process to automatic speech recognition.The Bell System Technical Journal 62(4):1035?1074.","journal-title":"The Bell System Technical Journal"},{"key":"CR20","first-page":"689","volume":"AAAI","author":"T.S. Levitt","year":"1987","unstructured":"Levitt, T.S., Lawton, D.T., Chelberg, D.M., & Nelson, P.C. (1987). Qualitative landmark-based path planning and following. InProceedings AAAI-87. AAAI. 689?694.","journal-title":"Proceedings AAAI-87"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1515\/9781400882618-006","volume-title":"Automata Studies","author":"E.F. Moore","year":"1956","unstructured":"Moore, E.F. (1956). Gedanken-experiments on sequential machines. InAutomata Studies. Princeton University Press, Princeton, New Jersey. 129?153."},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"Pitt, L., & Warmuth, M.K. (1989). The minimum consistent DFA problem cannot be approximated within any polynomial. InProceedings of the Twenty First Annual ACM Symposium on Theoretical Computing. 421?432.","DOI":"10.1109\/SCT.1989.41829"},{"issue":"1","key":"CR23","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF00130489","volume":"7","author":"R.D. Rimey","year":"1991","unstructured":"Rimey, R.D., & Brown, C.M. (1991). Controlling eye movements with hidden Markov models.International Journal of Computer Vision 7(1):47?65.","journal-title":"International Journal of Computer Vision"},{"key":"CR24","doi-asserted-by":"crossref","unstructured":"Rivest, R.L., & Schapire, R.E. (1987). Diversity-based inference of finite automata. InProceedings of the Twenty Eighth Annual Symposium on Foundations of Computer Science. 78?87.","DOI":"10.1109\/SFCS.1987.21"},{"key":"CR25","doi-asserted-by":"crossref","unstructured":"Rivest, R.L., & Schapire, R.E. (1989). Inference of finite automata using homing sequences. InProceedings of the Twenty First Annual ACM Symposium on Theoretical Computing. 411?420.","DOI":"10.1145\/73007.73047"},{"key":"CR26","doi-asserted-by":"crossref","unstructured":"Rudich, S. (1985). Inferring the structure of a Markov chain from its output. InProceedings of the Twenty Sixth Annual Symposium on Foundations of Computer Science. 321?326.","DOI":"10.1109\/SFCS.1985.34"},{"key":"CR27","unstructured":"Schapire, R.E. (1991). The design and analysis of efficient learning algorithms. Technical Report MIT\/LCS\/TR-493, MIT Laboratory for Computer Science."},{"key":"CR28","first-page":"151","volume":"8","author":"W.-G. Tzeng","year":"1992","unstructured":"Tzeng, W.-G. (1992). Learning probabilistic automata and Markov chains via queries.Machine Learning 8:151?166.","journal-title":"Machine Learning"},{"key":"CR29","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":"CR30","doi-asserted-by":"crossref","unstructured":"Whitehead, S.D., & Ballard, D.H. (1991). Learning to perceive and act by trial and error.Machine Learning 7.","DOI":"10.1007\/BF00058926"},{"key":"CR31","volume-title":"Adaptive Signal Processing","author":"B. Widrow","year":"1985","unstructured":"Widrow, B., & Stearns, S.D. (1985).Adaptive Signal Processing. Prentice-Hall, Englewood Cliffs, N.J."},{"key":"CR32","doi-asserted-by":"crossref","unstructured":"Yannakakis, M., & Lee, D. (1991). Testing finite state machines. InACM Symposium on Theoretical Computing. ACM Press. 476?485.","DOI":"10.1145\/103418.103468"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00993822.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00993822\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00993822","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,3]],"date-time":"2021-07-03T21:26:48Z","timestamp":1625347608000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00993822"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,1]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1995,1]]}},"alternative-id":["BF00993822"],"URL":"https:\/\/doi.org\/10.1007\/bf00993822","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,1]]}}}