{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,29]],"date-time":"2025-03-29T04:11:52Z","timestamp":1743221512959,"version":"3.40.3"},"reference-count":49,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2012,9,1]],"date-time":"2012-09-01T00:00:00Z","timestamp":1346457600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2016,9,21]],"date-time":"2016-09-21T00:00:00Z","timestamp":1474416000000},"content-version":"vor","delay-in-days":1481,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2012,9]]},"DOI":"10.1016\/j.tcs.2012.05.016","type":"journal-article","created":{"date-parts":[[2012,5,22]],"date-time":"2012-05-22T02:29:50Z","timestamp":1337653790000},"page":"21-38","source":"Crossref","is-referenced-by-count":5,"special_numbering":"C","title":["On families of categorial grammars of bounded value, their learnability and related complexity questions"],"prefix":"10.1016","volume":"452","author":[{"given":"Christophe","family":"Costa Flor\u00eancio","sequence":"first","affiliation":[]},{"given":"Henning","family":"Fernau","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.tcs.2012.05.016_br000005","unstructured":"M. Kanazawa, Learnable classes of categorial grammars, Ph.D. Thesis, CSLI, 1998."},{"key":"10.1016\/j.tcs.2012.05.016_br000010","unstructured":"C. Costa\u00a0Flor\u00eancio, Learning categorial grammars, Ph.D. Thesis, Universiteit Utrecht, The Netherlands, 2003."},{"year":"1999","series-title":"Parameterized Complexity","author":"Downey","key":"10.1016\/j.tcs.2012.05.016_br000015"},{"key":"10.1016\/j.tcs.2012.05.016_br000020","series-title":"Scientific Applications of Language Methods","first-page":"1","article-title":"Descriptional complexity \u2014 an introductory survey","volume":"vol.~2","author":"Holzer","year":"2010"},{"key":"10.1016\/j.tcs.2012.05.016_br000025","series-title":"COLT\u201993","first-page":"51","article-title":"Parameterized learning complexity","author":"Downey","year":"1993"},{"key":"10.1016\/j.tcs.2012.05.016_br000030","series-title":"Computer and Information Sciences II \u2014 26th International Symposium on Computer and Information Sciences","first-page":"277","article-title":"On the parameterised complexity of learning patterns","author":"Stephan","year":"2011"},{"key":"10.1016\/j.tcs.2012.05.016_br000035","series-title":"Language and Automata Theory and Applications LATA","first-page":"202","article-title":"Finding consistent categorial grammars of bounded value: a parameterized approach","volume":"vol. 6031","author":"Costa~Flor\u00eancio","year":"2010"},{"key":"10.1016\/j.tcs.2012.05.016_br000040","series-title":"International Colloquium on Grammatical Inference ICGI","first-page":"280","article-title":"H\u00f6lder norms and a hierarchy theorem for parameterized classes of CCG","volume":"vol.6339","author":"Costa~Flor\u00eancio","year":"2010"},{"key":"10.1016\/j.tcs.2012.05.016_br000045","series-title":"Categories, Polymorphism and Unification","first-page":"35","article-title":"Discovery procedures for categorial grammars","author":"Buszkowski","year":"1987"},{"key":"10.1016\/j.tcs.2012.05.016_br000050","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1007\/BF00370157","article-title":"Categorial grammars determined from linguistic data by unification","volume":"49","author":"Buszkowski","year":"1990","journal-title":"Stud. Log."},{"key":"10.1016\/j.tcs.2012.05.016_br000055","first-page":"1","article-title":"Die syntaktische Konnexit\u00e4t","volume":"1","author":"Adjukiewicz","year":"1935","journal-title":"Studia Philosophica"},{"key":"10.1016\/j.tcs.2012.05.016_br000060","doi-asserted-by":"crossref","first-page":"154","DOI":"10.2307\/2310058","article-title":"The mathematics of sentence structure","volume":"65","author":"Lambek","year":"1958","journal-title":"Amer. Math. Monthly"},{"key":"10.1016\/j.tcs.2012.05.016_br000065","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0024-3841(93)90024-Q","article-title":"Categorial grammar. Tutorial overview","volume":"90","author":"Steedman","year":"1993","journal-title":"Lingua"},{"year":"2000","series-title":"The Syntactic Process","author":"Steedman","key":"10.1016\/j.tcs.2012.05.016_br000070"},{"key":"10.1016\/j.tcs.2012.05.016_br000075","series-title":"Handbook of Logic and Language","first-page":"93","article-title":"Categorial type logics","author":"Moortgat","year":"1997"},{"key":"10.1016\/j.tcs.2012.05.016_br000080","series-title":"Proceedings. of the 10th Workshop on Logic, Language, Information and Computation, WoLLIC\u20192003, vol.~84","first-page":"60","article-title":"k-valued non-associative Lambek grammars are learnable from function-argument structures","author":"B\u00e9chet","year":"2003"},{"key":"10.1016\/j.tcs.2012.05.016_br000085","doi-asserted-by":"crossref","unstructured":"C. Costa\u00a0Flor\u00eancio, A limit point for rigid associative-commutative Lambek grammars, in: A.\u00a0Copestake, J.\u00a0Hajic\u02d8 (Eds.), Proceedings of EACL2003, Tenth Conference of the European Chapter of the Association for Computational Linguistics, Budapest, April 12\u201317, pp. 75\u201382.","DOI":"10.3115\/1067807.1067819"},{"key":"10.1016\/j.tcs.2012.05.016_br000090","doi-asserted-by":"crossref","first-page":"1095","DOI":"10.1016\/j.ic.2008.03.011","article-title":"Comparison of some descriptional complexities of 0L systems obtained by a unifying approach","volume":"206","author":"Dassow","year":"2008","journal-title":"Inf. Comput."},{"key":"10.1016\/j.tcs.2012.05.016_br000095","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1016\/S0019-9958(67)91165-5","article-title":"Language identification in the limit","volume":"10","author":"Gold","year":"1967","journal-title":"Inf. and Control"},{"year":"1999","series-title":"Systems that Learn: An Introduction to Learning Theory","author":"Jain","key":"10.1016\/j.tcs.2012.05.016_br000100"},{"key":"10.1016\/j.tcs.2012.05.016_br000105","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0019-9958(80)90285-5","article-title":"Inductive inference of formal languages from positive data","volume":"45","author":"Angluin","year":"1980","journal-title":"Inf. and Control"},{"year":"1994","series-title":"Grammar Systems: A Grammatical Approach to Distribution and Cooperation","author":"Csuhaj-Varj\u00fa","key":"10.1016\/j.tcs.2012.05.016_br000110"},{"key":"10.1016\/j.tcs.2012.05.016_br000115","unstructured":"D. Dudau-Sofronie, I. Tellier, M. Tommasi, A learnable class of classical categorial grammars from typed examples, in: 8th Conference on Formal Grammar, pp. 77\u201388."},{"year":"2004","series-title":"On The Logic And Learning Of Language","author":"Fulop","key":"10.1016\/j.tcs.2012.05.016_br000120"},{"key":"10.1016\/j.tcs.2012.05.016_br000125","series-title":"Proceedings of the Fourth Annual Workshop on Computational Learning Theory","first-page":"213","article-title":"Polynomial-time learning of very simple grammars from positive data","author":"Yokomori","year":"1991"},{"key":"10.1016\/j.tcs.2012.05.016_br000130","series-title":"Analogical and Inductive Inference: Proceedings of the International Workshop AII\u201992","first-page":"72","article-title":"Too much information can be too much for learning efficiently","author":"Wiehagen","year":"1992"},{"key":"10.1016\/j.tcs.2012.05.016_br000135","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1080\/09528139408953785","article-title":"Ignoring data may be the only way to learn efficiently","volume":"6","author":"Wiehagen","year":"1994","journal-title":"J. Exp. Theor. Artif. Intell."},{"key":"10.1016\/j.tcs.2012.05.016_br000140","series-title":"4th Workshop on Algorithmic Learning Theory ALT\u201993","first-page":"187","article-title":"Properties of language classes with finite elasticity","volume":"vol. 744","author":"Moriyama","year":"1993"},{"key":"10.1016\/j.tcs.2012.05.016_br000145","series-title":"COLT\u201991","first-page":"375","article-title":"The correct definition of finite elasticity: corrigendum to identification of unions","author":"Motoki","year":"1991"},{"key":"10.1016\/j.tcs.2012.05.016_br000150","series-title":"COLT\u201989","first-page":"328","article-title":"Identification of unions and languages drawn from an identifiable class","author":"Wright","year":"1989"},{"year":"1984","series-title":"Graph Algorithms and NP-Completeness","author":"Mehlhorn","key":"10.1016\/j.tcs.2012.05.016_br000155"},{"year":"2006","series-title":"Parameterized Complexity Theory","author":"Flum","key":"10.1016\/j.tcs.2012.05.016_br000160"},{"year":"2006","series-title":"Invitation to Fixed-Parameter Algorithms","author":"Niedermeier","key":"10.1016\/j.tcs.2012.05.016_br000165"},{"key":"10.1016\/j.tcs.2012.05.016_br000170","doi-asserted-by":"crossref","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","article-title":"Improved upper bounds for vertex cover","volume":"411","author":"Chen","year":"2010","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/j.tcs.2012.05.016_br000175","series-title":"Grammatical Inference: Algorithms and Applications; 6th International Colloquium","first-page":"49","article-title":"Consistent identification in the limit of rigid grammars from strings is NP-hard","volume":"vol. 2484","author":"Costa~Flor\u00eancio","year":"2002"},{"key":"10.1016\/j.tcs.2012.05.016_br000180","first-page":"133","article-title":"\u00dcber extreme Punkt- und Kantenmengen","volume":"2","author":"Gallai","year":"1959","journal-title":"Ann. Univ. Sci. Budapest, E\u00f6tv\u00f6s Sect. Math."},{"key":"10.1016\/j.tcs.2012.05.016_br000185","unstructured":"I.v. Rooij, Tractable cognition: complexity theory in cognitive psychology, Ph.D. Thesis, University of Victoria, Canada, 2003."},{"key":"10.1016\/j.tcs.2012.05.016_br000190","doi-asserted-by":"crossref","first-page":"939","DOI":"10.1080\/03640210801897856","article-title":"The tractable cognition thesis","volume":"32","author":"Rooij","year":"2008","journal-title":"Cogn. Sci."},{"key":"10.1016\/j.tcs.2012.05.016_br000195","first-page":"41","article-title":"Parameterized complexity for graph layout problems","volume":"86","author":"Serna","year":"2005","journal-title":"EATCS Bulletin"},{"key":"10.1016\/j.tcs.2012.05.016_br000200","series-title":"Combinatorial Algorithms","first-page":"2","article-title":"Towards fully multivariate algorithmics: some new results and directions in parameter ecology","volume":"vol. 5874","author":"Fellows","year":"2009"},{"key":"10.1016\/j.tcs.2012.05.016_br000205","series-title":"27th International Symposium on Theoretical Aspects of Computer Science","first-page":"17","article-title":"Reflections on multivariate algorithmics and problem parameterization","volume":"vol. 5","author":"Niedermeier","year":"2010"},{"key":"10.1016\/j.tcs.2012.05.016_br000210","doi-asserted-by":"crossref","unstructured":"F. Baader, J.H. Siekmann, Unification theory, in Ref.\u00a0[49], Oxford University Press, 1994, pp. 41\u2013125.","DOI":"10.1093\/oso\/9780198537465.003.0002"},{"key":"10.1016\/j.tcs.2012.05.016_br000215","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1145\/1077464.1077476","article-title":"The NP-completeness column","volume":"1","author":"Johnson","year":"2005","journal-title":"ACM Trans. Algorithms"},{"year":"1993","series-title":"Graph Isomorphism Problem: The Structural Complexity","author":"K\u00f6bler","key":"10.1016\/j.tcs.2012.05.016_br000220"},{"key":"10.1016\/j.tcs.2012.05.016_br000225","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1002\/jgt.3190010410","article-title":"The graph isomorphism disease","volume":"1","author":"Read","year":"1977","journal-title":"J. Graph Theory"},{"key":"10.1016\/j.tcs.2012.05.016_br000230","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1145\/322326.322334","article-title":"Inference of reversible languages","volume":"29","author":"Angluin","year":"1982","journal-title":"J. ACM"},{"key":"10.1016\/j.tcs.2012.05.016_br000235","series-title":"Proceedings of the 5th GI-Conference on Theoretical Computer Science","first-page":"13","article-title":"On the height of syntactical graphs","volume":"vol. 104","author":"Brandenburg","year":"1981"},{"key":"10.1016\/j.tcs.2012.05.016_br000240","series-title":"Fundamentals of Computation Theory, 12th International Symposium","first-page":"441","article-title":"A parallel context-free derivation hierarchy","volume":"vol. 1684","author":"Reinhardt","year":"1999"},{"year":"1994","series-title":"Handbook of Logic in Artificial Intelligence and Logic Programming","key":"10.1016\/j.tcs.2012.05.016_br000245"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397512004604?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397512004604?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T13:29:37Z","timestamp":1743168577000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397512004604"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9]]},"references-count":49,"alternative-id":["S0304397512004604"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2012.05.016","relation":{},"ISSN":["0304-3975"],"issn-type":[{"type":"print","value":"0304-3975"}],"subject":[],"published":{"date-parts":[[2012,9]]}}}