{"entities":{"Q5874424":{"pageid":7903975,"ns":120,"title":"Item:Q5874424","lastrevid":41647227,"modified":"2025-05-06T18:03:22Z","type":"item","id":"Q5874424","labels":{"en":{"language":"en","value":"The complexity of the Approximate Multiple Pattern Matching Problem for random strings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7651063"}},"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":"Q5874424$7538ADBA-2399-4B19-8C2F-5019F38548E8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"52f99931570b7c4604e735c160b9da3b251102e6","datavalue":{"value":{"entity-type":"item","numeric-id":322272,"id":"Q322272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5874424$71595193-B987-4EBC-9EE8-AC3981980BDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec4ecc250db8a2664e743e455cbacbba69fae79c","datavalue":{"value":{"entity-type":"item","numeric-id":431184,"id":"Q431184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5874424$F8E09693-F705-4729-8E82-0FBDCF132BB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0b91203c68e3451b4eff6295035ff58f17818cb2","datavalue":{"value":{"entity-type":"item","numeric-id":1028036,"id":"Q1028036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5874424$F149482D-CA4D-46A9-AAF3-47B2DE4A5E30","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1cf2c00ad9755e29029658ecb4f6eb01aba3c5f5","datavalue":{"value":{"time":"+2023-02-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5874424$F7B00944-D218-4D8F-8152-FE9B47CEAA34","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5874424$B1731B16-F30E-4712-8E1C-C0B026B1220E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b7b39305f7411bc08d075cae153e7c788100e955","datavalue":{"value":"7651063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5874424$BF31C570-ED6D-4F4F-815D-17FB430474BB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7b098843eb94d55c3d331079f92f661c10c787b","datavalue":{"value":"subcritical graph class","type":"string"},"datatype":"string"},"type":"statement","id":"Q5874424$F473D85F-54B3-4296-87C5-CD492452A45C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"090977cea00f7982df37586f4d263187534feb76","datavalue":{"value":"block statistic","type":"string"},"datatype":"string"},"type":"statement","id":"Q5874424$2FFFEFEA-07EF-4C6C-A4BB-9FDD91FD65AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f02718db51cc63404439297b3bce9ac104b98d01","datavalue":{"value":"number of blocks","type":"string"},"datatype":"string"},"type":"statement","id":"Q5874424$C6A9DC73-186A-4CCE-AD53-07C0B5CC648D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b021e17aa5d68733d2f8043d2f5b350f63304dc","datavalue":{"value":"number of edges","type":"string"},"datatype":"string"},"type":"statement","id":"Q5874424$D519FFD4-3C51-46DB-B21F-80ECBC8B8D4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1f1861aeda754af488fa73a95b33262d80f4ef5","datavalue":{"value":"number of spanning trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q5874424$963A25FD-F990-4CEB-896C-DA8DF4929DCE","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":"Q5874424$49C9C78D-681C-4787-939C-1EAC49F96ECF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"28ee99be1c1287ecc61404b7023e484ded5f4cfa","datavalue":{"value":"https://hal.science/hal-03214615","type":"string"},"datatype":"url"},"type":"statement","id":"Q5874424$99B176E7-15D1-4DB5-975B-C9A2E7B99460","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"10e72f43cf95d4bdc94141798eb059aad39cc7e8","datavalue":{"value":"W3038001709","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5874424$0D5202D1-3C1E-4A14-8564-657E9C9E29C6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b1d6a235468f7d191a26ca6ea8b0987a88619bca","datavalue":{"value":{"text":"The complexity of the Approximate Multiple Pattern Matching Problem for random strings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5874424$C6C8FADF-04D9-4BE5-AF04-D36494BC0217","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bab3f9776ed555277d2d1d39f02a9f0444c8b476","datavalue":{"value":"10.4230/LIPICS.AOFA.2020.24","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5874424$233E71A8-0FE8-46F9-8FB3-8D0C28A4CEBB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e57cc3e9d89c6cf08ef9eea302dbb5ffced8c0c","datavalue":{"value":{"entity-type":"item","numeric-id":4597604,"id":"Q4597604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76de769a0a2e48c498afcf4090e2ddd419fb4ab6","datavalue":{"value":{"amount":"+0.9284791","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5874424$99496BAA-6E2E-47BC-8409-E1A129CBB23A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a158692bfd451809a5826a47743442aefcf1f0c","datavalue":{"value":{"entity-type":"item","numeric-id":739054,"id":"Q739054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d83878deda104f6a39f0419cc5bc0f72ca07a0fb","datavalue":{"value":{"amount":"+0.8901121","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5874424$1511B0B3-8F34-42C6-871D-A9785CFD26F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"614de29c6a45c181cd6caa4ddf7f374840c62060","datavalue":{"value":{"entity-type":"item","numeric-id":3176612,"id":"Q3176612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"451b35706b418e84d1a67c57761e6ae66af07694","datavalue":{"value":{"amount":"+0.8840277","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5874424$01BEFD37-6E4C-47E6-8DC2-6FCA90511BB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6861ad6fb06142f10efff642c119c09b8c67ab6d","datavalue":{"value":{"entity-type":"item","numeric-id":4623134,"id":"Q4623134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"453f42e893725dc8004c448922a415cc3d90b6b0","datavalue":{"value":{"amount":"+0.88397896","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5874424$0C0CEF12-5604-4704-A234-0E81ECAD38C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e23ec747b95a2f1030577ee87319c29f58a65163","datavalue":{"value":{"entity-type":"item","numeric-id":4632499,"id":"Q4632499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33133fa0d134e750417779311d6812c2c486c184","datavalue":{"value":{"amount":"+0.8801455","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5874424$596B0FF0-3C1C-4F7B-B900-10DF0DCB68AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"592f94a4522eed38480ca8ae343611c64e6d84e4","datavalue":{"value":{"entity-type":"item","numeric-id":5219330,"id":"Q5219330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a075852af7abd1775ecb8c5140d3c3fa83f43b3c","datavalue":{"value":{"amount":"+0.8794665","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5874424$4E91E3C9-15E2-4636-BE5E-934394D346F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15209ce781eb1164b912a1c2a270a797065a40ba","datavalue":{"value":{"entity-type":"item","numeric-id":2256135,"id":"Q2256135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f182768e4214e94ceda11d0f8c37ea1f654d5c9b","datavalue":{"value":{"amount":"+0.87877244","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5874424$F0312EB0-31A4-45D3-BDFA-29061B6E5BEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b7498e0b0a350a27736967b949db71dc7b69901","datavalue":{"value":{"entity-type":"item","numeric-id":4291207,"id":"Q4291207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"162d5319e32dcdbf2d78666e85fcc00d7f959a7b","datavalue":{"value":{"amount":"+0.8765898","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5874424$BDF4FA29-EA5C-4803-9B71-B0528C5E1B2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f927b6b546cb97c59620e6421e66bae897873938","datavalue":{"value":{"entity-type":"item","numeric-id":6176774,"id":"Q6176774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27fdbb9c2d6a31e7c066415744768506bb235457","datavalue":{"value":{"amount":"+0.8762453","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5874424$C16BF031-38D8-423B-8E08-C142BB279A32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbafadedc78299dec21e4727885413e0e34db39b","datavalue":{"value":{"entity-type":"item","numeric-id":5436975,"id":"Q5436975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16c49d98570b98c645c9468405fa164868c61127","datavalue":{"value":{"amount":"+0.8739766","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5874424$622A253B-1400-44B9-897F-3552BF3AA243","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5874424","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5874424"}}}}}