{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T07:11:22Z","timestamp":1698045082632},"reference-count":6,"publisher":"Wiley","issue":"6","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"vor","delay-in-days":6653,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp; Computers in Japan"],"published-print":{"date-parts":[[1989,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper considers multiple context\u2010free grammars (mcfg's) which inherit the basic properties of context\u2010free grammars with generative capacity stronger than that of context\u2010free grammars but weaker than that of context\u2010sensitive grammars. It is shown that the time complexity of the membership problem for languages generated by mcfg's is polynomial. It is shown also that head grammars introduced by Pollard for describing the syntax of natural language correspond to a special subclass of mcfg's and, as a corollary, the time complexity of the membership problem for languages generated by head grammars is of order <jats:italic>n<\/jats:italic><jats:sup>6<\/jats:sup>.* This is an improvement by one order of magnitude, compared with the result by Pollard.<\/jats:p>","DOI":"10.1002\/scj.4690200605","type":"journal-article","created":{"date-parts":[[2007,11,14]],"date-time":"2007-11-14T12:18:53Z","timestamp":1195042733000},"page":"43-51","source":"Crossref","is-referenced-by-count":0,"title":["Membership problem for head languages and multiple context\u2010free languages"],"prefix":"10.1002","volume":"20","author":[{"given":"Tadao","family":"Kasami","sequence":"first","affiliation":[]},{"given":"Hiroyuki","family":"Seki","sequence":"additional","affiliation":[]},{"given":"Mamoru","family":"Fujii","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,3,21]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"T.Kasami H.SekiandM.Fujii.Generalized context\u2010free grammar multiple context\u2010free grammar and head grammar. Tech. Rep. Nat. Lang. Proc. Inf. Proc. Soc. Japan (Sept.1987)."},{"key":"e_1_2_1_3_2","series-title":"Iwanami Ser. 6","volume-title":"Automaton, Theory of Formal Language and Theory of Computation","author":"Fukumura","year":"1982"},{"key":"e_1_2_1_4_2","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J.","year":"1979"},{"key":"e_1_2_1_5_2","unstructured":"C. J.Pollard.Generalized phrase structure grammars head grammars and natural language. Ph.D. dissertation Stanford University (Feb.1984)."},{"issue":"5","key":"e_1_2_1_6_2","first-page":"758","article-title":"Generalized context\u2010free grammar and multiple context\u2010free grammar","volume":"71","author":"Kasami T.","year":"1988","journal-title":"Trans. (D), I.E.C.I.E., Japan"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"K.Vijay\u2010Shanker D. J.Weir andA. K.Joshi.Tree adjoining and head wrapping. Proc. of 11th Intl. Conf. on Comput. Ling. pp.202\u2013207(1986).","DOI":"10.3115\/991365.991425"}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690200605","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690200605","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T11:51:38Z","timestamp":1697975498000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690200605"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,1]]},"references-count":6,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1989,1]]}},"alternative-id":["10.1002\/scj.4690200605"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690200605","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,1]]}}}