{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T19:23:39Z","timestamp":1747164219287,"version":"3.40.5"},"reference-count":24,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T00:00:00Z","timestamp":1659312000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2023,3,2]],"date-time":"2023-03-02T00:00:00Z","timestamp":1677715200000},"content-version":"am","delay-in-days":213,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"},{"start":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T00:00:00Z","timestamp":1659312000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T00:00:00Z","timestamp":1659312000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T00:00:00Z","timestamp":1659312000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T00:00:00Z","timestamp":1659312000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2022,8,1]],"date-time":"2022-08-01T00:00:00Z","timestamp":1659312000000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2022,8]]},"DOI":"10.1016\/j.jcss.2022.02.003","type":"journal-article","created":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T15:59:51Z","timestamp":1645631991000},"page":"41-52","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":3,"special_numbering":"C","title":["O is an n-MCFL"],"prefix":"10.1016","volume":"127","author":[{"given":"Kilian","family":"Gebhardt","sequence":"first","affiliation":[]},{"given":"Fr\u00e9d\u00e9ric","family":"Meunier","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6230-0098","authenticated-orcid":false,"given":"Sylvain","family":"Salvati","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"issue":"2","key":"10.1016\/j.jcss.2022.02.003_br0010","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/1150334.1150336","article-title":"Algorithmic construction of sets for k-restrictions","volume":"2","author":"Alon","year":"2006","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"10.1016\/j.jcss.2022.02.003_br0020","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1090\/S0002-9939-1986-0861764-9","article-title":"The Borsuk\u2013Ulam theorem and bisection of necklaces","volume":"98","author":"Alon","year":"1986","journal-title":"Proc. Am. Math. Soc."},{"key":"10.1016\/j.jcss.2022.02.003_br0030","series-title":"Proceedings of the 11th Annual Meeting of the Northeastern Linguistics Society","first-page":"1","article-title":"Discontinuous constituents in generalized categorial grammars","author":"Bach","year":"1981"},{"key":"10.1016\/j.jcss.2022.02.003_br0040","series-title":"Categorial Grammars and Natural Language Structures","first-page":"17","article-title":"Categorial grammars as theories of language","author":"Bach","year":"1988"},{"issue":"3","key":"10.1016\/j.jcss.2022.02.003_br0050","doi-asserted-by":"crossref","first-page":"431","DOI":"10.2307\/1969651","article-title":"A generalization of Tucker's combinatorial lemma with topological applications","volume":"56","author":"Fan","year":"1952","journal-title":"Ann. Math."},{"key":"10.1016\/j.jcss.2022.02.003_br0060","series-title":"Groups, Languages, Algorithms","first-page":"1","article-title":"Formal languages and their application to combinatorial group theory","volume":"vol. 378","author":"Gilman","year":"2005"},{"author":"Gebhardt","key":"10.1016\/j.jcss.2022.02.003_br0070"},{"issue":"1","key":"10.1016\/j.jcss.2022.02.003_br0080","first-page":"9","article-title":"The word problem of Zn is a multiple context-free language","volume":"10","author":"Ho","year":"2018","journal-title":"Groups Complex. Cryptol."},{"issue":"4","key":"10.1016\/j.jcss.2022.02.003_br0090","first-page":"665","article-title":"A moment problem in l1 approximation","volume":"16","author":"Hobby","year":"1965","journal-title":"Proc. Am. Math. Soc."},{"key":"10.1016\/j.jcss.2022.02.003_br0100","series-title":"Natural Language Parsing","first-page":"206","article-title":"Tree-adjoining grammars: how much context sensitivity is required to provide reasonable structural descriptions?","author":"Joshi","year":"1985"},{"key":"10.1016\/j.jcss.2022.02.003_br0110","series-title":"Foundational Issues in Natural Language Processing","first-page":"31","article-title":"The convergence of mildly context-sensitive grammar formalisms","author":"Joshi","year":"1991"},{"key":"10.1016\/j.jcss.2022.02.003_br0120","series-title":"Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics","first-page":"666","article-title":"MIX is not a tree-adjoining language","author":"Kanazawa","year":"2012"},{"key":"10.1016\/j.jcss.2022.02.003_br0130","doi-asserted-by":"crossref","DOI":"10.1515\/9781400879946","article-title":"Introduction to Topology","author":"Lefschetz","year":"1949"},{"issue":"3","key":"10.1016\/j.jcss.2022.02.003_br0140","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0022-0000(83)90003-X","article-title":"Groups, the theory of ends, and context-free languages","volume":"26","author":"Muller","year":"1983","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/j.jcss.2022.02.003_br0150","series-title":"Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics","article-title":"A short proof that O2 is an MCFL","author":"Nederhof","year":"2016"},{"key":"10.1016\/j.jcss.2022.02.003_br0160","series-title":"From Semantics to Dialectometry: Festschrift for John Nerbonne","first-page":"273","article-title":"Free word order and MCFLs","author":"Nederhof","year":"2017"},{"key":"10.1016\/j.jcss.2022.02.003_br0170","doi-asserted-by":"crossref","DOI":"10.37236\/168","article-title":"Combinatorial necklace splitting","author":"P\u00e1lv\u00f6lgyi","year":"2009","journal-title":"Electron. J. Comb."},{"issue":"1","key":"10.1016\/j.jcss.2022.02.003_br0180","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1090\/S0002-9939-1976-0425470-0","article-title":"A simple proof of the Hobby\u2013Rice theorem","volume":"60","author":"Pinkus","year":"1976","journal-title":"Proc. Am. Math. Soc."},{"key":"10.1016\/j.jcss.2022.02.003_br0190","series-title":"Proceedings of the 21st Annual Meeting of the Association for Computational Linguistics","first-page":"1","article-title":"Context-freeness and the computer processing of human languages","author":"Pullum","year":"1983"},{"issue":"7","key":"10.1016\/j.jcss.2022.02.003_br0200","doi-asserted-by":"crossref","first-page":"1252","DOI":"10.1016\/j.jcss.2015.03.004","article-title":"MIX is a 2-MCFL and the word problem in Z2 is captured by the IO and the OI hierarchies","volume":"81","author":"Salvati","year":"2015","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"10.1016\/j.jcss.2022.02.003_br0210","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1093\/ietisy\/e91-d.2.209","article-title":"On the generative power of multiple context-free grammars and macro grammars","volume":"91-D","author":"Seki","year":"2008","journal-title":"IEICE Trans."},{"issue":"2","key":"10.1016\/j.jcss.2022.02.003_br0220","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0304-3975(91)90374-B","article-title":"On multiple context free grammars","volume":"88","author":"Seki","year":"1991","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.jcss.2022.02.003_br0230","series-title":"Proc. First Canadian Math. Congress 1945","first-page":"285","article-title":"Some topological properties of disk and sphere","author":"Tucker","year":"1946"},{"year":"1988","series-title":"Characterizing mildly context-sensitive grammar formalisms","author":"Weir","key":"10.1016\/j.jcss.2022.02.003_br0240"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000022000174?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000022000174?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,12,27]],"date-time":"2022-12-27T17:09:27Z","timestamp":1672160967000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000022000174"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8]]},"references-count":24,"alternative-id":["S0022000022000174"],"URL":"https:\/\/doi.org\/10.1016\/j.jcss.2022.02.003","relation":{},"ISSN":["0022-0000"],"issn-type":[{"type":"print","value":"0022-0000"}],"subject":[],"published":{"date-parts":[[2022,8]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"On is an n-MCFL","name":"articletitle","label":"Article Title"},{"value":"Journal of Computer and System Sciences","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.jcss.2022.02.003","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2022 Elsevier Inc. All rights reserved.","name":"copyright","label":"Copyright"}]}}