{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T18:38:47Z","timestamp":1776191927146,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540410119","type":"print"},{"value":"9783540452577","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/978-3-540-45257-7_2","type":"book-chapter","created":{"date-parts":[[2010,7,1]],"date-time":"2010-07-01T22:05:01Z","timestamp":1278021901000},"page":"15-24","source":"Crossref","is-referenced-by-count":23,"title":["Computational Complexity of Problems on Probabilistic Grammars and Transducers"],"prefix":"10.1007","author":[{"given":"Francisco","family":"Casacuberta","sequence":"first","affiliation":[]},{"given":"Colin","family":"de la Higuera","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"2_CR1","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1145\/322326.322334","volume":"29","author":"D. Angluin","year":"1982","unstructured":"Angluin, D.: Inference of reversible languages. Journal of the ACM\u00a029(3), 741\u2013765 (1982)","journal-title":"Journal of the ACM"},{"key":"2_CR2","series-title":"LNAI","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/3-540-58473-0_144","volume-title":"Grammatical Inference and Applications","author":"R. Carrasco","year":"1994","unstructured":"Carrasco, R., Oncina, J.: Learning stochastic regular grammars by means of a state merging method. In: Carrasco, R.C., Oncina, J. (eds.) ICGI 1994. LNCS (LNAI), vol.\u00a0862, pp. 139\u2013150. Springer, Heidelberg (1994)"},{"issue":"1","key":"2_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1051\/ita:1999102","volume":"33","author":"J.O. Carrasco","year":"1999","unstructured":"Carrasco, J.O.: Learning deterministic regular grammars from stochastic samples in polynomial time. Informatique Th\u00e9orique et Applications\u00a033(1), 1\u201319 (1999)","journal-title":"Informatique Th\u00e9orique et Applications"},{"key":"2_CR4","series-title":"LNAI","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/BFb0033362","volume-title":"Grammatical Inference: Learning Syntax from Sentences","author":"F. Casacuberta","year":"1996","unstructured":"Casacuberta, F.: Maximum mutual information and conditional maximum likelihood estimations of stochastic syntax-directed translation schemes. In: Miclet, L., de la Higuera, C. (eds.) ICGI 1996. LNCS (LNAI), vol.\u00a01147, pp. 282\u2013291. Springer, Heidelberg (1996)"},{"key":"2_CR5","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1142\/S0218001496000153","volume":"10","author":"F. Casacuberta","year":"1996","unstructured":"Casacuberta, F.: Growth transformations for probabilistic functions of stochastic grammars. International Journal on Pattern Recognition and Artificial Intelligence\u00a010, 183\u2013201 (1996)","journal-title":"International Journal on Pattern Recognition and Artificial Intelligence"},{"key":"2_CR6","volume-title":"Introduction to algorithms","author":"T. Cormen","year":"1990","unstructured":"Cormen, T., Leiserson, C., Rivest, R.: Introduction to algorithms. The MIT Press, Cambridge (1990)"},{"key":"2_CR7","unstructured":"Crescenzi, P., Kann, V.: A compendium of NP optimization problems (1995), http:\/\/www.nada.kth.se\/~viggo\/problemlist\/compendium.html"},{"key":"2_CR8","first-page":"59","volume":"5","author":"K.S. Fu","year":"1985","unstructured":"Fu, K.S., Booth, T.L.: Grammatical inference: introduction and survey. Part I and II, IEEE Transactions on System Man and Cybernetics\u00a05, 59\u201372, 409\u2013423 (1985)","journal-title":"IEEE Transactions on System Man and Cybernetics"},{"key":"2_CR9","volume-title":"Syntactic pattern recognition and applications","author":"K.S. Fu","year":"1982","unstructured":"Fu, K.S.: Syntactic pattern recognition and applications. Prentice-Hall, Englewood Cliffs (1982)"},{"issue":"9","key":"2_CR10","doi-asserted-by":"publisher","first-page":"920","DOI":"10.1109\/34.57687","volume":"12","author":"P. Garc\u00eda","year":"1990","unstructured":"Garc\u00eda, P., Vidal, E.: Inference of K-testable languages in the strict sense and applications to syntactic pattern recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence\u00a012(9), 920\u2013925 (1990)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"2_CR11","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman, San Francisco (1979)"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Goemans, M.X., Williamson, D.O.: 878-approximation algorithms for MAXCUT and MAX-2SAT. In: Proc. Twenty sixth Ann. ACM Symposium on Th. of Comp., pp. 422\u2013431 (1994)","DOI":"10.1145\/195058.195216"},{"key":"2_CR13","volume-title":"Syntactic pattern recognition: an introduction","author":"R. Gonz\u00e1lez","year":"1978","unstructured":"Gonz\u00e1lez, R., Thomason, M.: Syntactic pattern recognition: an introduction. Addison-Wesley, Reading (1978)"},{"key":"2_CR14","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0885-2308(91)90009-F","volume":"5","author":"K. Lari","year":"1991","unstructured":"Lari, K., Young, S.: Applications of stocashtic context-free grammars. Computer Speech and Language\u00a05, 237\u2013257 (1991)","journal-title":"Computer Speech and Language"},{"key":"2_CR15","series-title":"LNAI","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1007\/3-540-58473-0_146","volume-title":"Grammatical Inference and Applications","author":"S. Lucas","year":"1994","unstructured":"Lucas, S., Vidal, E., Amiri, A., Hanlon, S., Amengual, J.-C.: A comparison of syntactic and statistical techniques for off-line OCR. In: Carrasco, R.C., Oncina, J. (eds.) ICGI 1994. LNCS (LNAI), vol.\u00a0862, pp. 168\u2013179. Springer, Heidelberg (1994)"},{"key":"2_CR16","first-page":"45","volume-title":"Speech Recognition and Understanding","author":"H. Ney","year":"1995","unstructured":"Ney, H.: Stochastic grammars and Pattern Recognition. In: Laface, P., de Mori, R. (eds.) Speech Recognition and Understanding, pp. 45\u2013360. Springer, Heidelberg (1995)"},{"key":"2_CR17","first-page":"1","volume":"27","author":"C. Higuera de la","year":"1997","unstructured":"de la Higuera, C.: Characteristic sets for grammatical inference. Machine Learning\u00a027, 1\u201314 (1997)","journal-title":"Machine Learning"},{"key":"2_CR18","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1109\/34.211465","volume":"15","author":"J. Oncina","year":"1993","unstructured":"Oncina, J., Garc\u00eda, P., Vidal, E.: Learning subsequential transducers for pattern recognition tasks. IEEE Transactions on Pattern Analysis and Machine Intelligence\u00a015, 448\u2013458 (1993)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"2_CR19","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimisation approximation and complexity classes. Journal Computing System Science\u00a043, 425\u2013440 (1991)","journal-title":"Journal Computing System Science"},{"key":"2_CR20","volume-title":"Fundamentals of Speech Recognition","author":"L. Rabiner","year":"1993","unstructured":"Rabiner, L., Juang, B.H.: Fundamentals of Speech Recognition. Prentice-Hall, Englewood Cliffs (1993)"},{"key":"2_CR21","doi-asserted-by":"crossref","unstructured":"Ron, D., Singer, Y., Tishby, N.: On the Learnability and Usage of Acyclic Probabilistic Finite Automata. In: Ron, D., Singer, Y., Tishby, N. (eds.) Proceedings of COLT 1995, pp. 31\u201340 (1995)","DOI":"10.1145\/225298.225302"},{"key":"2_CR22","doi-asserted-by":"crossref","unstructured":"Rulot, H., Vidal, E.: Modelling (sub)string-length-based constraints through grammatical inference methods. In: Devijver, Kittler (eds.), Springer, Heidelberg (1987)","DOI":"10.1007\/978-3-642-83069-3_35"},{"key":"2_CR23","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/S0304-3975(97)00014-5","volume":"185","author":"Y. Sakakibara","year":"1997","unstructured":"Sakakibara, Y.: Recent Advances of Grammatical Inference. Theoretical Computer Science\u00a0185, 15\u201345 (1997)","journal-title":"Theoretical Computer Science"},{"key":"2_CR24","series-title":"LNAI","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1007\/3-540-58473-0_141","volume-title":"Grammatical Inference and Applications","author":"A. Stolcke","year":"1994","unstructured":"Stolcke, A., Omohundro, S.: Inducing Probabilistic Grammars by Bayesian Model Merging. In: Carrasco, R.C., Oncina, J. (eds.) ICGI 1994. LNCS (LNAI), vol.\u00a0862, pp. 106\u2013118. Springer, Heidelberg (1994)"},{"key":"2_CR25","unstructured":"Thollard, F., Dupont, P., de la Higuera, C.: Probabilistic DFA Inference using Kullback-Leibler Divergence and Minimality. In: ICML 2000, International Colloquium on Machine Learning, Stanford (2000)"},{"key":"2_CR26","series-title":"NATO-ASI Series","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1007\/978-3-642-57745-1_27","volume-title":"New Advances and Trends in Speech Recognition and Coding","author":"E. Vidal","year":"1995","unstructured":"Vidal, E., Casacuberta, F., Garc\u00eda, P.: Syntactic Learning Techniques for Language Modeling and Acoustic-Phonetic Decoding. In: Rubio, A. (ed.) New Advances and Trends in Speech Recognition and Coding. NATO-ASI Series, ch.\u00a027, pp. 174\u2013191. Springer, Heidelberg (1995)"},{"key":"2_CR27","unstructured":"Young-Lai, M., Tompa, F.W.: Stochastic Grammatical Inference of Text Database Structure. To appear in Machine Learning (2000)"}],"container-title":["Lecture Notes in Computer Science","Grammatical Inference: Algorithms and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45257-7_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T17:13:20Z","timestamp":1559236400000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45257-7_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540410119","9783540452577"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45257-7_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000]]}}}