{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:33:02Z","timestamp":1759638782044,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540880080"},{"type":"electronic","value":"9783540880097"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-88009-7_13","type":"book-chapter","created":{"date-parts":[[2008,9,20]],"date-time":"2008-09-20T03:52:54Z","timestamp":1221882774000},"page":"163-174","source":"Crossref","is-referenced-by-count":10,"title":["Towards Feasible PAC-Learning of Probabilistic Deterministic Finite Automata"],"prefix":"10.1007","author":[{"given":"Jorge","family":"Castro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ricard","family":"Gavald\u00e0","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"Carrasco, R.C., Oncina, J.: Learning stochastic regular grammars by means of a state merging method. In: ICGI, pp. 139\u2013152 (1994)","DOI":"10.1007\/3-540-58473-0_144"},{"issue":"1","key":"13_CR2","first-page":"1","volume":"33","author":"R.C. Carrasco","year":"1999","unstructured":"Carrasco, R.C., Oncina, J.: Learning deterministic regular grammars from stochastic samples in polynomial time. ITA\u00a033(1), 1\u201320 (1999)","journal-title":"ITA"},{"key":"13_CR3","first-page":"473","volume":"5","author":"A. Clark","year":"2004","unstructured":"Clark, A., Thollard, F.: PAC-learnability of probabilistic deterministic finite state automata. Journal of Machine Learning Research\u00a05, 473\u2013497 (2004)","journal-title":"Journal of Machine Learning Research"},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"de la Higuera, C., Oncina, J., Vidal, E.: Identification of DFA: data-dependent vs data-independent algorithms. In: ICGI, pp. 313\u2013325 (1996)","DOI":"10.1007\/BFb0033365"},{"key":"13_CR5","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)"},{"key":"13_CR6","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, 1349\u20131371 (2005)","journal-title":"Pattern Recognition"},{"key":"13_CR7","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":"13_CR8","unstructured":"Guttman, O.: Probabilistic Automata Distributions over Sequences. Ph.D. thesis, The Australian National University (September 2006)"},{"key":"13_CR9","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":"13_CR10","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"},{"key":"13_CR11","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/3-540-45790-9_12","volume-title":"Grammatical Inference: Algorithms and Applications","author":"C. Kermorvant","year":"2002","unstructured":"Kermorvant, C., Dupont, P.: Stochastic grammatical inference with multinomial tests. In: Adriaans, P.W., Fernau, H., van Zaanen, M. (eds.) ICGI 2002. LNCS (LNAI), vol.\u00a02484, pp. 149\u2013160. Springer, Heidelberg (2002)"},{"key":"13_CR12","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/11564089_14","volume-title":"Algorithmic Learning Theory","author":"N. Palmer","year":"2005","unstructured":"Palmer, N., Goldberg, P.W.: PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance. In: Jain, S., Simon, H.U., Tomita, E. (eds.) ALT 2005. LNCS (LNAI), vol.\u00a03734, pp. 157\u2013170. Springer, Heidelberg (2005)"},{"issue":"2","key":"13_CR13","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."},{"key":"13_CR14","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1007\/978-3-540-30195-0_22","volume-title":"Grammatical Inference: Algorithms and Applications","author":"F. Thollard","year":"2004","unstructured":"Thollard, F., Clark, A.: Learning stochastic deterministic regular languages. In: Paliouras, G., Sakakibara, Y. (eds.) ICGI 2004. LNCS (LNAI), vol.\u00a03264, pp. 248\u2013259. Springer, Heidelberg (2004)"},{"key":"13_CR15","unstructured":"Thollard, F., Dupont, P., de la Higuera, C.: Probabilistic DFA inference using Kullback-Leibler divergence and minimality. In: ICML, pp. 975\u2013982 (2000)"}],"container-title":["Lecture Notes in Computer Science","Grammatical Inference: Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-88009-7_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T03:47:31Z","timestamp":1715312851000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-88009-7_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540880080","9783540880097"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-88009-7_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}