{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,30]],"date-time":"2023-11-30T08:52:27Z","timestamp":1701334347177},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1992,3,1]],"date-time":"1992-03-01T00:00:00Z","timestamp":699408000000},"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":[[1992,3]]},"DOI":"10.1007\/bf00992862","type":"journal-article","created":{"date-parts":[[2005,1,9]],"date-time":"2005-01-09T11:53:01Z","timestamp":1105271581000},"page":"151-166","source":"Crossref","is-referenced-by-count":7,"title":["Learning probabilistic automata and Markov chains via queries"],"prefix":"10.1007","volume":"8","author":[{"given":"Wen-Guey","family":"Tzeng","sequence":"first","affiliation":[]}],"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":"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","first-page":"319","volume":"2","author":"D. Angluin","year":"1987","unstructured":"Angluin, D. (1987a). Queries and concept learning.Machine Learning, 2 319?342.","journal-title":"Machine Learning"},{"key":"CR4","first-page":"87","volume":"75","author":"D. Angluin","year":"1987","unstructured":"Angluin, D. (1987b). Learning regular sets from queries and counterexamples.Information and Control, 75 87?106.","journal-title":"Information and Control"},{"key":"CR5","series-title":"Technical Report YALEU\/DCS\/RR-559","volume-title":"Learning k-term DNF formulas using queries and counterexamples","author":"D. Angluin","year":"1987","unstructured":"Angluin, D. (1987c).Learning k-term DNF formulas using queries and counterexamples (Technical Report YALEU\/DCS\/RR-559). New Haven, CT: Yale University, Computer Science Department."},{"key":"CR6","series-title":"Technical Report YALEU\/DCS\/RR-648","volume-title":"Negative results for equivalence queries","author":"D. Angluin","year":"1988","unstructured":"Angluin, D. (1988).Negative results for equivalence queries (Technical Report YALEU\/DCS\/RR-648). New Haven, CT: Yale University, Computer Science Department."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/B978-0-08-094829-4.50012-X","volume-title":"Proceedings of the Second Workshop on Computational Learning Theory","author":"D. Angluin","year":"1989","unstructured":"Angluin, D. (1989). Equivalence queries and approximate fingerprints.Proceedings of the Second Workshop on Computational Learning Theory (pp. 134?145). San Mateo, CA: Morgan Kaufmann."},{"key":"CR8","series-title":"Technical Report UCB\/CSD 89-528","volume-title":"Learning read-once formulas with queries","author":"D. Angluin","year":"1989","unstructured":"Angluin, D., Hellerstein, L., & Karpinski, M. (1989).Learning read-once formulas with queries (Technical Report UCB\/CSD 89-528). Berkeley, CA: University of California-Berkeley, Computer Science Division (EECS)."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M.K. (1989). Learnability and the Vapnik-Chervonenkis dimension.Journal of the Association for Computing Machinery, 36 929?965.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"CR10","first-page":"54","volume-title":"Proceedings of the Twenty-Second Annual Symposium on Theory of Computing","author":"R. Board","year":"1990","unstructured":"Board, R., & Pitt, L. (1990). On the necessity of Occam algorithms.Proceedings of the Twenty-Second Annual Symposium on Theory of Computing (pp. 54?63). New York: NY: ACM Press."},{"key":"CR11","doi-asserted-by":"crossref","DOI":"10.1037\/14496-000","volume-title":"Stochastic models for learning","author":"R.R. Bush","year":"1955","unstructured":"Bush, R.R., & Mosteller, F. (1955).Stochastic models for learning. New York, NY: Wiley."},{"key":"CR12","first-page":"110","volume-title":"Proceedings of the Twenty-Ninth Annual Symposium on Foundations of Computer Science","author":"A. DeSantis","year":"1988","unstructured":"DeSantis, A., Markowsky, G., Wegman, M.N. (1988). Learning probabilistic prediction functions,Proceedings of the Twenty-Ninth Annual Symposium on Foundations of Computer Science (pp. 110?119). Los Alamitos, CA: IEEE Press."},{"key":"CR13","volume-title":"Proceedings of Symposium on Computer and Information Science","author":"K.S. Fu","year":"1966","unstructured":"Fu, K.S. (1966). Stochastic automata as models of learning systems.Proceedings of Symposium on Computer and Information Science. Columbus, OH: Purdue University."},{"key":"CR14","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 automaton identification from given data.Information and Control, 37 302?320.","journal-title":"Information and Control"},{"key":"CR15","first-page":"42","volume-title":"Proceedings of the First Workshop on Computational Learning Theory","author":"D. Haussler","year":"1988","unstructured":"Haussler, D., Kearns, M., Littlestone, M., & Warmuth, M.K. (1988). Equivalence of models for polynomial learnability.Proceedings of the First Workshop on Computational Learning Theory (pp. 42?55). San mateo, CA: Morgan Kaufmann."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N. Karmarkar","year":"1984","unstructured":"Karmarkar, N. (1984). A new polynomial-time algorithm for linear programming.Combinatorica, 4 373?395.","journal-title":"Combinatorica"},{"key":"CR17","first-page":"285","volume-title":"Proceedings of the Nineteenth Annual Symposium on Theory of Computing","author":"M. Kearns","year":"1987","unstructured":"Kearns, M., Li, M., Pitt, L., & Valiant, L.G. (1987). On the learnability of boolean formulae.Proceedings of the Nineteenth Annual Symposium on Theory of Computing (pp. 285?295). New York, NY: ACM Press."},{"key":"CR18","first-page":"433","volume-title":"Proceedings of the Twenty-First Annual Symposium on Theory of Computing","author":"M. Kearns","year":"1989","unstructured":"Kearns, M., & Valiant, L.G. (1989). Cryptographic limitations on learning Boolean formulae and finite automata.Proceedings of the Twenty-First Annual Symposium on Theory of Computing (pp. 433?444). New York, NY: ACM Press."},{"key":"CR19","first-page":"191","volume":"20","author":"L.G. Khachiyan","year":"1979","unstructured":"Khachiyan, L.G. (1979). A polynomial algorithm in linear programming (in Russian). Translated inSoviet Mathematics Doklady, 20, 191?194.","journal-title":"Translated in Soviet Mathematics Doklady"},{"key":"CR20","volume-title":"Introduction to probabilistic automata","author":"A. Paz","year":"1971","unstructured":"Paz, A. (1971)Introduction to probabilistic automata. New York, NY: Academic Press."},{"key":"CR21","series-title":"Technical Report UIUCDCS-R-89-1530","volume-title":"Inductive inference, DFAs, and computational complexity","author":"L. Pitt","year":"1989","unstructured":"Pitt, L. (1989).Inductive inference, DFAs, and computational complexity (Technical Report UIUCDCS-R-89-1530). Champaign, IL: University of Illinois at Urbana-Champaign, Department of Computer Science."},{"key":"CR22","first-page":"421","volume-title":"Proceedings of the Twenty-First Annual Symposium on theory of Computing","author":"L. Pitt","year":"1989","unstructured":"Pitt, L., & Warmuth, M.K. (1989). The minimum consistent DFA problem cannot be approximated within any polynomial.Proceedings of the Twenty-First Annual Symposium on theory of Computing (pp. 421?432). New York, NY: ACM Press."},{"key":"CR23","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1016\/0022-0000(90)90028-J","volume":"43","author":"L. Pitt","year":"1990","unstructured":"Pitt, L., & Warmuth, M.K. (1990). Prediction-preserving reducibility.Journal of Computer and System Sciences, 43 430?467.","journal-title":"Journal of Computer and System Sciences"},{"key":"CR24","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","volume":"6","author":"M.O. Rabin","year":"1963","unstructured":"Rabin, M.O. (1963). Probabilistic automata.Information and Control, 6 230?245.","journal-title":"Information and Control"},{"key":"CR25","first-page":"321","volume-title":"Proceedings of the Twenty-Sixth Annual Symposium on Foundations of Computer Science","author":"S. Rudich","year":"1985","unstructured":"Rudich, S. (1985). Inferring the structure of a Markov chain from its output.Proceedings of the Twenty-Sixth Annual Symposium on Foundations of Computer Science (1989) (pp. 321?326). Los Alamitos, CA: IEEE Press."},{"key":"CR26","unstructured":"Tzeng, W. (1990). A polynomial-time algorithm for the equivalence of probabilistic automata. Submitted for publication."},{"key":"CR27","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 Association for Computing Machinery, 27 1134?1142.","journal-title":"Communications of the Association for Computing Machinery"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00992862.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00992862\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00992862","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T18:58:37Z","timestamp":1556564317000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00992862"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,3]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1992,3]]}},"alternative-id":["BF00992862"],"URL":"https:\/\/doi.org\/10.1007\/bf00992862","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,3]]}}}