{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,10]],"date-time":"2026-10-10T14:41:17Z","timestamp":1791643277047,"version":"4.3.4"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2-3","license":[{"start":{"date-parts":[[1992,7,1]],"date-time":"1992-07-01T00:00:00Z","timestamp":709948800000},"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,7]]},"DOI":"10.1007\/bf00992677","type":"journal-article","created":{"date-parts":[[2005,1,14]],"date-time":"2005-01-14T17:44:17Z","timestamp":1105724657000},"page":"205-260","source":"Crossref","is-referenced-by-count":44,"title":["On the computational complexity of approximating distributions by probabilistic automata"],"prefix":"10.1007","volume":"9","author":[{"given":"Naoki","family":"Abe","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manfred K.","family":"Warmuth","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"CR1","volume-title":"Proceedings of the 1991 Workshop on Computational Learning Theory","author":"N. Abe","year":"1991","unstructured":"Abe, N., Takeuchi, J., & Warmuth, M. K., (1991). Polynomial learnability of probabilistic concepts with respect to the Kullback-Leibler divergence. InProceedings of the 1991 Workshop on Computational Learning Theory. San Mateo, CA: Morgan Kaufmann."},{"key":"CR2","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 minimal inference of regular sets.Information and Control, 39 337?350.","journal-title":"Information and Control"},{"key":"CR3","unstructured":"Angluin, D., (1988).Identifying languages from stochastic examples (Technical Report YALEU\/DCS\/RR-614). Yale University."},{"key":"CR4","unstructured":"Angluin, D., (1989).Minimum consistent 2-state DFA problem is NP-complete. Unpublished manuscript."},{"key":"CR5","unstructured":"Barron, A.R. & Cover, T.M., (1989). Minimum complexity density estimation.IEEE Transactions on Information Theory."},{"key":"CR6","first-page":"1","volume":"3","author":"L.E. Baum","year":"1972","unstructured":"Baum, L.E., (1972). An inequality and associated maximization technique in statistical estimation for probabilistic functions of a Markov process.Inequalities, 3 1?8.","journal-title":"Inequalities"},{"key":"CR7","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, (1989). Learnability and the Vapnik-Chervonenkis dimension.Journal of the ACM, 36 929?965.","journal-title":"Journal of the ACM"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"Gill, J., (1977) Probabilistic Turing machines.SLAM J. Comput., 6 675?695.","journal-title":"SLAM J. Comput."},{"key":"CR9","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":"CR10","unstructured":"Hamming, R.W., (1986). Coding and Information Theory, Second Edition. Prentice-Hall."},{"key":"CR11","unstructured":"Haussler, D., (1991). Decision theoretic generalizing of the pac model for neural net and other learning applications.Information and Computation. To appear. (An extended abstract appeared in the Proceedings of FOCS '89.)"},{"key":"CR12","unstructured":"Kearns, M., & Schapire, R., (1990). Efficient distribution-free learning of probabilitic concepts. InProceedings of IEEE Symposium on Foundations of Computer Science."},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"Kullback, S., (1967). A lower bound for discrimination in terms of variation.IEEE Transactions on Information Theory, 126?127.","DOI":"10.1109\/TIT.1967.1053968"},{"key":"CR14","volume-title":"Proceedings of the 1988 Workshop on Computational Learning Theory","author":"P.D. Laird","year":"1988","unstructured":"Laird, P.D. (1988). Efficient unsupervised learning. InProceedings of the 1988 Workshop on Computational Learning Theory. San Mateo, CA: Morgan Kaufmann."},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"Levinson, S.E., Rabiner, L.R., & Sondhi, M.M., (1983). An introduction to the application of the theory of the probabilistic functions of a Markov process to automatic speech recognition.The Bell System Technical Journal, 62.","DOI":"10.1002\/j.1538-7305.1983.tb03114.x"},{"key":"CR16","doi-asserted-by":"crossref","unstructured":"Pitt, L., & Warmuth, M.K., (1989). The minimum consistent DFA problem cannot be approximated within any polynomial. InProc. 19th ACM Symp. on Theory of Computation. To appear in JACM.","DOI":"10.1109\/SCT.1989.41829"},{"key":"CR17","doi-asserted-by":"crossref","unstructured":"Pollard, D., (1984).Convergence of Stochastic Processes. Springer-Verlag.","DOI":"10.1007\/978-1-4612-5254-2"},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"Tzeng, W., (1989). The equivalence and learning of probabilistic automata. InProceedings of the 30th IEEE Annual Symposium on the Foundations of Computer Science.","DOI":"10.1109\/SFCS.1989.63489"},{"key":"CR19","first-page":"1134","volume":"27","author":"L.G. Valiant","year":"1984","unstructured":"Valiant, L.G., (1984). A theory of the learnable.Communications of A.C.M., 27 1134?1142.","journal-title":"Communications of A.C.M."},{"key":"CR20","unstructured":"Yamanishi, K., (1991). A learning criterion for stochastic rules.Machine Learning, 9,."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00992677.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00992677\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00992677","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T22:58:34Z","timestamp":1556578714000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00992677"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,7]]},"references-count":20,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[1992,7]]}},"alternative-id":["BF00992677"],"URL":"https:\/\/doi.org\/10.1007\/bf00992677","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,7]]}}}