{"entities":{"Q1736791":{"pageid":1747532,"ns":120,"title":"Item:Q1736791","lastrevid":56699388,"modified":"2026-03-18T23:51:08Z","type":"item","id":"Q1736791","labels":{"en":{"language":"en","value":"Uniform \\textit{vs.} nonuniform membership for mildly context-sensitive languages: a brief survey"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042341"}},"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":"Q1736791$8C7B0403-DCFD-4C43-9C4E-6FBEDC5C0C8F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"70facb030cc643d22c1fc84d578e4eeadab6b921","datavalue":{"value":{"text":"Uniform \\textit{vs.} nonuniform membership for mildly context-sensitive languages: a brief survey","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736791$D7F6DC89-04E6-4821-82B8-FD8BB0A74EB2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f59e0cbeefab4e14ba36b510bcd3d5bb4cb5af5c","datavalue":{"value":"1461.68095","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736791$6047819E-980D-45B2-9F67-57C94057BBA3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"096420e2486caf88e63ac4f00185baf32ff3dd87","datavalue":{"value":{"entity-type":"item","numeric-id":300255,"id":"Q300255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736791$B6ACBF76-545D-4890-8CC7-55A8E06CA55D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2cf597ce3cadae8c1ff364393a3717f8e981adfd","datavalue":{"value":{"entity-type":"item","numeric-id":388106,"id":"Q388106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736791$20EAA9FD-B6A4-423A-9EC4-B48CD037E9F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"15ce70cafed9dd3ca08840af67e52c39d4f2257c","datavalue":{"value":{"entity-type":"item","numeric-id":1736790,"id":"Q1736790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736791$FDB57FF3-B4AB-454C-AF31-8D42335C0FD5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736791$FA73EE8A-9FE3-4A36-96B6-7474745FE139","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-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":"Q1736791$C80ED328-3F1A-4C98-BF10-68979B07E005","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a0c1a4bbc781bae8793b8c56ac94a11a2bd2f07a","datavalue":{"value":"Summary: Parsing for mildly context-sensitive language formalisms is an important area within natural language processing. While the complexity of the parsing problem for some such formalisms is known to be polynomial, this is not the case for all of them. This article presents a series of results regarding the complexity of parsing for linear context-free rewriting systems and deterministic tree-walking transducers. We discuss the difference between uniform and nonuniform complexity measures and how parameterized complexity theory can be used to investigate how different aspects of the formalisms influence how hard the parsing problem is. The main results we survey are all hardness results and indicate that parsing is hard even for relatively small values of parameters such as rank and fan-out in a rewriting system.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736791$312AFDF4-0525-4758-A134-6B0F864A469E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736791$EC22D87D-88DB-4F98-B220-8F9D83EB346A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736791$2BBB75FB-15E1-43BB-B4E3-F7E137C5C816","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ca84c0a1de3e8c9074706ad5adbc0b1d28c30279","datavalue":{"value":"68Q27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736791$0C302697-B306-463F-B2CD-745CCE91358A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736791$6C653696-9CA9-4AF5-98E9-E37B26751FC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ae62b6ae8284bad4753b7ed23b6f2503aa5e4b9f","datavalue":{"value":"68T50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736791$1785AFDB-5403-4F08-AADC-C3BF4CC80230","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7bfc63905ac48e3aba2d066e43c1757455d24596","datavalue":{"value":"7042341","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736791$009734A6-A070-4982-BE7B-C50FED15D1C8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8ecd171594a6e066f0d18b78d6631aab161a7eb","datavalue":{"value":"mildly context-sensitive languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736791$DB5110A3-11F7-4325-A764-DB37EBB2C61B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a0c7bb0ecf32b900347362cf461885c46f832ca","datavalue":{"value":"parsing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736791$B042B124-7E7E-44F5-A541-EA6056523EA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b30b88dd7d8d4d3a542dd1829bf3206a53951e76","datavalue":{"value":"formal languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736791$44248BFB-2E07-4F5B-B648-29C149668B1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee63604621b6fd9d90b10f19ccdd9c167a66b1b6","datavalue":{"value":"parameterized complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736791$1B88C0DB-7972-4002-B3C7-049E407CD08B","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":"Q1736791$9FA467DB-825D-4FA7-8A4C-5C994C912FFE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"eb5f7e045082f2ab0d92d73b9bca83ab23b46bb2","datavalue":{"value":"https://doi.org/10.3390/a9020032","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736791$A1593E40-9F08-45CB-A06E-A4ED46D82EE9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b8c74d3fd34b7ded3027806f90252ea00f86e186","datavalue":{"value":"W2350714487","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736791$0E2786BE-E844-421D-86D7-D10D20931701","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e97002deaa32bce9238411fd6668f6b28c627864","datavalue":{"value":{"entity-type":"item","numeric-id":5536272,"id":"Q5536272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736791$8379522F-B927-4E60-B4D5-300A2F90A53C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736791$BAD901A3-E7F4-4886-B32E-5FF1704CB1EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90f5019b9268ce75998bc450e26ba8b1acf55f43","datavalue":{"value":{"entity-type":"item","numeric-id":4311636,"id":"Q4311636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736791$53B88829-0A24-48E7-AA51-E3751496D545","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"626ebcfcef8b7e2eb36d8de7f315ce6589dd2a5f","datavalue":{"value":{"entity-type":"item","numeric-id":1177161,"id":"Q1177161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736791$5EF76954-BC5F-457F-BD3B-99FBCC986DE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74790942b2e6b5ed9810f28f0f37dd82301f55c3","datavalue":{"value":{"entity-type":"item","numeric-id":5656401,"id":"Q5656401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736791$CB711A20-03D9-428B-8B62-88D10FBC8979","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70fd8d7ceb6d85a50859109efa1c5b5b69b35fd5","datavalue":{"value":{"entity-type":"item","numeric-id":1176107,"id":"Q1176107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736791$8A7807B3-5747-4CEE-A6E7-7BF867A3964B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"980a6530e26b95b1ccced773b6d57739ceae5608","datavalue":{"value":{"entity-type":"item","numeric-id":1136239,"id":"Q1136239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736791$DECBFCD4-A135-46E8-A9EA-CA6D2AFD3DB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"975471caf2c85a39486ecbc3724696ed27a8b8cf","datavalue":{"value":{"entity-type":"item","numeric-id":1267708,"id":"Q1267708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736791$19099F54-8D5F-4836-A85B-8B6CB2D8C5D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e020ad692b6149cabbf5eb602292edf891b1db8a","datavalue":{"value":{"entity-type":"item","numeric-id":4923554,"id":"Q4923554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736791$9E27C787-7FB2-437A-88C6-F0D2C95584D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20255a8237134d4b6e87b409de5384e1758f8215","datavalue":{"value":{"entity-type":"item","numeric-id":2785998,"id":"Q2785998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736791$DCBC5AB5-19C3-4728-B8D9-2CD7B1FBB4CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"454dee464435a4f81ba19fac05704ee1c50116c6","datavalue":{"value":{"entity-type":"item","numeric-id":3540091,"id":"Q3540091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736791$E766643D-C296-40BD-B047-81BDADAB49EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae35b42269b65df7a1c59338bf97c0ea301c5c81","datavalue":{"value":{"entity-type":"item","numeric-id":2488567,"id":"Q2488567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736791$4171CB3F-D621-4144-A0B8-04A7F7B1E6AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6675e97a5567d6ffd99627c3e438b8eb3c13dc93","datavalue":{"value":{"entity-type":"item","numeric-id":983734,"id":"Q983734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736791$728A97A6-8C5C-4DF4-A6D3-5E57F0C32CBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1034267be85d6529562b88e2b1c8a57404367a39","datavalue":{"value":{"entity-type":"item","numeric-id":4599177,"id":"Q4599177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736791$C165C0A1-6335-414B-9231-F512C2479F7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae78a63a69a74848d5aeaa89bef60027b93de2fb","datavalue":{"value":{"entity-type":"item","numeric-id":1892937,"id":"Q1892937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736791$4F9F0395-8607-44A3-B40B-4A03665789AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87f001f0cbad53dd7b0f7605c3f62967f6287c69","datavalue":{"value":{"entity-type":"item","numeric-id":4281539,"id":"Q4281539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736791$A5B65056-8318-4B70-A647-27E273E2CC3C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"35ced024b5758f641bc32a48cf02f260f9270829","datavalue":{"value":"10.3390/A9020032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736791$32A7FD56-7738-4B6E-BC70-2D0A6715F70D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"956111cfa3922a412d1f9447a3d89bbe52f028ac","datavalue":{"value":{"entity-type":"item","numeric-id":4599177,"id":"Q4599177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78266eebb01ff49fb8340c51e141f7abed54c48f","datavalue":{"value":{"amount":"+0.781103253364563","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":"Q1736791$846283AC-7DE4-43B6-B2BA-A40E8ECB39C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e19b096656ab68eef43bfa4b1477e80c410d2223","datavalue":{"value":{"entity-type":"item","numeric-id":4662828,"id":"Q4662828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b12483bd1bb76eb14fa76edf7726de8ce74a812","datavalue":{"value":{"amount":"+0.764585554599762","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":"Q1736791$2E5A757C-633C-4EBA-A9EF-3FFEA337DE1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1848558364636026b6bb09b5d181d5f218bc7b53","datavalue":{"value":{"entity-type":"item","numeric-id":5376328,"id":"Q5376328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44f089405a3de0c550f97a7cd573e51e2d15c510","datavalue":{"value":{"amount":"+0.7609370350837708","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":"Q1736791$0A2379DE-D150-40A8-B126-FD0E0DE25917","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26c5f9e546015df2c73881e65b74702ce4039dce","datavalue":{"value":{"entity-type":"item","numeric-id":1736827,"id":"Q1736827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb861de4a2fe47f25408af3f90c16b4174afaa74","datavalue":{"value":{"amount":"+0.7490177750587463","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":"Q1736791$DD61EEAD-9BA1-49CF-94C7-A05970AB2D57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4c0835b6875e53628d1eef7256a2bf973cdc179","datavalue":{"value":{"entity-type":"item","numeric-id":4355685,"id":"Q4355685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de290889d1b8db82aea2d94691b285166e813f3c","datavalue":{"value":{"amount":"+0.7323080897331238","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":"Q1736791$92EEC0C4-ED23-4062-9B2A-D90FDD0F776C","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736791$FFD3C8F7-76DE-4FAD-B5CD-2962607E3DF6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1736791","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1736791"}}}}}