{"entities":{"Q606993":{"pageid":608769,"ns":120,"title":"Item:Q606993","lastrevid":63045111,"modified":"2026-04-11T10:00:38Z","type":"item","id":"Q606993","labels":{"en":{"language":"en","value":"On the complexity of deciding avoidability of sets of partial words"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5817532"}},"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":"Q606993$8B4BC061-98F8-4765-B5AC-CD6E9A22C0E7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f68d32daea8b37212a8079f489d23b6a465c11ec","datavalue":{"value":{"text":"On the complexity of deciding avoidability of sets of partial words","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q606993$8D5C21C5-F9FF-4F7C-9228-58A26C9B3EAE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1c1920cdacb8b6f83e2e09cc1cf5400e909d14bb","datavalue":{"value":"1208.68164","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q606993$D20A6F31-65CE-4100-A5BA-A5D6141100D6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0d71654d85fe5a0a0339b7e73f3e6e855dd7f251","datavalue":{"value":{"entity-type":"item","numeric-id":606991,"id":"Q606991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q606993$13907137-24E2-4CAA-846F-7E6EBF709725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"93b45e6f35a46f2e2f1fa86a21166fefbadd915c","datavalue":{"value":{"entity-type":"item","numeric-id":591667,"id":"Q591667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q606993$1723B458-B5EA-4BAF-915B-C0651960D671","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ea55bb9091cbea7ec0a34f1fb5dd037eddc5351","datavalue":{"value":{"entity-type":"item","numeric-id":606992,"id":"Q606992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q606993$8AFA0744-BB70-44CC-96CC-A5AA9C101172","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fb8579d08d02888dcfc6c4a0d1e7ad3780689962","datavalue":{"value":{"entity-type":"item","numeric-id":284844,"id":"Q284844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q606993$73C22307-4A84-42C4-95C4-E6140CFA0639","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":"Q606993$5ECDC4EE-1BDE-47DE-B42D-96909E925D9F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b1a8b0b4410e75478f392738ec80b73d0645c344","datavalue":{"value":{"time":"+2010-11-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":"Q606993$E6B0A70F-53E2-4F92-9036-FD3140BCB9A2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q606993$2E5117E2-9AD5-412D-AB39-A645D61EBFCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q606993$B72E578D-01D0-4B4C-9F82-EC6D6761FA94","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1bd29ac3a07ee5e1e7f9d25a93a72c40a8545bba","datavalue":{"value":"5817532","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q606993$BD09126E-9DB2-409A-9AF3-E7C25E18DEBF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q606993$D1255F2B-CF0D-4B0F-94BF-A014F308ABC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8967d0a934eaa6194b5afbe1fbb4e78c8127645d","datavalue":{"value":"combinatorics on words","type":"string"},"datatype":"string"},"type":"statement","id":"Q606993$29B37717-F7EB-4E84-BF08-9F6B1861FDCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"665bb6b521670920ffccf875b8511ad8132838e1","datavalue":{"value":"partial words","type":"string"},"datatype":"string"},"type":"statement","id":"Q606993$9F5B0131-3B3B-40E4-B083-DE769CCA6904","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8718a10fc5200235f7a5ff6090340c216c0cbe3","datavalue":{"value":"unavoidable sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q606993$E8E48AA4-AFBB-4EBD-BEE1-1FC49C409267","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99974e488eefe65e9a359b970a995a9b6d33d8e8","datavalue":{"value":"NP-hard problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q606993$F2CB116F-A5A7-4A26-8C38-D879EF35DBE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f248a4a504a499f931ffd5eabb8da7e87c1fbc32","datavalue":{"value":"de Bruijn graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q606993$D0BBC2AC-0547-475D-8E78-B16C3D85BBEE","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":"Q606993$2AEBC4C3-A07F-4170-B806-D083E7113815","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"38f120ae24bdab04d3f2906666821aa96f47f131","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2010.09.006","type":"string"},"datatype":"url"},"type":"statement","id":"Q606993$EB30DC68-A63E-40BC-9CFF-38F86BB033E3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"aae315ad7e7502c2ae1ae4a48c0449f042648e57","datavalue":{"value":"W2129749965","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q606993$75F89D7D-0C35-404E-A32C-838944CF4132","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e884892508373839ae801c95d241a499a8aaf0a5","datavalue":{"value":{"entity-type":"item","numeric-id":4055184,"id":"Q4055184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q606993$8D4E9E6F-7F56-43D3-9EE3-D4868DCADDD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1d5e92edf5f1cf932cc218da9428822ea79ab86","datavalue":{"value":{"entity-type":"item","numeric-id":3637218,"id":"Q3637218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q606993$EAE19229-55B4-4C11-B4E8-B51B3541F62A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"258bdba76977b3dec81e7e3a5e90f663de66a9f8","datavalue":{"value":{"entity-type":"item","numeric-id":5310364,"id":"Q5310364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q606993$2301C827-3EB5-4677-B8EB-E9303D12078D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82953dad0f697c5abfeae8cd3f750bf5c4608fc1","datavalue":{"value":{"entity-type":"item","numeric-id":733729,"id":"Q733729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q606993$97A17CDB-2F1B-4E76-8B6C-DC7DCEA3B2ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"179ad11066acb9c1a2e4a3d98d88eb4154a23def","datavalue":{"value":{"entity-type":"item","numeric-id":1006080,"id":"Q1006080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q606993$5E754A90-B10E-4FE0-ACDB-232631D2F69A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a61bbd634ba961cd9f67cf22bbddb73fbd7ed2ad","datavalue":{"value":{"entity-type":"item","numeric-id":5692237,"id":"Q5692237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q606993$88DD3D73-3754-4B84-AD74-35C50EF8B96B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe929f01fa86af5ec1780a3fd0d8f9ac3346a63b","datavalue":{"value":{"entity-type":"item","numeric-id":4714446,"id":"Q4714446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q606993$C5B5CFFF-3BB8-452E-911B-0184703C4E00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f355cef83bff81e6cffbc663ee1c89c02d7ebb5","datavalue":{"value":{"entity-type":"item","numeric-id":845893,"id":"Q845893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q606993$20C61736-D6A6-4E97-8493-4CB1EF57469F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2f727b9ae79be8b892e918eb79f12cb2c0e1b40","datavalue":{"value":{"entity-type":"item","numeric-id":598457,"id":"Q598457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q606993$F3443360-2525-42A7-954F-436EF989AA6B","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":"Q606993$FA9B3477-D414-40F7-A842-E6DD9A99527C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a2161f3bae52ff41e38d4f3caa26722526aef57","datavalue":{"value":{"entity-type":"item","numeric-id":3994681,"id":"Q3994681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q606993$B8986AC9-30F4-493C-8CFE-A373540D886A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bac7f1baaa55096d83c73bf345e8308c96e8d9b7","datavalue":{"value":{"entity-type":"item","numeric-id":4255576,"id":"Q4255576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q606993$F21AFEB1-D85D-4908-AFD4-210F9194E752","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q606993$D04C6CC7-6407-451B-A22C-736A5EC58509","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"edf3005b7670eb623d7b5a68242619e9bfdb9fa6","datavalue":{"value":{"entity-type":"item","numeric-id":1078338,"id":"Q1078338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q606993$452569C3-0EA4-40A4-B6B2-C58063F42D47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ab968868a27793512725f9615e172750ff9d631","datavalue":{"value":{"entity-type":"item","numeric-id":4529547,"id":"Q4529547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q606993$DD8EC5FA-6380-47DB-9A49-E0444DE17388","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"967f5a7805fc69b217b1464d7db64ac370f55d4c","datavalue":{"value":{"entity-type":"item","numeric-id":2547222,"id":"Q2547222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q606993$A42C5A34-35FB-4A7A-8170-E94111685B61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"736a1d463d18d2f300e2b9600c3f86eae2986ef8","datavalue":{"value":{"entity-type":"item","numeric-id":2537313,"id":"Q2537313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q606993$5C773207-6284-4D72-B6EC-09CD82E95515","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dd81cb6e038eaaf07bc869b113fd447085e22270","datavalue":{"value":"10.1016/J.TCS.2010.09.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q606993$EBC95235-3747-404B-BF77-3EEC960E1F94","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46df79e7810c6a81b6018398d50e74d69c55edcb","datavalue":{"value":{"entity-type":"item","numeric-id":3637218,"id":"Q3637218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1115d00fb4d06fb1d2e6789870cf9d1479cecc89","datavalue":{"value":{"amount":"+0.9978188276290894","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":"Q606993$7F93C2D3-201B-43C2-8292-7720E0B453C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee040d988a5d2d34a66c0211de7a28adab059c81","datavalue":{"value":{"entity-type":"item","numeric-id":1006080,"id":"Q1006080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e879b4638955d07c624f79ea9ca2a6901e4bfe3","datavalue":{"value":{"amount":"+0.909712016582489","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":"Q606993$93779B3A-D9C4-47BB-9D25-E732D1463E32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"399c39e554eb00a9521f5d19bb6f28619cda50b0","datavalue":{"value":{"entity-type":"item","numeric-id":5016356,"id":"Q5016356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e12798b66107ac499e72743408076c3623df3bad","datavalue":{"value":{"amount":"+0.8497148752212524","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":"Q606993$988F350F-A6AC-4982-BE07-57F8E89F54B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc291f2eda4c8865663d8fbbba7c1f8c18fdf169","datavalue":{"value":{"entity-type":"item","numeric-id":450549,"id":"Q450549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"705a0dd7fa5881abfc0e67afb14cf302d713eb28","datavalue":{"value":{"amount":"+0.8414844870567322","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":"Q606993$4D9B6365-E9BA-4E25-8EDC-00C4EE8C454D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e1ce8e829975cee099ed3bc76d1c3b3da14a382","datavalue":{"value":{"entity-type":"item","numeric-id":4608614,"id":"Q4608614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3ae9253362e1a740e5bedc035e33308aff38529","datavalue":{"value":{"amount":"+0.8129969239234924","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":"Q606993$775D8721-FBF7-4F01-BDE7-19FCC01E6CEA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of deciding avoidability of sets of partial words","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_complexity_of_deciding_avoidability_of_sets_of_partial_words"}}}}}