{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T15:54:42Z","timestamp":1770479682317,"version":"3.49.0"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,1,6]],"date-time":"2011-01-06T00:00:00Z","timestamp":1294272000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Artif Intell Rev"],"published-print":{"date-parts":[[2011,6]]},"DOI":"10.1007\/s10462-010-9199-1","type":"journal-article","created":{"date-parts":[[2011,1,5]],"date-time":"2011-01-05T07:04:12Z","timestamp":1294211052000},"page":"1-27","source":"Crossref","is-referenced-by-count":40,"title":["A survey of grammatical inference methods for natural language learning"],"prefix":"10.1007","volume":"36","author":[{"given":"Arianna","family":"D\u2019Ulizia","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fernando","family":"Ferri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patrizia","family":"Grifoni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,1,6]]},"reference":[{"key":"9199_CR1","unstructured":"Adriaans PW (2001) Learning shallow context-free languages under simple distributions. In: Opestake A, Vermeulen K (eds) Algebras, diagrams and decisions in language, logic and computation, CSLI\/CUP"},{"key":"9199_CR2","unstructured":"Adriaans PW (1992) Language learning from a categorial perspective. PhD thesis, University of Amsterdam, Amsterdam"},{"key":"9199_CR3","unstructured":"Adriaans PW, Vervoort M (2002) The EMILE 4.1 grammar induction toolbox. In: Adriaans P, Fernau H, van Zaanen M (eds) Grammatical inference: algorithms and applications: 6th international colloquium: ICGI 2002. Lecture notes in computer science, vol 2484. Springer, Heidelberg, pp 293\u2013295"},{"key":"9199_CR4","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1145\/322326.322334","volume":"29","author":"D Angluin","year":"1982","unstructured":"Angluin D (1982) Inference of reversible languages. J ACM 29: 741\u2013765","journal-title":"J ACM"},{"key":"9199_CR5","doi-asserted-by":"crossref","unstructured":"Baker JK (1979) Trainable grammars for speech recognition. In: Klatt DH, Wolf JJ (eds) Speech communication papers for the 97th meeting of the acoustical society of America, pp 547\u2013550","DOI":"10.1121\/1.2017061"},{"key":"9199_CR6","doi-asserted-by":"crossref","unstructured":"Black E, Abney S, Flickinger D, Gdaniec C, Grishman R, Harrison P, Hindle D, Ingria R, Jelinek F, Klavans J, Liberman M, Marcus M, Roukos S, Santorini B, Strzalkowski T (1991) A procedure for quantitatively comparing the syntactic coverage of English grammars. In: Proceedings of the DARPA speech and natural language workshop, pp 306\u2013311","DOI":"10.3115\/112405.112467"},{"key":"9199_CR7","doi-asserted-by":"crossref","unstructured":"Blum A, Mitchell T (1998) Combining labeled and unlabeled data with cotraining. In: Proceedings of the workshop on computational learning theory","DOI":"10.1145\/279943.279962"},{"key":"9199_CR8","unstructured":"Bonnema R, Bod R, Scha R (1997) A DOP model for semantic interpretation. In: ACL 1997, pp 159\u2013167"},{"key":"9199_CR9","doi-asserted-by":"crossref","unstructured":"Briscoe T (2000) Grammatical acquisition: inductive bias and coevolution of language and the language acquisition device. Language, pp 245\u2013296","DOI":"10.1353\/lan.2000.0015"},{"key":"9199_CR10","doi-asserted-by":"crossref","unstructured":"Charniak E, Johnson M (2005) Coarse-to-fine n-best parsing and MaxEnt discriminative reranking. In: Proceedings of the 43rd annual meeting of the ACL, Ann Arbor, pp 173\u2013180","DOI":"10.3115\/1219840.1219862"},{"key":"9199_CR11","unstructured":"Charniak E (1997) Statistical parsing with a context-free grammar and word statistics. In: Proceedings of the fourteenth national conference on artificial intelligence, Menlo Park. AAAI Press\/MIT Press"},{"key":"9199_CR12","doi-asserted-by":"crossref","unstructured":"Chomsky N (1957) Syntactic Structures. The Hague Mouton.","DOI":"10.1515\/9783112316009"},{"key":"9199_CR13","doi-asserted-by":"crossref","unstructured":"Clark A (2001) Unsupervised induction of stochastic context-free grammars using distributional clustering. In: ConLL \u201801: Proceedings of the 2001 workshop on computational natural language learning, Morristown, NJ, USA. Association for Computational Linguistics, pp 1\u20138","DOI":"10.3115\/1117822.1117831"},{"key":"9199_CR14","doi-asserted-by":"crossref","unstructured":"Cramer B (2007) Limitations of current grammar induction algorithms. In: Proceedings of the 45th annual meeting of the ACL: student research workshop, June 25\u201326, 2007, Prague, Czech Republic","DOI":"10.3115\/1557835.1557845"},{"key":"9199_CR15","doi-asserted-by":"crossref","unstructured":"D\u00e9jean H (2000) ALLiS: a symbolic learning system for natural language learning. In: Cardie C, Daelemans W, N\u2019edellec C, Tjong Kim Sang E (eds) Proceedings of the fourth conference on computational natural language learning and of the second learning language in logic workshop; Lisbon, Portugal. Held in cooperation with ICGI-2000, pp 95\u201398","DOI":"10.3115\/1117601.1117622"},{"key":"9199_CR16","unstructured":"de la Higuera C, Oncina J (2003) Identification with Probability One of Stochastic Deterministic Linear Languages. In: Proceedings of ALT 2003. Springer, Berlin, Heidelberg, pp 134\u2013148"},{"key":"9199_CR17","doi-asserted-by":"crossref","unstructured":"Denis F (1998) Pac learning from positive statistical queries. In: Proceedings of 9th international conference on algorithmic learning theory\u2014ALT \u201898, Springer, pp 112\u2013126","DOI":"10.1007\/3-540-49730-7_9"},{"key":"9199_CR18","unstructured":"Edelman S, Solan Z, Horn D, Ruppin E (2005) Learning syntactic constructions from raw corpora. In: 29th Boston University conference on language development, Cascadilla Press"},{"key":"9199_CR19","doi-asserted-by":"crossref","unstructured":"Emerald JD, Subramanian KG, Thomas DG (1996) Learning code regular and code linear languages. In: Proceedings of international colloquium on grammatical inference (ICGI-96), lecture notes in artificial intelligence 1147, Springer, pp 211\u2013221","DOI":"10.1007\/BFb0033356"},{"issue":"9","key":"9199_CR20","doi-asserted-by":"crossref","first-page":"920","DOI":"10.1109\/34.57687","volume":"12","author":"P Garcia","year":"1990","unstructured":"Garcia P, Vidal E (1990) Inference of K-testable languages in the strict sense and applications to syntactic pattern recognition. J IEEE Trans Pattern Anal Mach Intell 12(9): 920\u2013925","journal-title":"J IEEE Trans Pattern Anal Mach Intell"},{"key":"9199_CR21","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1016\/S0019-9958(67)91165-5","volume":"10","author":"EM Gold","year":"1967","unstructured":"Gold EM (1967) Language identification in the limit. Inform Control 10: 447\u2013474","journal-title":"Inform Control"},{"key":"9199_CR22","unstructured":"H\u00e4nig C, Bordag S, Quasthoff U (2008) UnsuParse: unsupervised parsing with unsupervised part of speech tagging. In: Proceedings of the sixth international language resources and evaluation (LREC 2008)"},{"key":"9199_CR23","volume-title":"Introduction to automata theory, languages, and computation","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft JE, Ullman JE (1979) Introduction to automata theory, languages, and computation. Addison-Wesley, New York"},{"key":"9199_CR24","unstructured":"Horning JJ (1969) A study of grammatical inference. PhD thesis, Stanford University, Stanford:CA, USA"},{"key":"9199_CR25","unstructured":"Kasami T (1965) An efficient recognition and syntax analysis algorithm for context-free languages. Science report, Air Force Cambridge Research Laboratory, Bedford"},{"key":"9199_CR26","unstructured":"Koshiba T, Makinen E, Takada Y (1997) Inferring pure context-free languages from positive data. Technical report A-1997-14, Department of Computer Science, University of Tampere"},{"key":"9199_CR27","doi-asserted-by":"crossref","unstructured":"Langley P, Stromsten S (2000) Learning context-free grammars with a simplicity bias. In: Proceedings of the eleventh European conference on machine learning (ECML 2000), lecture notes in artificial intelligence 1810, Springer, pp 220\u2013228","DOI":"10.1007\/3-540-45164-1_23"},{"issue":"4","key":"9199_CR28","first-page":"845","volume":"163","author":"VI Levenshtein","year":"1965","unstructured":"Levenshtein VI (1965) Binary codes capable of correcting deletions, insertions, and reversals. Doklady Akademii Nauk SSR 163(4): 845\u2013848 (Original in Russian)","journal-title":"Doklady Akademii Nauk SSR"},{"key":"9199_CR29","volume-title":"The CHILDES project: tools for analyzing talk","author":"B MacWhinney","year":"1991","unstructured":"MacWhinney B (1991) The CHILDES project: tools for analyzing talk. Erlbaum, Mahwah"},{"issue":"2","key":"9199_CR30","first-page":"313","volume":"19","author":"M Marcus","year":"1993","unstructured":"Marcus M, Santorini B, Marcinkiewicz M (1993) Building a large annotated corpus of English: the Penn treebank. Comput Linguist 19(2): 313\u2013330","journal-title":"Comput Linguist"},{"key":"9199_CR31","doi-asserted-by":"crossref","unstructured":"McClosky D, Charniak E, Johnson M (2006) Effective self-training for parsing. In: Proceedings of HLT-NAACL 2006","DOI":"10.3115\/1220835.1220855"},{"key":"9199_CR32","first-page":"53","volume-title":"ECML workshop on learning contex-free grammars","author":"K Nakamura","year":"2003","unstructured":"Nakamura K (2003) Incremental learning of context free grammars by extended inductive cyk algorithm. In: Higuera C, Adriaans PW, Zaanen M, Oncina J (eds) ECML workshop on learning contex-free grammars. Ruder Boskovic Institute, Zagreb, pp 53\u201364"},{"key":"9199_CR33","doi-asserted-by":"crossref","unstructured":"Nakamura K, Matsumoto M (2002) Incremental learning of context free grammars. In: ICGI \u201802: proceedings of the 6th international colloquium on grammatical inference (London, UK), Springer, pp 174\u2013184","DOI":"10.1007\/3-540-45790-9_14"},{"key":"9199_CR34","doi-asserted-by":"crossref","unstructured":"Nakamura K, Ishiwata T (2000) Synthesizing context free grammars from sample strings based on inductive cyk algorithm. In: ICGI \u201800: proceedings of the 5th international colloquium on grammatical inference, London, UK, Springer, pp 186\u2013195","DOI":"10.1007\/978-3-540-45257-7_15"},{"key":"9199_CR35","first-page":"69","volume":"7","author":"G Petasis","year":"2004","unstructured":"Petasis G, Paliouras G, Karkaletsis V, Halatsis C, Spyropoulos CD (2004) e-GRIDS: computationally efficient grammatical inference from positive examples. GRAMMARS 7: 69\u2013110","journal-title":"GRAMMARS"},{"key":"9199_CR36","unstructured":"Pullum GK (2003) Learnability. In: The Oxford International Encyclopaedia of Linguistics, 2nd edn. Oxford, Oxford University Press, pp 431\u2013434"},{"key":"9199_CR37","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1214\/aos\/1176346150","volume":"11","author":"J Rissanen","year":"1982","unstructured":"Rissanen J (1982) A universal prior for integers and estimation by minimum description length. Ann Statist 11: 416\u2013431","journal-title":"Ann Statist"},{"key":"9199_CR38","unstructured":"Roberts A, Atwell E (2002) Unsupervised grammar inference systems for natural language. Research report number 2002.20. School of Computing, University of Leeds"},{"key":"9199_CR39","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. Theor Comput Sci 185: 15\u201345","journal-title":"Theor Comput Sci"},{"key":"9199_CR40","doi-asserted-by":"crossref","first-page":"5112","DOI":"10.1093\/nar\/22.23.5112","volume":"22","author":"Y Sakakibara","year":"1994","unstructured":"Sakakibara Y, Brown M, Hughley R, Mian I, Sjolander K, Underwood R, Haussler D (1994) Stochastic context-free grammars for tRNA modeling. Nucleic Acids Res 22: 5112\u20135120","journal-title":"Nucleic Acids Res"},{"key":"9199_CR41","doi-asserted-by":"crossref","unstructured":"Sakakibara Y, Muramatsu H (2000) Learning context-free grammars from partially structured examples. In: Proceedings of the 5th international colloquium on grammatical inference: algorithms and applications (ICGI), pp 229\u2013240","DOI":"10.1007\/978-3-540-45257-7_19"},{"issue":"3","key":"9199_CR42","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1142\/S0218001402001691","volume":"16","author":"I Salvador","year":"2002","unstructured":"Salvador I, Bened\u0131 JM (2002) RNA modeling by combining stochastic context-free grammars and n-Gram models. Int J Pattern Recogn Artif Intell 16(3): 309\u2013316","journal-title":"Int J Pattern Recogn Artif Intell"},{"key":"9199_CR43","unstructured":"Seginer Y (2007) Fast unsupervised incremental parsing. In: Proceedings of the ACL 2007, Prague"},{"issue":"33","key":"9199_CR44","doi-asserted-by":"crossref","first-page":"11629","DOI":"10.1073\/pnas.0409746102","volume":"102","author":"Z Solan","year":"2005","unstructured":"Solan Z, Horn D, Ruppin E, Edelman S (2005) Unsupervised learning of natural languages. Proc Natl Acad Sci USA 102(33): 11629\u201311634","journal-title":"Proc Natl Acad Sci USA"},{"key":"9199_CR45","doi-asserted-by":"crossref","unstructured":"Steedman M, Osborne M, Sarkar A, Clark S, Hwa R, Hockenmaier J, Ruhlen P, Baker S, Crim J (2003) Bootstrapping statistical parsers from small datasets. In: Proceedings of the annual meeting of the European chapter of the ACL, Budapest, Hungary","DOI":"10.3115\/1067807.1067851"},{"key":"9199_CR46","unstructured":"van Zaanen MV (2001) Bootstrapping structure into language: alignment-based learning. PhD thesis, School of Computing, University of Leeds, UK"},{"key":"9199_CR47","unstructured":"van Zaanen M, Adriaans P (2001) Alignment-based learning versus EMILE: a comparison. In: Proceedings of the Belgian-Dutch conference on artificial intelligence (BNAIC), Amsterdam, The Netherlands"},{"key":"9199_CR48","unstructured":"Watkinson S, Manandhar S (2001) A psychologically plausible and computationally effective approach to learning syntax. In: Proceedings of the workshop computational natural language learning (CoNLL-2001), pp 160\u2013167"},{"key":"9199_CR49","first-page":"153","volume":"19","author":"T Yokomori","year":"1995","unstructured":"Yokomori T (1995) On polynomial-time learnability in the limit of strictly deterministic automata. J Mach Learn 19: 153\u2013179","journal-title":"J Mach Learn"}],"container-title":["Artificial Intelligence Review"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10462-010-9199-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10462-010-9199-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10462-010-9199-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,15]],"date-time":"2020-06-15T08:30:01Z","timestamp":1592209801000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10462-010-9199-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,6]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,6]]}},"alternative-id":["9199"],"URL":"https:\/\/doi.org\/10.1007\/s10462-010-9199-1","relation":{},"ISSN":["0269-2821","1573-7462"],"issn-type":[{"value":"0269-2821","type":"print"},{"value":"1573-7462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1,6]]}}}