{"entities":{"Q1177161":{"pageid":1187910,"ns":120,"title":"Item:Q1177161","lastrevid":46246420,"modified":"2025-12-24T09:42:02Z","type":"item","id":"Q1177161","labels":{"en":{"language":"en","value":"On multiple context-free grammars"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 20016"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177161$8A25339D-16F2-45EC-9AE7-3FBBB08D04F0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5e946ea68d2f00d62f79bfc101144450ab7ce0d2","datavalue":{"value":{"text":"On multiple context-free grammars","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1177161$0EFE90B6-D6AF-40C7-ABA0-06BD14DC4F46","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e99f7cd64b37c6666f0f14bb572e1e0caaeb0f8e","datavalue":{"value":"0762.68039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177161$83F23D17-5E61-44AE-8341-2CD73142DF7E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f2e2f20285cfe9c4fddfc4aec1fb2cc6ab2cdd33","datavalue":{"value":"10.1016/0304-3975(91)90374-B","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177161$DB427DD7-360B-45EB-BEE4-C04C1581EF9F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9fb2d259f8ee70e6c5555f0f5760222d05e77b94","datavalue":{"value":{"entity-type":"item","numeric-id":208751,"id":"Q208751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177161$186C1C87-F394-4843-8129-3B331F346331","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c467a2670a6c063bd4781a7319ce556036622dfb","datavalue":{"value":{"entity-type":"item","numeric-id":1177159,"id":"Q1177159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177161$B870B53E-94AB-46A3-9FBA-EFEBBA0DF9D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"870f737de7bddcc240db9aefd597aa6a164bc2c9","datavalue":{"value":{"entity-type":"item","numeric-id":1177160,"id":"Q1177160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177161$1247AE8F-9432-46E3-A05E-B8BA0FB2FA22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5ac8477c8571818916759218f885a65ca2902ef6","datavalue":{"value":{"entity-type":"item","numeric-id":1060027,"id":"Q1060027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177161$BE2105E3-92F0-4C46-8A7A-6BEB4765314E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177161$5A4C37F6-EC52-412C-87C5-93991F2C7355","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1177161$88062A7D-0F65-4C1B-B80B-4C5B2B387753","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dd3b83138cfd59c4caad0a112e643956e48d3085","datavalue":{"value":"This paper discusses some generalizations of context free grammars. The resulting languages lie between the class of context free languages and the class of context sensitive languages. The paper investigates and establishes containment relations, many of them strict, between the newly introduced classes of languages.   The new classes of languages are known as \\(m\\)-parallel multiple context free languages (\\(m-PMCFL\\)) and \\(m\\)-multiple context free languages (\\(m- MFCL\\)), where \\(m\\) is a natural number parameter. For example, the class \\(1-MCFL\\) is identical to the class of context free languages; \\(\\{a^{2^ n}n\\geq 0\\}\\) is a \\(1-PMCFL\\), and \\(\\{a^{n^ 2}n>0\\}\\) is a \\(2-PMCFL\\). The paper gives the containment relation \\(m-MCFL\\subset m- PMCFL\\) and the strict containment relation \\(m-MCFL\\subset (m+1)-MCFL\\). In addition, considering the classes \\(PMCFL=\\cup_ mm-PMCFL\\) and \\(MCFL=\\cup_ mm-MCFL\\), the paper proves that \\(MCFL\\) is properly contained in \\(PMCFL\\), which itself is properly contained in the class of context sensitive languages. Also, all the above classes are substitution-closed full AFLs.   The paper contains an extensive development of these language classes, including algorithms for testing membership, a pumping lemma, and analyses of derivations. It also considers two classes of grammars previously considered by other authors - head grammars (hgs) and tree adjoining grammars (tags) - and relates them to the currently considered classes.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177161$3133E85E-BE95-4A59-B856-F11EBA44E899","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177161$AC42EFE6-BBD3-434A-A317-EAD7E2CD8349","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177161$7D14856D-F79C-4979-83DF-7F54FE9D4AD5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d2bf4bea8c5fd3b5139d2c5adf0efcc302701d27","datavalue":{"value":"20016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177161$B44585CF-9FC2-4AD1-A86C-80A9018B50C0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5fb45d500db3cc394a8455fe28c2a1ecac31286","datavalue":{"value":"multiple context free grammar","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177161$1EFB6005-228C-4204-8DE4-59D63F6B55BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"44d2f2957b6a571bacf97ef6be5a6945b29311c7","datavalue":{"value":"context free languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177161$CC3131AC-176B-4891-8C7A-A97E67FF7F7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf07cb3ab1d14e971f28a4a5a0947ab8907795ce","datavalue":{"value":"context sensitive languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177161$D3A84BAE-5145-41A1-ABC9-D492C9362F71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"08a7452d07b5ec0275f65ab9938005071aff974b","datavalue":{"value":"head grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177161$BB348F42-A30A-4F54-8E95-C0DE8565508A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dcdef2f48832f57f749312873a1fbe9a2558704c","datavalue":{"value":"tree adjoining grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177161$EB746250-50ED-4587-AE4D-0B8303D5DBB3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7a747404b59b859f32425194571ad2a4a9cc4221","datavalue":{"value":{"entity-type":"item","numeric-id":1839320,"id":"Q1839320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177161$931153B9-D487-4477-A60C-A60B71867D08","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177161$5D12B1A9-E1C9-481F-B845-80E1DB770309","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177161$B43287D5-A094-43ED-A645-CCB0CCF55A5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76e34b733d5c968f4670211735e85d54b3608649","datavalue":{"value":{"entity-type":"item","numeric-id":1225947,"id":"Q1225947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177161$A4038072-9192-4301-AC5F-E8B9B510BE0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56aa7a343db226e6c7da9bd7db585a412df58862","datavalue":{"value":{"entity-type":"item","numeric-id":5678435,"id":"Q5678435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177161$98A88744-A8E1-4894-9D8A-E52736BEF7F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d84f24dac612efbeb8b272b4c01bb6817bd11b6","datavalue":{"value":{"entity-type":"item","numeric-id":4776850,"id":"Q4776850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177161$A30D9E2D-D971-4601-9A82-C96AF8B623F4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c645cbe337c0e926123e141dbabf02ec70f9eec6","datavalue":{"value":"https://doi.org/10.1016/0304-3975(91)90374-b","type":"string"},"datatype":"url"},"type":"statement","id":"Q1177161$1E9C1D17-22BB-4D94-B716-36CDEFBAF586","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b3d4f3f82149978ec01a27ee0c6a0f48c8e55d0f","datavalue":{"value":"W2089385274","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177161$418C7707-765C-433B-878B-DC5C0C7AD150","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a60b72115e726efd01d5c35b372f3ef0c24fa849","datavalue":{"value":{"entity-type":"item","numeric-id":5687660,"id":"Q5687660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51a2058db55d796943f4793f3d038c696580d0e6","datavalue":{"value":{"amount":"+0.7969111204147339","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1177161$FCB49732-D7DF-498D-9B4E-9BC72C6A7A65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ac5a84553e92ce31daeab1d6884ba5fef7374d9","datavalue":{"value":{"entity-type":"item","numeric-id":1749480,"id":"Q1749480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6e82f8cc933c0d856aa9e9ea04488b546ea3c09","datavalue":{"value":{"amount":"+0.7955946326255798","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1177161$FBAB1539-C386-4A84-B007-6396F7D6C7C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"603112349c690bc43ccf2606b7148f665770e347","datavalue":{"value":{"entity-type":"item","numeric-id":2770668,"id":"Q2770668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39be1244d750bd9be8012d7bdd6cfea568cd7bc3","datavalue":{"value":{"amount":"+0.7865138053894043","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1177161$A2737F12-9978-4D6D-B4B2-2F35420BB315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a66f9bf69e8963fa3f65a4fc91ce2bcd9f367f48","datavalue":{"value":{"entity-type":"item","numeric-id":4311636,"id":"Q4311636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07c2932bd883e8d577e1ef02e293a3ca8e58a3d3","datavalue":{"value":{"amount":"+0.7859922051429749","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1177161$CF68F65D-9FE9-41BE-8527-9E1E2BB22BEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e25ef7fedf90d9fadf89c07f9454ea6bbab56df9","datavalue":{"value":{"entity-type":"item","numeric-id":3795250,"id":"Q3795250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87c3d8bcb423e6e411efeaba8143b2040f592c80","datavalue":{"value":{"amount":"+0.7853683233261108","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1177161$89A81961-0F57-4FE9-ACF5-7C60BF9539EB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1177161","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1177161"}}}}}