{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T17:44:47Z","timestamp":1755798287462},"reference-count":62,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2006,8,4]],"date-time":"2006-08-04T00:00:00Z","timestamp":1154649600000},"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":[[2007,1]]},"DOI":"10.1007\/s10994-006-9593-8","type":"journal-article","created":{"date-parts":[[2006,8,7]],"date-time":"2006-08-07T11:57:51Z","timestamp":1154951871000},"page":"7-31","source":"Crossref","is-referenced-by-count":13,"title":["LARS: A learning algorithm for rewriting systems"],"prefix":"10.1007","volume":"66","author":[{"given":"R\u00e9mi","family":"Eyraud","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Colin","family":"de la Higuera","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Christophe","family":"Janodet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,8,4]]},"reference":[{"key":"9593_CR1","doi-asserted-by":"crossref","unstructured":"Adriaans, P., Fernau, H., & van Zaannen, M. (Eds.) (2002). Grammatical inference: Algorithms and applications, In Proceedings of ICGI \u201902, vol. 2484 of LNAI, Berlin, Heidelberg: Springer-Verlag.","DOI":"10.1007\/3-540-45790-9"},{"key":"9593_CR2","unstructured":"Adriaans, P., Vervoort, M. (2002). The EMILE 4.1 grammar induction toolbox. In P., Adriaans, H., Fernau, & van, M. Zaannen (Eds.), Grammatical inference: Algorithms and applications, Proceedings of ICGI \u201902, vol. 2484 of LNAI (pp. 293\u2013295). Berlin, Heidelberg: Springer-Verlag."},{"key":"9593_CR3","unstructured":"Angluin, D. (2001). Queries revisited. In N. Abe, R. Khardon, & T. Zeugmann (Eds.), Proceedings of ALT 2001, number 2225 in LNCS, (pp. 12\u201331), Berlin, Heidelberg: Springer-Verlag."},{"key":"9593_CR4","unstructured":"Boasson, L. (1980). Grammaire \u00e0 non-terminaux s\u00e9par\u00e9s. In Proc. 7th ICALP (pp. 105\u2013118). LNCS 85."},{"key":"9593_CR5","doi-asserted-by":"crossref","unstructured":"Book, R., & Otto, F. (1993). String-rewriting systems. Springer-Verlag.","DOI":"10.1007\/978-1-4613-9771-7"},{"issue":"6","key":"9593_CR6","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/S0020-0190(98)00172-0","volume":"68","author":"J. Calera-Rubio","year":"1998","unstructured":"Calera-Rubio, J., & Carrasco, R. C. (1998). Computing the relative entropy between regular tree languages. Information Processing Letters, 68(6), 283\u2013289.","journal-title":"Information Processing Letters"},{"key":"9593_CR7","doi-asserted-by":"crossref","unstructured":"Carrasco, R. C., & Oncina, J. (Eds.) (1994). Grammatical inference and applications. In Proceedings of ICGI \u201994, number 862 in LNAI, Berlin, Heidelberg: Springer-Verlag.","DOI":"10.1007\/3-540-58473-0"},{"key":"9593_CR8","doi-asserted-by":"crossref","unstructured":"Carrasco, R. C., & Oncina, J. (1994) Learning stochastic regular grammars by means of a state merging method. In R. C., Carrasco, & J. Oncina (Eds.), Grammatical inference and applications. Proceedings of ICGI \u201994, number 862 in LNAI, Berlin, (pp. 139\u2013150), Heidelberg, Springer-Verlag.","DOI":"10.1007\/3-540-58473-0_144"},{"issue":"1","key":"9593_CR9","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1023\/A:1010836331703","volume":"44","author":"R. C. Carrasco","year":"2001","unstructured":"Carrasco, R. C., Oncina, J., & Calera-Rubio, J. (2001). Stochastic inference of regular tree languages. Machine Learning Journal, 44(1), 185\u2013197.","journal-title":"Machine Learning Journal"},{"key":"9593_CR10","unstructured":"Charniak, E. (1996). Tree-bank grammars. In AAAI\/IAAI, (vol. 2, pp. 1031\u20131036)."},{"key":"9593_CR11","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1109\/TIT.1956.1056813","volume":"3","author":"N. Chomsky","year":"1956","unstructured":"Chomsky, N. (1956). Three models for the description of language. IRE Transactions on Information Theory, 3, 113\u2013124.","journal-title":"IRE Transactions on Information Theory"},{"key":"9593_CR12","unstructured":"Clark, A. (2006). Learning deterministic context free grammars: the omphalos competition. Published in this special issue."},{"key":"9593_CR13","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1023\/A:1007353007695","volume":"27","author":"C. de la Higuera","year":"1997","unstructured":"de la Higuera, C. (1997). Characteristic sets for polynomial grammatical inference. Machine Learning Journal, 27, 125\u2013138.","journal-title":"Machine Learning Journal"},{"key":"9593_CR14","unstructured":"de la Higuera, C., Adriaans, P., van Zaanen, M., & Oncina, J. (Eds.), (2003). In Proceedings of the Workshop and Tutorial on Learning Context-free Grammars. ISBN 953-6690-39-X."},{"key":"9593_CR15","unstructured":"de la Higuera, C., & Oncina, J. (2002). Learning deterministic linear languages. In J., Kivinen, & R. H., Sloan, (Eds.), Proceedings of COLT 2002, number 2375 in LNAI, (pp. 185\u2013200). Berlin, Heidelberg. Springer-Verlag."},{"key":"9593_CR16","unstructured":"de la Higuera, C., & Oncina, J. (2006). Learning context-free languages. Artificial Intelligence Reviews. (To appear)."},{"issue":"1","key":"9593_CR17","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1023\/A:1010828029885","volume":"44","author":"A. L. de Oliveira","year":"2001","unstructured":"de Oliveira, A. L., & Silva, J. P. M. (2001). Efficient algorithms for the inference of minimum size DFAs. Machine Learning Journal, 44(1), 93\u2013119.","journal-title":"Machine Learning Journal"},{"key":"9593_CR18","doi-asserted-by":"crossref","unstructured":"Dershowitz, N., & Jouannaud, J. (1990). Rewrite systems. In J. van Leeuwen (Ed.), Handbook of Theoretical Computer Science: Formal Methods and Semantics, (vol. B, chap. 6, pp. 243\u2013320). North Holland, Amsterdam.","DOI":"10.1016\/B978-0-444-88074-1.50011-1"},{"key":"9593_CR19","doi-asserted-by":"crossref","unstructured":"Dupont, P. (1994). Regular grammatical inference from positive & negative samples by genetic search: the GIG method. In R. C., Carrasco, & J. Oncina, (Eds.), Grammatical inference and applications, Proceedings of ICGI \u201994, number 862 in LNAI (pp. 236\u2013245). Berlin, Heidelberg: Springer-Verlag.","DOI":"10.1007\/3-540-58473-0_152"},{"key":"9593_CR20","doi-asserted-by":"crossref","unstructured":"Emerald, J. D., Subramanian, K. G., & Thomas, D. G. (1998). Learning a subclass of context-free languages. In V., Honavar, & G. Slutski, (Eds.), Grammatical inference, Proceedings of ICGI \u201998, number 1433 in LNAI, (pp. 223\u2013231). Berlin, Heidelberg: Springer-Verlag.","DOI":"10.1007\/BFb0054078"},{"key":"9593_CR21","doi-asserted-by":"crossref","unstructured":"Fernau, H. (2002). Learning tree languages from text. In J., Kivinen, & R. H. Sloan, (Eds.), Proceedings of COLT 2002, number 2375 in LNAI, (pp. 153\u2013168). Berlin, Heidelberg. Springer-Verlag.","DOI":"10.1007\/3-540-45435-7_11"},{"issue":"2","key":"9593_CR22","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0020-0190(94)00074-3","volume":"51","author":"M. Frazier","year":"1994","unstructured":"Frazier, M., & Page, C.D. Jr, (1994). Prefix grammars: An alternative characterisation of the regular languages. Information Processing Letters, 51(2), 67\u201371.","journal-title":"Information Processing Letters"},{"key":"9593_CR23","unstructured":"Garc\u00eda, P., & Oncina, J. (1993). Inference of recognizable tree sets. Technical Report DSIC-II\/47\/93, Departamento de Lenguajes y Sistemas Inform\u00e1ticos, Universidad Polit\u00e9cnica de Valencia, Spain."},{"key":"9593_CR24","doi-asserted-by":"crossref","unstructured":"Giordano, J. Y. (1994). Inference of context-free grammars by enumeration: Structural containment as an ordering bias. In R. C., Carrasco, & J. Oncina, (Eds.), Grammatical inference and applications, Proceedings of ICGI \u201994, number 862 in LNAI, (pp. 212\u2013221). Berlin, Heidelberg, Springer-Verlag.","DOI":"10.1007\/3-540-58473-0_150"},{"key":"9593_CR25","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\u2013320.","journal-title":"Information and Control"},{"issue":"1","key":"9593_CR26","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1006\/jcss.1995.1003","volume":"50","author":"S. A. Goldman","year":"1995","unstructured":"Goldman, S. A., & Kearns, M. (1995). On the complexity of teaching. Journal of Computer and System Sciences, 50(1), 20\u201331.","journal-title":"Journal of Computer and System Sciences"},{"key":"9593_CR27","unstructured":"Habrard, A., Bernard, M., & Jacquenet, F. (2002). Generalized stochastic tree automata for multi-relational data mining. In P., Adriaans, H., Fernau, & M. van Zaannen. (Eds.), Grammatical inference: Algorithms and applications, Proceedings of ICGI \u201902, vol. 2484 of LNAI, (pp. 120\u2013133). Berlin, Heidelberg. Springer-Verlag."},{"key":"9593_CR28","doi-asserted-by":"crossref","unstructured":"Honavar, V., & Slutski, G. (Eds.) (1998). Grammatical inference, Proceedings of ICGI \u201998, number 1433 in LNAI, Berlin, Heidelberg. Springer-Verlag.","DOI":"10.1007\/BFb0054058"},{"key":"9593_CR29","first-page":"151","volume":"5","author":"H. Ishizaka","year":"1995","unstructured":"Ishizaka, H. (1995). Polynomial time learnability of simple deterministic languages. Machine Learning Journal, 5, 151\u2013164.","journal-title":"Machine Learning Journal"},{"key":"9593_CR30","unstructured":"Kivinen, J., & Sloan, R. H. (Eds.), (2002). In Proceedings of COLT 2002, number 2375 in LNAI, Berlin, Heidelberg: Springer-Verlag."},{"key":"9593_CR31","doi-asserted-by":"crossref","unstructured":"Klop, J. W. (1992). Term rewriting systems. In S. Abramsky, D. Gabbay, & T. Maibaum, (Eds.), Handbook of Logic in Computer Science, (vol. 2, pp. 1\u2013112). Oxford University Press.","DOI":"10.1093\/oso\/9780198537618.003.0001"},{"key":"9593_CR32","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0304-3975(94)90033-7","volume":"129","author":"T. Knuutila","year":"1994","unstructured":"Knuutila, T., & Steinby, M. (1994). Inference of tree languages from a finite sample: an algebraic approach. Theoretical Computer Science, 129, 337\u2013367.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"9593_CR33","first-page":"469","volume":"14","author":"T. Koshiba","year":"2000","unstructured":"Koshiba, T., M\u00e4kinen, E., & Takada, Y. (2000). Inferring pure context-free languages from positive data. Acta Cybernetica, 14(3), 469\u2013477.","journal-title":"Acta Cybernetica"},{"key":"9593_CR34","doi-asserted-by":"crossref","unstructured":"Kremer, S. C. (1997). Parallel stochastic grammar induction. In Proceedings of the 1997 International Conference on Neural Networks (ICNN \u201997), (vol. I, pp. 612\u2013616).","DOI":"10.1109\/ICNN.1997.611740"},{"key":"9593_CR35","unstructured":"Laird, P., & Gamble, E. (1990). Ebg and term rewriting systems. In Algorithmic Learning Theory (pp. 425\u2013440)."},{"key":"9593_CR36","unstructured":"Lang, K., Pearlmutter, B. A., & Coste, F. (1998). The Gowachin automata learning competition."},{"key":"9593_CR37","unstructured":"Lang, K., Pearlmutter, B. A., & Price, R. A. (1998). The Abbadingo one DFA learning competition. In Proceedings of ICGI\u201998, (pp. 1\u201312). The abbadingo competition can be found at the address: http:\/\/abbadingo.cs.unm.edu\/"},{"key":"9593_CR38","doi-asserted-by":"crossref","unstructured":"Lang, K. J., Pearlmutter, B. A., & Price, R. A. (1998). Results of the Abbadingo one DFA learning competition and a new evidence-driven state merging algorithm. In V., Honavar, & G. Slutski, (Eds.), Grammatical Inference, Proceedings of ICGI \u201998, number 1433 in LNAI, (pp. 1\u201312). Berlin, Heidelberg: Springer-Verlag.","DOI":"10.1007\/BFb0054059"},{"key":"9593_CR39","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0885-2308(90)90022-X","volume":"4","author":"K. Lari","year":"1990","unstructured":"Lari, K., & Young, S. J. (1990). The estimation of stochastic context free grammars using the inside-outside algorithm. Computer Speech and Language, 4, 35\u201356.","journal-title":"Computer Speech and Language"},{"key":"9593_CR40","unstructured":"Lee, L. (1996). Learning of context-free languages: A survey of the literature. Technical Report TR-12-96, Center for Research in Computing Technology, Harvard University, Cambridge, Massachusetts."},{"issue":"2","key":"9593_CR41","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1145\/42282.42284","volume":"35","author":"R. McNaughton","year":"1988","unstructured":"McNaughton, R., Narendran, P., & Otto, F. (1988). Church-Rosser Thue systems and formal languages. Journal of the Association for Computing Machinery, 35(2), 324\u2013344.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"9593_CR42","doi-asserted-by":"crossref","unstructured":"Moczydlowski, W., & Geser, A. (2005). Termination of single-threaded one-rule semi-thue systems. In Proceedings of the 16th International Conference on Rewriting Techniques and Applications, (pp. 338\u2013352). LNCS 3467.","DOI":"10.1007\/978-3-540-32033-3_25"},{"issue":"9","key":"9593_CR43","doi-asserted-by":"crossref","first-page":"1384","DOI":"10.1016\/j.patcog.2005.01.004","volume":"38","author":"K. Nakamura","year":"2005","unstructured":"Nakamura, K., & Matsumoto, M. (2005). Incremental learning of context-free grammars based on bottom-up parsing and search. Pattern Recognition, 38(9), 1384\u20131392.","journal-title":"Pattern Recognition"},{"key":"9593_CR44","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1613\/jair.374","volume":"7","author":"C. Nevill-Manning","year":"1997","unstructured":"Nevill-Manning, C., & Witten, I. (1997). Identifying hierarchical structure in sequences: a linear-time algorithm. Journal of Artificial Intelligence Research, 7, 67\u201382.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9593_CR45","doi-asserted-by":"crossref","unstructured":"Nivat, M. (1970). On some families of languages related to the dyck language. In Proc. 2nd Annual Symposium on Theory of Computing.","DOI":"10.1145\/800161.805168"},{"key":"9593_CR46","doi-asserted-by":"crossref","unstructured":"O\u2019Donnell, M. J. (1977). Computing in Systems Described by Equations, vol. 58 of LNCS. Springer.","DOI":"10.1007\/3-540-08531-9"},{"key":"9593_CR47","unstructured":"Oncina, J., & Garc\u00eda, P. (1992). Identifying regular languages in polynomial time. In H. Bunke, (Ed.), Advances in Structural and Syntactic Pattern Recognition, vol. 5 of Series in Machine Perception and Artificial Intelligence, (pp. 99\u2013108). World Scientific."},{"key":"9593_CR48","first-page":"69","volume":"7","author":"G. Petasis","year":"2004","unstructured":"Petasis, G., Paliouras, G., Karkaletsis, V., Halatsis, C., & Spyropoulos, C. (2004). E-grids: Computationally efficient grammatical inference from positive examples. Grammars, 7, 69\u2013110.","journal-title":"Grammars"},{"key":"9593_CR49","doi-asserted-by":"crossref","unstructured":"Rao, M. R. K. Krishna. (2004). Inductive inference of term rewriting systems from positive data. In Agorithmic Learning Theory, (pp. 69\u201382).","DOI":"10.1007\/978-3-540-30215-5_7"},{"key":"9593_CR50","doi-asserted-by":"crossref","unstructured":"Rico-Juan, J. R., Calera-Rubio, J., & Carrasco, R. C. Stochastic k-testable tree languages and applications. In Adriaans, P., Fernau, H., & van Zaannen, M. (Eds.), (2002). Grammatical inference: Algorithms and applications, In Proceedings of ICGI \u201902, vol. 2484 of LNAI, (pp. 199\u2013212). Berlin, Heidelberg: Springer-Verlag.","DOI":"10.1007\/3-540-45790-9_16"},{"key":"9593_CR51","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0304-3975(90)90017-C","volume":"76","author":"Y. Sakakibara","year":"1990","unstructured":"Sakakibara, Y. (1990). Learning context-free grammars from structural data in polynomial time. Theoretical Computer Science, 76, 223\u2013242.","journal-title":"Theoretical Computer Science"},{"key":"9593_CR52","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0890-5401(92)90003-X","volume":"97","author":"Y. Sakakibara","year":"1992","unstructured":"Sakakibara, Y. (1992). Efficient learning of context-free grammars from positive structural examples. Information and Computation, 97, 23\u201360.","journal-title":"Information and Computation"},{"key":"9593_CR53","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/S0304-3975(97)00014-5","volume":"185","author":"Y. Sakakibara","year":"1997","unstructured":"Sakakibara, Y. (1997). Recent advances of grammatical inference. Theoretical Computer Science, 185, 15\u201345.","journal-title":"Theoretical Computer Science"},{"key":"9593_CR54","unstructured":"Sakakibara, Y., & Kondo, M. (1999). Ga-based learning of context-free grammars using tabular representations. In Proceedings of 16th International Conference on Machine Learning (ICML-99) (pp. 354\u2013360)."},{"issue":"1","key":"9593_CR55","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0304-3975(97)00145-X","volume":"192","author":"G. S\u00e9nizergues","year":"1998","unstructured":"S\u00e9nizergues, G. (1998). A polynomial algorithm testing partial confluence of basic semi-thue systems. Theor. Comput. Sci., 192(1), 55\u201375.","journal-title":"Theor. Comput. Sci."},{"key":"9593_CR56","unstructured":"Starkie, B., Coste, F., & van Zaanen, M. (2004). Omphalos context-free language learning competition. The Omphalos competition is at the address: http:\/\/www.irisa.fr\/Omphalos\/"},{"issue":"4","key":"9593_CR57","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0020-0190(88)90208-6","volume":"28","author":"Y. Takada","year":"1988","unstructured":"Takada, Y. (1988). Grammatical inference for even linear languages based on control sets. Information Processing Letters, 28(4), 193\u2013199.","journal-title":"Information Processing Letters"},{"key":"9593_CR58","unstructured":"Thollard, F., Dupont, P., & de la Higuera, C. (2000). Probabilistic DFA inference using Kullback-Leibler divergence and minimality. In Proc. 17th International Conf. on Machine Learning, (pp. 975\u2013982). San Francisco, CA: Morgan Kaufmann."},{"key":"9593_CR59","unstructured":"Togashi, A., & Noguchi, S. (1990). Inductive inference of term rewriting systems realizing algebras. In Algorithm Learning Theory, (pp. 411\u2013424)."},{"key":"9593_CR60","first-page":"39","volume":"2","author":"K. Vanlehn","year":"1987","unstructured":"Vanlehn, K., & Ball, W. (1987). A version space approach to learning context-free grammars. Machine Learning Journal, 2, 39\u201374.","journal-title":"Machine Learning Journal"},{"key":"9593_CR61","unstructured":"Wolf, G. (1978). Grammar discovery as data compression. In Proceedings of AISB\/GI Conference on Artificial Intelligence, (pp. 375\u2013379), Hamburg."},{"issue":"298","key":"9593_CR62","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/S0304-3975(02)00423-1","volume":"1","author":"T. Yokomori","year":"2003","unstructured":"Yokomori, T. (2003). Polynomial-time identification of very simple grammars from positive data. Theor. Comput. Sci., 1(298), 179\u2013206.","journal-title":"Theor. Comput. Sci."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-006-9593-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10994-006-9593-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-006-9593-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,5]],"date-time":"2024-02-05T21:46:01Z","timestamp":1707169561000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10994-006-9593-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,8,4]]},"references-count":62,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["9593"],"URL":"https:\/\/doi.org\/10.1007\/s10994-006-9593-8","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,8,4]]}}}