{"entities":{"Q579948":{"pageid":581715,"ns":120,"title":"Item:Q579948","lastrevid":62944923,"modified":"2026-04-11T09:09:28Z","type":"item","id":"Q579948","labels":{"en":{"language":"en","value":"Membership for growing context-sensitive grammars is polynomial"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4016213"}},"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":"Q579948$4EA8F3C1-CD58-4296-A30A-222445A4C266","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c894b6df1456f895d327b75a1c478d8dff1dfc3f","datavalue":{"value":{"text":"Membership for growing context-sensitive grammars is polynomial","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q579948$CDA2C8B9-8EEA-4889-942C-7736FB10848E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"494584896245b5a263dc420fae68e0a6012704b3","datavalue":{"value":"0625.68055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579948$506B72B7-5786-4D15-943C-87A985DBB649","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dd8373caa46a163f7e49de5ab5df7a439c21781d","datavalue":{"value":"10.1016/0022-0000(86)90062-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579948$5FE3C806-C7E4-47FD-A44B-2A82043435D4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9d1c5666cfcb8034d94e72905fe0b245c5645906","datavalue":{"value":{"entity-type":"item","numeric-id":233438,"id":"Q233438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$5BA91081-2BAE-415C-A863-88AF07CD27E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4d42337cf24b90f5ac095f15e64afb2b57c10dc7","datavalue":{"value":{"entity-type":"item","numeric-id":391735,"id":"Q391735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$9FA564ED-835E-4E05-81F7-78CC77EAF017","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$34850E44-1542-47CE-90A2-E715B84E84F0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q579948$0A77323C-FC76-40B3-BC65-C712FD9D6EC9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9ccbb8ab66e44fe5ac49786c9b80fa77e04a86d8","datavalue":{"value":"A context-sensitive grammar is a growing context-sensitive grammar, if the right-hand side of every production is strictly longer than the left- hand side. We show that for any fixed growing context sensitive grammar, the membership problem for the corresponding language is polynomial.","type":"string"},"datatype":"string"},"type":"statement","id":"Q579948$D981D6AA-B13A-436C-98A5-0616361C566D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579948$8B4C0504-0ACD-4953-9989-94C5574526C7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9304f8d1f87583e8e24a6f221d90951f5c403659","datavalue":{"value":"4016213","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579948$4D3444AF-AA2B-4516-8562-4D77C09DFABC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0294b6c368af97e8cdb7cb82fc5afee5e14ec8e2","datavalue":{"value":"context-sensitive grammar","type":"string"},"datatype":"string"},"type":"statement","id":"Q579948$8685A0C7-B21D-4284-88C2-E3C6E96D4FCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a2a5aaf2813613e191091bab6a7937bd2f6db3d","datavalue":{"value":"membership problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q579948$BF15E748-D6CE-42C6-A5CC-4B374954CDE5","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":"Q579948$1BE43213-A323-4838-9C95-5E9AC07FA983","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b17922e358a90c96302885f7290e8de34af01411","datavalue":{"value":"https://doi.org/10.1016/0022-0000(86)90062-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q579948$5510365D-F5B7-4DFF-B1B4-8D42F1DEDEDB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"044516926fba98fbb5c7cbe1e1e9ae812ba69e38","datavalue":{"value":"W1970379778","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579948$2FA2C735-ADE8-495F-8019-FC36F651300B","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"59d87406fd7dfca8461507f2b9a1b651e0e6791b","datavalue":{"value":"Q60307679","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579948$BF52ED24-9DFC-45C3-A20F-913112F102D0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"83a6823e76c11ef1f853772c882ad2f84a6d8b84","datavalue":{"value":{"entity-type":"item","numeric-id":3292904,"id":"Q3292904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$C7261B88-069E-4F0A-B078-037E8039276A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc58fb48063b63f2c168fecda121eb4a00ae957e","datavalue":{"value":{"entity-type":"item","numeric-id":2548174,"id":"Q2548174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$E4AD994D-CD87-4904-85F9-FF4F1962350E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eab863414ffd9a32eeb4561cd8d8533d61ccaabe","datavalue":{"value":{"entity-type":"item","numeric-id":5683718,"id":"Q5683718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$01786BFF-EE6F-4100-B3E5-4075AE104489","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cbb0886b17933b25b5f7256954a7df33d8681db","datavalue":{"value":{"entity-type":"item","numeric-id":1239000,"id":"Q1239000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$7264C41F-18F4-4519-B3A9-CC24F1778D9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce1615f1ba07dd34eb39a6170b8cdad8c1989872","datavalue":{"value":{"entity-type":"item","numeric-id":3292017,"id":"Q3292017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$781A0C64-6036-4B44-B56F-23B587B170DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a4296617abf48730e248717b8067412bc703696","datavalue":{"value":{"entity-type":"item","numeric-id":3727407,"id":"Q3727407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$F7E96E27-23F1-444A-9B08-8666A87D274A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$DCDBA921-A108-4354-80AC-74323637D074","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2e551e57e8d9990938c53781c2eeb2d81106cdc","datavalue":{"value":{"entity-type":"item","numeric-id":5518372,"id":"Q5518372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$8C001324-E49A-4EF9-A69F-94435875722D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6cdeca5dafd1429b6543e0edea3652acb9b31971","datavalue":{"value":{"entity-type":"item","numeric-id":1081314,"id":"Q1081314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$16A45BB6-075B-4C89-AF99-EE0FCA74295D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c154058ac910a307c577639e1aff64db21d8f14c","datavalue":{"value":{"entity-type":"item","numeric-id":1082085,"id":"Q1082085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$9684DAB3-9B69-4625-9D6B-BB8D209DD91A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18a065f9b3036080619d00e2559f06d0382bfdcc","datavalue":{"value":{"entity-type":"item","numeric-id":1820586,"id":"Q1820586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$84B50701-FC47-48CF-A851-DB01D1303B7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dfd37957908f3e0c2267c98e8890f0bc23466819","datavalue":{"value":{"entity-type":"item","numeric-id":1115634,"id":"Q1115634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$8CF7B5B0-E7EA-4ED8-88E4-0F591258F702","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e869522a9cfb25fcb5d1eba98b8a6ada9919a2d6","datavalue":{"value":{"entity-type":"item","numeric-id":2532394,"id":"Q2532394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$AD0AF1FC-5B6A-429F-8D7C-1871CC6C429B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5af7139c65837eb8115c64cb4d4e1bbefc86dded","datavalue":{"value":{"entity-type":"item","numeric-id":4198075,"id":"Q4198075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$FFC5FE6F-A223-408C-8498-1948F9EEE864","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$269A7248-47E9-4891-85C1-2894C78AD5C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6926e920f34ad943bbe1de8ce4a6882fa67a950c","datavalue":{"value":{"entity-type":"item","numeric-id":5596812,"id":"Q5596812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$E4D02C64-54E7-4777-990F-9520EC8DE017","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"968ed2bb9673d23fe5adc9089490f47820735d88","datavalue":{"value":{"entity-type":"item","numeric-id":5607230,"id":"Q5607230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$902E7BC0-0DBD-4FC6-B3EA-0616DDCEB799","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0751213ac1721d4b7bcbd9ddb031d0ca4971a705","datavalue":{"value":{"entity-type":"item","numeric-id":1145502,"id":"Q1145502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$FAE52499-985F-4793-A11A-6EB9882B72AB","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":"Q579948$2199AE65-8859-474A-A0B4-2AB9CBCDE947","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa5bee5357a250d05fef165e66d176475085e3ad","datavalue":{"value":{"entity-type":"item","numeric-id":5180413,"id":"Q5180413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$32BA0394-E736-4634-9BA9-612205EC01E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59a71ee27fc06ad3b0b4b92d7dad58a5649789e7","datavalue":{"value":{"entity-type":"item","numeric-id":4158497,"id":"Q4158497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$FA043B4C-342F-4BD5-BC5D-F78E4DFA5F58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12ea32d3564501ddd74ef94d6b05e5727de3a8dd","datavalue":{"value":{"entity-type":"item","numeric-id":1104095,"id":"Q1104095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$69AB88DD-ADE3-4C0D-A714-79E646DAB049","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79e03cd8581db3f1a993a90df4b9b3924df0ec8d","datavalue":{"value":{"entity-type":"item","numeric-id":5528645,"id":"Q5528645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q579948$BD99CE30-0576-4935-8374-0C872A40954B","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"98e86e8179aa5aa5c0fbc577e1958dbb58382f64","datavalue":{"value":"journals/jcss/DahlhausW86","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q579948$C73CE232-E866-4184-ABB8-E19041F3A919","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9076098b5e07f1817d7bdec4f56c65cb57accd01","datavalue":{"value":{"entity-type":"item","numeric-id":3727407,"id":"Q3727407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29d3d1ae6877a333cc4f58d32463a6138da7cd5d","datavalue":{"value":{"amount":"+0.9492196440696716","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":"Q579948$79AB0DE4-9DB3-492D-B285-9530ECA880DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05f79761642a4b6c773efb93d250e3d0a645e6ba","datavalue":{"value":{"entity-type":"item","numeric-id":5204308,"id":"Q5204308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"891662559a955fdd457b691c3dd3dda17643c0f6","datavalue":{"value":{"amount":"+0.8636260628700256","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":"Q579948$0CEC1E73-79A0-4AB7-B1C8-57957F63DAEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3beb3b95133486297f3688707644b61c9e88053f","datavalue":{"value":{"entity-type":"item","numeric-id":3210903,"id":"Q3210903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"557bff83b5f742666cbd6950bcaa77f56b73ab28","datavalue":{"value":{"amount":"+0.8437442183494568","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":"Q579948$07012564-6FBB-4547-9C3C-1DD95D9C0BB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff3771d3d01d1f8a2c8707b9b81c0e3233cac6f1","datavalue":{"value":{"entity-type":"item","numeric-id":2882390,"id":"Q2882390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55d523d9b10ae66fdfc4c42bdc34f737b70d4145","datavalue":{"value":{"amount":"+0.8175210952758789","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":"Q579948$E6B099A1-867A-4C60-A268-E4C1B8EFE1C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ee2fe93c8d4f6f1bd773737938fb6a65664713e","datavalue":{"value":{"entity-type":"item","numeric-id":4259982,"id":"Q4259982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27bb6f9c4bdf0971685349f0f52494aef6f040e6","datavalue":{"value":{"amount":"+0.7456542253494263","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":"Q579948$8AADDC75-71DE-4184-AE0C-A1FFEEB3B5D1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Membership for growing context-sensitive grammars is polynomial","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Membership_for_growing_context-sensitive_grammars_is_polynomial"}}}}}