{"entities":{"Q5859630":{"pageid":7889181,"ns":120,"title":"Item:Q5859630","lastrevid":53974622,"modified":"2026-01-26T00:41:13Z","type":"item","id":"Q5859630","labels":{"en":{"language":"en","value":"On the membership problem of permutation grammars -- a direct proof of NP-completeness"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7334809"}},"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":"Q5859630$9AA6EE0D-D3FD-4614-BC3A-4C0B74F81F65","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9120cb3cb0c0fbf2d044b26c3584625cea1ad766","datavalue":{"value":{"text":"On the Membership Problem of Permutation Grammars \u2014 A Direct Proof of NP-Completeness","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5859630$B2B71E8C-F99D-4EE5-8189-7E12D2827514","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c950c603b12a028650145263198f02b360edc20b","datavalue":{"value":"1458.68109","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5859630$19353BBE-290E-4CC2-AB43-AFC73AF2CAB1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6aa3ae5d4608f36b3589c9bf8672871c1b73db53","datavalue":{"value":"10.1142/S0129054120500227","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5859630$34A29D33-764B-4455-9BEA-A6EFA95A4132","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a7ae5ba1a1ad8f7b8209780a8077ef09c939a57c","datavalue":{"value":{"entity-type":"item","numeric-id":439937,"id":"Q439937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5859630$573B53C6-6033-4CFB-9F3F-E37229E3B647","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"47adaa7123c6f3744cf7fa8eab088d52b4982295","datavalue":{"value":{"entity-type":"item","numeric-id":2703009,"id":"Q2703009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5859630$7ED116C9-8232-4A83-9126-9507950C5A44","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a9a75ecc8651000ecb4ff9566ba97a118200de08","datavalue":{"value":{"time":"+2021-04-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5859630$1F5AD31D-7488-4D0F-84B3-BE9EFB35D174","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5859630$268C0048-06F6-4C06-9B5B-717E9C83C841","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5859630$AF520D40-8805-42AA-AEE8-E538E252268E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5859630$9B2A2FA3-2C8B-4076-8654-C7853922C4A7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"229d74cff454017be332263f0e2ec198b97661f7","datavalue":{"value":"7334809","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5859630$D703952E-D75A-457E-858E-A03F3523C740","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b30b88dd7d8d4d3a542dd1829bf3206a53951e76","datavalue":{"value":"formal languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q5859630$150B8A09-500B-45CF-ADF5-3975324AF261","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"efd670f6409581101d00cc745c7ce48b72edc7f7","datavalue":{"value":"beyond context-freeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q5859630$689FED1F-851C-450A-89D8-A1AC877BC505","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a0c7bb0ecf32b900347362cf461885c46f832ca","datavalue":{"value":"parsing","type":"string"},"datatype":"string"},"type":"statement","id":"Q5859630$EC389CB7-B1DD-4F85-96E8-47BC9E022B25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5859630$3AF5DA84-6BCB-4EE8-B2CD-119BE761BEAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q5859630$AC881E7B-714A-45C4-8091-57C4F6BB375F","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":"Q5859630$D2E37CD5-C050-492C-9B48-D5C71C271B3A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d6efed081156db1a2c5a763ba542488263bea69","datavalue":{"value":{"entity-type":"item","numeric-id":388107,"id":"Q388107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5859630$76D4E3A0-7127-407E-9809-B6A52CC7666F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"138cce00a9725f330453af8fe64208cd8e005cf6","datavalue":{"value":{"entity-type":"item","numeric-id":579948,"id":"Q579948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5859630$8295FAA3-7083-49FE-8D3D-D40F984294D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4f4bef7d78ccba3680de2d8de5a780f92459b6f","datavalue":{"value":{"entity-type":"item","numeric-id":4040325,"id":"Q4040325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5859630$27762317-732A-46FB-AA09-E38ACE2147B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be8a53fe134b0b70830e68dfe27608ac9174a22f","datavalue":{"value":{"entity-type":"item","numeric-id":4140712,"id":"Q4140712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5859630$70E0AFA1-8B44-4FCB-9EC1-B40BAAA45595","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":"Q5859630$C4C04268-55CF-48C9-AD29-7EC2B57FF42A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee2472e37ebb1d7e71d5d604c88ff41b191f2bac","datavalue":{"value":{"entity-type":"item","numeric-id":5416738,"id":"Q5416738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5859630$40BC0702-0AD6-42FA-8B34-F7539158BD55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff23966022d72a3b330af6c39b20ebfcd3a95292","datavalue":{"value":{"entity-type":"item","numeric-id":2947424,"id":"Q2947424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5859630$69F04C40-FDE5-4A21-A5C7-4620A784D732","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6be8b7c7c0697538775b0d64185ee47f6d92e87","datavalue":{"value":{"entity-type":"item","numeric-id":5223617,"id":"Q5223617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5859630$405B910A-4FC9-490C-9E87-4529B44EBE0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3a3b962ee832efaf7c7d62dc9afdf9fed1d9ba3","datavalue":{"value":{"entity-type":"item","numeric-id":1068558,"id":"Q1068558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5859630$DEF7FC6F-BBF8-48D5-9B9D-07DB7CF9BA6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f953d564d9d74b02e68af097b26fcfbf0ec9a818","datavalue":{"value":{"entity-type":"item","numeric-id":5406167,"id":"Q5406167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5859630$8B571ABD-7F06-41B7-9324-0B65CDFE7F9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a4d350bf249db4d1ea83318d4bcfdf084c63b94","datavalue":{"value":{"entity-type":"item","numeric-id":3589634,"id":"Q3589634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5859630$D7BF5E24-54F3-4EAF-9C25-6E2F6AA2C2E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76d8c521d1327fbb45293f787d8e110d34af1c29","datavalue":{"value":{"entity-type":"item","numeric-id":4922680,"id":"Q4922680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5859630$E239B68B-3498-4890-BAC2-A6E5089D53C6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"aa54e853526efb67e9bc48817658475f1773133d","datavalue":{"value":"https://doi.org/10.1142/s0129054120500227","type":"string"},"datatype":"url"},"type":"statement","id":"Q5859630$672A5F66-940D-498B-A7A6-66077887BCAE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"605ea4bc6188cd9b17a88a6318014472e74519c8","datavalue":{"value":"W3038534939","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5859630$B125F71A-01DD-4D45-A965-828ABD962F1B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4eb8b374e354e3e26199b757e14de6913850c14","datavalue":{"value":{"entity-type":"item","numeric-id":2947424,"id":"Q2947424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81b471c06992b295ff0d5465929d681771490e9e","datavalue":{"value":{"amount":"+0.8978402614593506","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":"Q5859630$5ECA0A2F-54FD-45CC-92C0-A35F8DD09A56","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":"82614c4016cab47d15e0de9c43c86f82c5542cd3","datavalue":{"value":{"amount":"+0.7952549457550049","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":"Q5859630$4CA9800C-0243-4851-AB07-0D9383191A33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"75fd197170095d1dcb62df75c6e5612d74938383","datavalue":{"value":{"entity-type":"item","numeric-id":2685503,"id":"Q2685503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5184e0573e06ef0455bceb20f60fb5473cfe8628","datavalue":{"value":{"amount":"+0.791644811630249","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":"Q5859630$60060DBB-10C8-445D-855E-3AF16B746C64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5227472dfb56b5d8b220fbe3e76d6a72322b661c","datavalue":{"value":{"entity-type":"item","numeric-id":4922680,"id":"Q4922680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"797253fb990dca9a6d5a0214833f623dae5fbae5","datavalue":{"value":{"amount":"+0.7890688180923462","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":"Q5859630$F441B5B9-DB98-4D4E-BD2E-83BDA2D28047","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9089c5736d4e96fc10e8f61df0f1df93078326e6","datavalue":{"value":{"entity-type":"item","numeric-id":5416738,"id":"Q5416738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9086d417ec226f35438135daeefd88e22e9a3feb","datavalue":{"value":{"amount":"+0.7721061110496521","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":"Q5859630$A616271A-D864-4005-8B95-7A2C7D6499DD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5859630","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5859630"}}}}}