{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:19:24Z","timestamp":1725563964519},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642161070"},{"type":"electronic","value":"9783642161087"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/linproxy.fan.workers.dev:443\/http\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-16108-7_17","type":"book-chapter","created":{"date-parts":[[2010,8,31]],"date-time":"2010-08-31T08:58:37Z","timestamp":1283245117000},"page":"179-193","source":"Crossref","is-referenced-by-count":2,"title":["A Lower Bound for Learning Distributions Generated by Probabilistic Automata"],"prefix":"10.1007","author":[{"given":"Borja","family":"Balle","sequence":"first","affiliation":[]},{"given":"Jorge","family":"Castro","sequence":"additional","affiliation":[]},{"given":"Ricard","family":"Gavald\u00e0","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2-3","key":"17_CR1","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/BF00992677","volume":"9","author":"N. Abe","year":"1992","unstructured":"Abe, N., Warmuth, M.K.: On the computational complexity of approximating distributions by probabilistic automata. Mach. Learn.\u00a09(2-3), 205\u2013260 (1992)","journal-title":"Mach. Learn."},{"issue":"1","key":"17_CR2","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1006\/jcss.1997.1507","volume":"55","author":"S. Ben-David","year":"1997","unstructured":"Ben-David, S., Lindenbaum, M.: Learning distributions by their density levels: A paradigm for learning without a teacher. J. Comput. Syst. Sci.\u00a055(1), 171\u2013182 (1997)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"17_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1051\/ita:1999102","volume":"33","author":"R.C. Carrasco","year":"1999","unstructured":"Carrasco, R.C., Oncina, J.: Learning deterministic regular grammars from stochastic samples in polynomial time. RAIRO (Theoretical Informatics and Applications)\u00a033(1), 1\u201320 (1999)","journal-title":"RAIRO (Theoretical Informatics and Applications)"},{"key":"17_CR4","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-540-88009-7_13","volume-title":"Grammatical Inference: Algorithms and Applications","author":"J. Castro","year":"2008","unstructured":"Castro, J., Gavald\u00e0, R.: Towards feasible PAC-learning of probabilistic deterministic finite automata. In: Clark, A., Coste, F., Miclet, L. (eds.) ICGI 2008. LNCS (LNAI), vol.\u00a05278, pp. 163\u2013174. Springer, Heidelberg (2008)"},{"key":"17_CR5","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546921","volume-title":"Prediction, Learning, and Games","author":"N. Cesa-Bianchi","year":"2006","unstructured":"Cesa-Bianchi, N., Lugosi, G.: Prediction, Learning, and Games. Cambridge University Press, New York (2006)"},{"key":"17_CR6","unstructured":"Clark, A., Thollard, F.: PAC-learnability of probabilistic deterministic finite state automata. Journal of Machine Learning Research (2004)"},{"key":"17_CR7","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1007\/11776420_22","volume-title":"Learning Theory","author":"F. Denis","year":"2006","unstructured":"Denis, F., Esposito, Y., Habrard, A.: Learning rational stochastic languages. In: Lugosi, G., Simon, H.U. (eds.) COLT 2006. LNCS (LNAI), vol.\u00a04005, pp. 274\u2013288. Springer, Heidelberg (2006)"},{"issue":"9","key":"17_CR8","doi-asserted-by":"publisher","first-page":"1349","DOI":"10.1016\/j.patcog.2004.03.020","volume":"38","author":"P. Dupont","year":"2005","unstructured":"Dupont, P., Denis, F., Esposito, Y.: Links between probabilistic automata and hidden markov models: probability distributions, learning models and induction algorithms. Pattern Recognition\u00a038(9), 1349\u20131371 (2005)","journal-title":"Pattern Recognition"},{"key":"17_CR9","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/11871842_18","volume-title":"Machine Learning: ECML 2006","author":"R. Gavald\u00e0","year":"2006","unstructured":"Gavald\u00e0, R., Keller, P.W., Pineau, J., Precup, D.: PAC-learning of markov models with hidden state. In: F\u00fcrnkranz, J., Scheffer, T., Spiliopoulou, M. (eds.) ECML 2006. LNCS (LNAI), vol.\u00a04212, pp. 150\u2013161. Springer, Heidelberg (2006)"},{"key":"17_CR10","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/11564089_15","volume-title":"Algorithmic Learning Theory","author":"O. Guttman","year":"2005","unstructured":"Guttman, O., Vishwanathan, S.V.N., Williamson, R.C.: Learnability of probabilistic automata via oracles. In: Jain, S., Simon, H.U., Tomita, E. (eds.) ALT 2005. LNCS (LNAI), vol.\u00a03734, pp. 171\u2013182. Springer, Heidelberg (2005)"},{"key":"17_CR11","unstructured":"Hsu, D., Kakade, S.M., Zhang, T.: A spectral algorithm for learning hidden markov models. CoRR abs\/0811.4413 (2008)"},{"issue":"6","key":"17_CR12","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1145\/293347.293351","volume":"45","author":"M. Kearns","year":"1998","unstructured":"Kearns, M.: Efficient noise-tolerant learning from statistical queries. J. ACM\u00a045(6), 983\u20131006 (1998)","journal-title":"J. ACM"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"Kearns, M.J., Mansour, Y., Ron, D., Rubinfeld, R., Schapire, R.E., Sellie, L.: On the learnability of discrete distributions. In: STOC, pp. 273\u2013282 (1994)","DOI":"10.1145\/195058.195155"},{"issue":"3","key":"17_CR14","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1016\/S0022-0000(02)00009-0","volume":"65","author":"R.B. Lyngs\u00f8","year":"2002","unstructured":"Lyngs\u00f8, R.B., Pedersen, C.N.S.: The consensus string problem and the complexity of comparing hidden markov models. J. Comput. Syst. Sci.\u00a065(3), 545\u2013569 (2002)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"17_CR15","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/j.tcs.2007.07.023","volume":"387","author":"N. Palmer","year":"2007","unstructured":"Palmer, N., Goldberg, P.W.: PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance. Theor. Comput. Sci.\u00a0387(1), 18\u201331 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"17_CR16","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1006\/jcss.1997.1555","volume":"56","author":"D. Ron","year":"1998","unstructured":"Ron, D., Singer, Y., Tishby, N.: On the learnability and usage of acyclic probabilistic finite automata. J. Comput. Syst. Sci.\u00a056(2), 133\u2013152 (1998)","journal-title":"J. Comput. Syst. Sci."},{"issue":"7","key":"17_CR17","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1109\/TPAMI.2005.147","volume":"27","author":"E. Vidal","year":"2005","unstructured":"Vidal, E., Thollard, F., de la Higuera, C., Casacuberta, F., Carrasco, R.C.: Probabilistic finite-state machines - part I. IEEE Trans. Pattern Anal. Mach. Intell.\u00a027(7), 1013\u20131025 (2005)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"7","key":"17_CR18","doi-asserted-by":"publisher","first-page":"1026","DOI":"10.1109\/TPAMI.2005.148","volume":"27","author":"E. Vidal","year":"2005","unstructured":"Vidal, E., Thollard, F., de la Higuera, C., Casacuberta, F., Carrasco, R.C.: Probabilistic finite-state machines - part II. IEEE Trans. Pattern Anal. Mach. Intell.\u00a027(7), 1026\u20131039 (2005)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/linproxy.fan.workers.dev:443\/http\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16108-7_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T17:23:57Z","timestamp":1558286637000},"score":1,"resource":{"primary":{"URL":"https:\/\/linproxy.fan.workers.dev:443\/http\/link.springer.com\/10.1007\/978-3-642-16108-7_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642161070","9783642161087"],"references-count":18,"URL":"https:\/\/linproxy.fan.workers.dev:443\/https\/doi.org\/10.1007\/978-3-642-16108-7_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}