{"entities":{"Q2904756":{"pageid":2915481,"ns":120,"title":"Item:Q2904756","lastrevid":79695977,"modified":"2026-05-06T14:30:29Z","type":"item","id":"Q2904756","labels":{"en":{"language":"en","value":"Compressed membership for NFA (DFA) with compressed labels is in NP (P)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6070897"}},"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":"Q2904756$A07ECFEF-3735-4E3C-BDB4-5D3B68651B74","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b1201318ce39f1b973cfd3a9b2586d3f9804f2e3","datavalue":{"value":"1245.68126","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2904756$2844C93F-BC16-4839-A337-D95A62638487","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"956ccad67dc502dfc66055868e0a535a76df3b6e","datavalue":{"value":{"entity-type":"item","numeric-id":248925,"id":"Q248925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2904756$CEF0C087-EFB6-488B-A142-A757D7CE21B1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"65565ef421231dd2fa47bb94f379079908ab66d7","datavalue":{"value":{"time":"+2012-08-23T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2904756$E7DA7610-3D68-49BE-8D27-3F390B502939","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"440d34dd3d2f33605ecc8dd744d973629fccc34f","datavalue":{"value":"https://arxiv.org/abs/1110.2318","type":"string"},"datatype":"url"},"type":"statement","id":"Q2904756$5AD02033-BCE9-4180-9AE2-BFB1E504C09B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2904756$19F4E597-5A13-4318-954A-AF9279B4FE14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2904756$371403D7-30B0-45D9-BA71-826D1F26C410","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2904756$9DEDA570-316D-4A84-8366-90ED42B40BB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4264b8bf260e532ba12469970b36fcaf09f85467","datavalue":{"value":"68P30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2904756$D4B46EDA-AD5F-4D53-BCDE-90666E616234","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1a3a1b78b9e2a29e8a9161755c4e69a2be680fb7","datavalue":{"value":"6070897","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2904756$9DB94B87-27C0-4D00-B374-4B82AF63447D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"46caf22bf256e6c13e7402ddbec99e3edaf64c0d","datavalue":{"value":"compressed membership problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2904756$9927407D-31E6-4DDC-A218-F2838B9C43E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"712d7a80a9d269975b3a5f7dce881d5f6c3f2bea","datavalue":{"value":"SLP","type":"string"},"datatype":"string"},"type":"statement","id":"Q2904756$25179CE6-7823-45C9-9859-B0984C0AE3AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8fe1ec072eddb82e8c6723b370c91fea5db0efe","datavalue":{"value":"finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q2904756$A5A5E6D6-F3B2-4B71-8F74-E7FD127372CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3470a0005a473e38cad08cf73f3fb9f04e1b60b0","datavalue":{"value":"algorithms for compressed data","type":"string"},"datatype":"string"},"type":"statement","id":"Q2904756$2C10A068-8CF0-4566-A9B9-DE3AB493275B","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":"Q2904756$0AF1B67D-FF47-44AC-BB7F-F9AF496DAB7E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b9d25ac316b13ba513abdaf7706c0cf5e48e0fc7","datavalue":{"value":"10.4230/LIPICS.STACS.2012.136","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2904756$0D0512B8-0579-4A18-B8AD-7A0F62ECF159","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1e5597223c88a38ef0dfb5057df8ce2f6f367fd5","datavalue":{"value":{"text":"Compressed membership for NFA (DFA) with compressed labels is in NP (P)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2904756$A2CFD5B1-6680-4E48-977A-920D67F71D33","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b826091a7adbb19cacdc92801a42b4c6607ab17a","datavalue":{"value":{"entity-type":"item","numeric-id":2254509,"id":"Q2254509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c29ef72ad9ae18ae81e9ddb8899f1f3f4c76913","datavalue":{"value":{"amount":"+0.9831115007400512","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":"Q2904756$8198AEFD-3491-489C-A05C-17495F4874C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d1da3a9eca32f1990b36a25fe20c2d395082811","datavalue":{"value":{"entity-type":"item","numeric-id":3007633,"id":"Q3007633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7acd35ad992ca780bd4f1f8427c34c3d2a0ea17f","datavalue":{"value":{"amount":"+0.8950666189193726","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":"Q2904756$ED94ADB2-A13B-4C49-9958-2E53B6149255","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17fd67be0a253c91bfae5adfe3471e9a15b3f9f0","datavalue":{"value":{"entity-type":"item","numeric-id":3056281,"id":"Q3056281"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7108c3aec1b4634f671c1b4a7a150f8843858224","datavalue":{"value":{"amount":"+0.8301914930343628","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":"Q2904756$26ADB815-4AC2-4904-A8FF-61E94BA8871F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b9917a52e83780200d26e941ee15b3092854262","datavalue":{"value":{"entity-type":"item","numeric-id":4941166,"id":"Q4941166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"024af51ee28d7581b88f0401836d0eb669b77d4a","datavalue":{"value":{"amount":"+0.8240253329277039","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":"Q2904756$9D57AB40-E79B-413B-9FDE-FE60C0D918F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e313270f7eae7fe515c77fd1e98a61970f0bca0","datavalue":{"value":{"entity-type":"item","numeric-id":4277533,"id":"Q4277533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"024af51ee28d7581b88f0401836d0eb669b77d4a","datavalue":{"value":{"amount":"+0.8240253329277039","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":"Q2904756$BF65F170-1BCC-4C79-A392-A6562D272934","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Compressed membership for NFA (DFA) with compressed labels is in NP (P)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Compressed_membership_for_NFA_(DFA)_with_compressed_labels_is_in_NP_(P)"}}}}}