{"entities":{"Q507598":{"pageid":509365,"ns":120,"title":"Item:Q507598","lastrevid":62400012,"modified":"2026-04-11T05:49:34Z","type":"item","id":"Q507598","labels":{"en":{"language":"en","value":"Separating sets of strings by finding matching patterns is almost always hard"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6680984"}},"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":"Q507598$BC7D65F3-08D0-4D13-B6F6-3D9CDF7FFCD8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6841eb35a8fb904a486b5856b96840ba9d0ae61f","datavalue":{"value":{"text":"Separating sets of strings by finding matching patterns is almost always hard","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q507598$B276B88C-51BC-4AFA-9F33-3194459D6604","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b6e10a652ed81f4cdf7a79c91c6d69274a54889b","datavalue":{"value":"1356.68101","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q507598$FF9939B0-E9B7-4326-9793-C9F75A4A88F2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fa1ce206998641885f9e972a2a0fbe3d209931ee","datavalue":{"value":{"entity-type":"item","numeric-id":301941,"id":"Q301941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$22B2265F-919A-484F-AE7B-512006799427","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"616a3e9d8641ef3d5bbb0a72f3fe2c7061fe1a76","datavalue":{"value":{"entity-type":"item","numeric-id":414865,"id":"Q414865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$310B627F-DD04-49AD-AFC7-1A8196253965","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f873c2e007625a14c9aceb5234e31e754e9db113","datavalue":{"value":{"entity-type":"item","numeric-id":191620,"id":"Q191620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$55BF818F-B216-4274-BD9C-F3954B2AF9B2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$810305BB-AA1E-4963-8C75-C1B7B4F0112F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"69224595960101be6ec21574e4c403135d7942f5","datavalue":{"value":{"time":"+2017-02-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q507598$86869C54-BB65-429E-815F-8CF46E654D96","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1bc7f627ed33a8adcdc2600381a8dfefc6e93991","datavalue":{"value":"https://arxiv.org/abs/1604.03243","type":"string"},"datatype":"url"},"type":"statement","id":"Q507598$DF4D2253-775D-484E-B19D-DDB803B7B271","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q507598$8EC025BB-4D5C-476D-A326-361DBF348E9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q507598$4AD5E9F5-A40F-478F-ACFD-14ACE4DADEBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q507598$7FF09A6B-0F99-447A-A5ED-475A94768D6D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cbbb97c097c85a227e2d46929843173a5fbc59d2","datavalue":{"value":"6680984","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q507598$E919F852-5EDF-4174-B1DD-9A0234348C93","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a891e2134b26c90044efe84a049b7a823eba172","datavalue":{"value":"pattern identification","type":"string"},"datatype":"string"},"type":"statement","id":"Q507598$88D0328F-A45D-4DB4-B87E-7041F6084F26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee63604621b6fd9d90b10f19ccdd9c167a66b1b6","datavalue":{"value":"parameterized complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q507598$8DCCB15C-C03E-4777-83FB-EE26779E24D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q507598$C8BFBB59-6DF2-4DB5-94AA-DFA2B2C5C647","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":"Q507598$45FAECBE-EE49-483B-B5C8-D0F1C46BBA77","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"09447e446286de204c9c4e20923b5b0a7e5e0fad","datavalue":{"value":"W2963448547","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q507598$4E25321C-5975-4C90-B90F-29DE0E2BF30F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6422ef138be173ca7bc1ed6caff5e742dc3bc0f8","datavalue":{"value":{"entity-type":"item","numeric-id":1149795,"id":"Q1149795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$A52A2455-8DAB-4EA7-AC46-8CAFC89F04C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"695659329ba6a827f01cc683284bdda9a8476d2e","datavalue":{"value":{"entity-type":"item","numeric-id":3993359,"id":"Q3993359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$1BE10EE2-9580-422D-AEDA-FA5EF8131CD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d1f3a7a7c36fffb751c05631cde06478f21b18b","datavalue":{"value":{"entity-type":"item","numeric-id":2346970,"id":"Q2346970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$831409DF-6ADA-4437-8164-F8CDA2644E97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3882f0d92b8b77cc690ee6835f81e8ff543e1c82","datavalue":{"value":{"entity-type":"item","numeric-id":5405946,"id":"Q5405946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$FCDE5044-5271-40D1-9710-F25830826B73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc002ae351e0fb16dafde5b7cbfa48e45487156f","datavalue":{"value":{"entity-type":"item","numeric-id":4967170,"id":"Q4967170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$9BEB8F0C-2F4C-4035-A2CB-41D5F8F95BEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d4aa30a2020b4a555f00e2774888642333f5f9b","datavalue":{"value":{"entity-type":"item","numeric-id":1430285,"id":"Q1430285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$97B2B43B-56CD-4DEE-AE5A-0D328AC032D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"355274a283369f04f9f02212b1d819a3f129798d","datavalue":{"value":{"entity-type":"item","numeric-id":5294024,"id":"Q5294024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$E9157397-9027-4FD5-82A5-240BEBAB363D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0917a207f3af8a20adf245537a26e87b5cfa63cd","datavalue":{"value":{"entity-type":"item","numeric-id":2843289,"id":"Q2843289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$3AC0C6AC-FA33-4E09-A2E1-0FCB718177F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f2c3a8543183f3e4a94b8ead76c8f2780175602","datavalue":{"value":{"entity-type":"item","numeric-id":1877698,"id":"Q1877698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$09B772AD-2D7A-4A37-B0DF-E4CDEAED8028","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70eef5fc9af1d141ea9e67b51db233bbd0b03388","datavalue":{"value":{"entity-type":"item","numeric-id":4737204,"id":"Q4737204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$F310E4AF-6BC7-4914-BE73-B438C0EC7FF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05ccbb66f253e8aabe9f774ba9414f12634b864d","datavalue":{"value":{"entity-type":"item","numeric-id":383833,"id":"Q383833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$E208A7A9-E879-405C-AF9A-5E2BBA492DFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3d5352adf00d3ba6c6280f75a2382719f6f5022","datavalue":{"value":{"entity-type":"item","numeric-id":4217593,"id":"Q4217593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$DD1B5B3C-E380-48E4-87C6-1D9BC263DB13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74f5d5c8e9cc46169ad3d1f7cd96a6b011221a39","datavalue":{"value":{"entity-type":"item","numeric-id":4736845,"id":"Q4736845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$0DA1AC5F-99FB-4198-93FA-67B3D6438560","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":"Q507598$24FA3425-16C3-4ED9-9D6C-EECD8CAA532D","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":"Q507598$824986F5-3C5C-4A66-A308-45C587DE0743","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a98a2b34d2336504a1a8fb6673bf39299c75adb9","datavalue":{"value":{"entity-type":"item","numeric-id":2432546,"id":"Q2432546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$93C9EDE2-A1BF-43C2-BA85-526F2C4A33C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4ae85b74cd18c4f4082ce00bf4740968f96a532","datavalue":{"value":{"entity-type":"item","numeric-id":1424248,"id":"Q1424248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$8B59B087-916B-4353-82CB-52DB0F84497C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f4f6417af3313b2a4f1959b9dee0bb7940ea475","datavalue":{"value":{"entity-type":"item","numeric-id":4526964,"id":"Q4526964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$D9D07B88-C561-4A96-B678-3EA0AF932065","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"666dea21bc7d084a0e46ab44b30e54220fa91dc0","datavalue":{"value":{"entity-type":"item","numeric-id":495996,"id":"Q495996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$D5430935-FC48-4F44-BCB7-8337EB6C1049","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a567a0bd5149009c58baa277d371437f0fed769","datavalue":{"value":{"entity-type":"item","numeric-id":1213733,"id":"Q1213733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$F77B0D7D-E438-4AFD-866A-26C5333267FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa48d821ceda254ea2f53d88639c3b6b92bcaf10","datavalue":{"value":{"entity-type":"item","numeric-id":4013526,"id":"Q4013526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$957AF22B-C67E-445A-A2B4-FFD28922349A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"02901919df95c5cfee893a7b08627856779e1e47","datavalue":{"value":{"entity-type":"item","numeric-id":3196639,"id":"Q3196639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$EFAE3656-E856-4F7D-97B4-1552A594BB15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18d5cfedfe66a3b5d774d6c8fbd31b828323bdab","datavalue":{"value":{"entity-type":"item","numeric-id":4527015,"id":"Q4527015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q507598$B431C979-2A2E-4B0A-978A-CE6113F43E46","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7f875af5f88c0ad8e602c43434d3d2d55fbeb686","datavalue":{"value":"10.1016/J.TCS.2016.12.018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q507598$1C41B0E6-8287-4999-875F-ACCC2102271B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e75500767f50a237d8079ab17c6baba9c674ac2","datavalue":{"value":{"entity-type":"item","numeric-id":3044513,"id":"Q3044513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"866616cf8c7df72ef622366d16d121d12977ccfb","datavalue":{"value":{"amount":"+0.7845180630683899","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":"Q507598$0BA51966-B436-4C36-A223-504D24209024","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2842392c3270c10989a91b0f958f2c057114cd88","datavalue":{"value":{"entity-type":"item","numeric-id":1870541,"id":"Q1870541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f653c2290af3f4c5ccbdf929c7f9eec985bad686","datavalue":{"value":{"amount":"+0.7646608352661133","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":"Q507598$96DD3E6D-7067-49C2-9EC1-7F987D08A61C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10f6c3294c241293967f5982656cb62e83688206","datavalue":{"value":{"entity-type":"item","numeric-id":858110,"id":"Q858110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"adbd05fb1b1a2e36fde1e607cdfe652e52e714ed","datavalue":{"value":{"amount":"+0.7345693111419678","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":"Q507598$15E86210-4BBB-4821-8DB5-956D97264E4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca0f95c72fc0fe05284165a97e180a9faaee0330","datavalue":{"value":{"entity-type":"item","numeric-id":1427861,"id":"Q1427861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8c507548ddb13906e58462a5ce3be0e56909e6c","datavalue":{"value":{"amount":"+0.7340773344039917","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":"Q507598$331ADE65-1F6B-45F2-A88E-5A9D832F47CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33ef1431f2b1a6d80ad02bc79b58e6d0e04da6db","datavalue":{"value":{"entity-type":"item","numeric-id":2432546,"id":"Q2432546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cb71da7b3bd4e5b0a278962df48247129827d25","datavalue":{"value":{"amount":"+0.7311097979545593","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":"Q507598$4A4E0963-5538-455C-B844-59A0F2DD76DC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Separating sets of strings by finding matching patterns is almost always hard","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Separating_sets_of_strings_by_finding_matching_patterns_is_almost_always_hard"}}}}}