{"entities":{"Q2009646":{"pageid":2020388,"ns":120,"title":"Item:Q2009646","lastrevid":57666465,"modified":"2026-03-31T20:32:35Z","type":"item","id":"Q2009646","labels":{"en":{"language":"en","value":"A trichotomy for regular simple path queries on graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7138703"}},"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":"Q2009646$A0CAAFEB-B721-478E-B887-9BBC42FB7298","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"01262c601a24427bdb11547d753d86d4d58041b3","datavalue":{"value":{"text":"A trichotomy for regular simple path queries on graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2009646$E9F4DCEB-29AC-45BF-B582-3DD3772DE6A3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"542631813008609ced9db42fe790a2b6fc5d628f","datavalue":{"value":"1436.68131","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2009646$39C49795-B945-4CE6-A6CD-9AAC692FBE83","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7ce204d731bf12e4303d0af7ec42e262a211d391","datavalue":{"value":{"entity-type":"item","numeric-id":510621,"id":"Q510621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$E8A52CA1-1E5C-4CD0-9117-F3ACD0B84261","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b242fe5b87c79e0efff9468a66e7f7b87f5a7565","datavalue":{"value":{"entity-type":"item","numeric-id":204993,"id":"Q204993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$E670ABA9-17EB-47F0-B6B5-6BCCC8B861A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d299956f6001e85b9d48235e908ddbc8bc26ad35","datavalue":{"value":{"entity-type":"item","numeric-id":462477,"id":"Q462477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$37645F45-36E0-46C9-916B-A8BAC28E9C24","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$08509554-96C5-49BE-952A-4A801F2D932B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7f761c2195f3c85e8ba1c4b44d40c14b3e4a30e0","datavalue":{"value":{"time":"+2019-11-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2009646$47EE434E-1B37-4E65-9FDA-ABD5593A3CE0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"eb6afd5ee1cdc1532c6b3864f21deceda6bf3b81","datavalue":{"value":"https://arxiv.org/abs/1212.6857","type":"string"},"datatype":"url"},"type":"statement","id":"Q2009646$78DE09EC-2255-4D28-880E-CF1AB5C6A7A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"5b2832607864805f65145f43e5a4c123214bbf3e","datavalue":{"value":"https://hal.inria.fr/hal-02435355/file/jcss19%20%281%29.pdf","type":"string"},"datatype":"url"},"type":"statement","id":"Q2009646$D6A14FDC-5837-4B61-9200-FCF536A87C92","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2009646$EDEF3289-0F45-4FC8-B3A6-824BC2F4993B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2009646$96A94C0B-4DCB-41C1-9515-53A77B4B9F8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ca84c0a1de3e8c9074706ad5adbc0b1d28c30279","datavalue":{"value":"68Q27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2009646$51223FE8-A607-488B-9AE5-EF0FA1AEA963","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2009646$FD47A2E8-C3B3-4665-8DFA-E291B039A0A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2009646$2F03DC5D-5033-4BCB-8895-93E4470AF811","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c39485469387afa166b3522d3dbed5a2aea2cf27","datavalue":{"value":"7138703","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2009646$4D27016B-B6C1-44DE-99B4-7C1ABAC63CC3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3e2c5cdbb9bf737c4fa7ac78971f831677d8a1d","datavalue":{"value":"graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2009646$28B226FF-16D2-46DD-910E-121B977A3AF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce8b7fa4386a7eae0843f067e8a3b1db74b8463b","datavalue":{"value":"regular simple paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q2009646$A8EB80D6-DB78-467C-9C53-F5CEBAF9DF9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2009646$C0194BF8-A460-40AB-AF44-7D76D7159886","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7142d39c3323636bd7cc377526eabf4365b5d436","datavalue":{"value":"regular languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q2009646$46508AAC-7E42-4C69-98E5-DBF2D6C361D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae07fe120276ee4c21c2b056394433e1dd18622","datavalue":{"value":"automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q2009646$B4B4829D-EAB7-4CB8-BB48-E0C41196AAA9","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":"Q2009646$2BF659C8-B0A9-45B9-9BD1-6852EA9F87CA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5095421fe833850fc5033048e4ef0f677a40de68","datavalue":{"value":"W4390689069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2009646$889AA33B-C640-4EC9-B7B8-73A2BE876B3E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"42451d9b2f091244b010a7dc1fc6a0f53a57abc4","datavalue":{"value":{"entity-type":"item","numeric-id":4369883,"id":"Q4369883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$AD046D4E-BF97-4F16-A52D-B068F6BE8A86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dae83de450da28599420d61279e9fde2d78ab413","datavalue":{"value":{"entity-type":"item","numeric-id":4302836,"id":"Q4302836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$A7EBC7F3-1C9A-483A-8A22-0B66F85D97EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"044bfd14bd8a71efd8a31e830f9b50bafcd53681","datavalue":{"value":{"entity-type":"item","numeric-id":4507373,"id":"Q4507373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$856F72C4-159A-4024-935C-82E9070BAAD5","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":"Q2009646$E5705D7E-83D2-4E9B-84CD-1F4047C1E9E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80c767919e94a3332b8d198174b1921d5e4026fe","datavalue":{"value":{"entity-type":"item","numeric-id":3821586,"id":"Q3821586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$44AED1BF-74B3-45D3-9B61-045DAAE99757","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df698818c0dd57be3b2281fd72be32288a321373","datavalue":{"value":{"entity-type":"item","numeric-id":4227581,"id":"Q4227581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$784C3D9A-CFD8-4515-93F3-6AD85A43FB44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12600cb24649ba9815ffcfab5b752a2fd38d0d39","datavalue":{"value":{"entity-type":"item","numeric-id":1850539,"id":"Q1850539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$56E08A84-0D0F-41A4-84B7-195738E8C48B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df14fe4c93c519deb312ec21007edf4c3f593b3c","datavalue":{"value":{"entity-type":"item","numeric-id":3345793,"id":"Q3345793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$05291E93-6C31-4609-A06F-A2C30E98B4BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"311eedc10240175b9db47fa47521f3dc6c7c9539","datavalue":{"value":{"entity-type":"item","numeric-id":2943554,"id":"Q2943554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$91CAA804-B9CB-4B97-982E-85478EA4C974","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1dca9ca6e2fed48a55af897a277d534c91cda414","datavalue":{"value":{"entity-type":"item","numeric-id":3305367,"id":"Q3305367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$3114AD45-F9C3-41B2-9DAE-31A538CA58B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0fcf02119bbc2a5aef6da48d353740c8b394536","datavalue":{"value":{"entity-type":"item","numeric-id":4862795,"id":"Q4862795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$ADDADD33-788D-49D7-889C-C23F99CF2562","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9b0c7c4723e1470d6efa8c58ca7ecf7ab770390","datavalue":{"value":{"entity-type":"item","numeric-id":4943840,"id":"Q4943840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$04921C32-7950-4FAD-B1C9-92CF58F0AF03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f9d7f84a9821b89780e21ad996d0e60b6838c16","datavalue":{"value":{"entity-type":"item","numeric-id":4485193,"id":"Q4485193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$9D949893-ED1C-465B-9A09-94B6D36BF212","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$28A2D3A9-0226-4195-AF7C-CE5865D285A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e23bd51a5e1a4df4224fe69471a24cd640168e7","datavalue":{"value":{"entity-type":"item","numeric-id":5540449,"id":"Q5540449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$F83BD2A3-40E1-471E-BB20-0330CF23EDA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"398ef8bc27e00efd8312d46a33efaa0333728c17","datavalue":{"value":{"entity-type":"item","numeric-id":1892832,"id":"Q1892832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$B1D0B135-3329-4E00-94C9-081474A8DEF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8194b210616a81519a29e9c197fab619e01f1c6","datavalue":{"value":{"entity-type":"item","numeric-id":1062759,"id":"Q1062759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$C720B34A-58F9-43AD-AE53-7CCBB15C09D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5201c5307b958e6ccdf0d91cd8283163e96fc273","datavalue":{"value":{"entity-type":"item","numeric-id":4305357,"id":"Q4305357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$2E248E77-320E-4097-AF35-B72164157093","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98554b277242125c67fbb359aa4c54ca22c25d4c","datavalue":{"value":{"entity-type":"item","numeric-id":5339335,"id":"Q5339335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$3920162E-7DD6-431A-B5DF-F54112AC1022","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"284716d56418c087f1054a4ced5e6a48e6de9043","datavalue":{"value":{"entity-type":"item","numeric-id":2270086,"id":"Q2270086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$47CE541E-FF98-44AB-ACC8-1BFAC97DBC4C","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"f598b3444c055189e25d1a559eefe7948da79166","datavalue":{"value":"Q127214244","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2009646$26E7E748-CA9D-4FC5-9185-4E9CF5C957E8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"595bb7a1e1c4592624c2ba5e3535251662b00799","datavalue":{"value":"10.1016/J.JCSS.2019.08.006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2009646$DB96BC10-0105-48C2-9573-BF895A4CB767","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb93ebf77ec410c5da21927a9491593b0002eb7f","datavalue":{"value":{"entity-type":"item","numeric-id":4862795,"id":"Q4862795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54ca7b9c5ddaf73b1ce25a27b166ea6ad4587eb9","datavalue":{"value":{"amount":"+0.8180457353591919","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":"Q2009646$86878BDC-E405-457E-8774-1AAE0637823B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fa17c1ab543792cd440096fdce31bb3c3db0537","datavalue":{"value":{"entity-type":"item","numeric-id":3305367,"id":"Q3305367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7bce3d1247f199603dd43c65a7358e306e59c881","datavalue":{"value":{"amount":"+0.8057475090026855","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":"Q2009646$81D5D8DE-03C7-4C70-8F10-20BFF682AA94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55a963524cd014a0fd827bddcdf945b637ae9a2f","datavalue":{"value":{"entity-type":"item","numeric-id":5054859,"id":"Q5054859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f81b077f6dc80af61d1980d1e9c1c64e98104b92","datavalue":{"value":{"amount":"+0.8025357127189636","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":"Q2009646$E76B623F-E76C-4C03-BA31-AB7DD609E155","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"013da327d775d619b37eae211f607c85f8651028","datavalue":{"value":{"entity-type":"item","numeric-id":4808694,"id":"Q4808694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac9c07719d1cd5068cf701998b7fa4f49bcb9e73","datavalue":{"value":{"amount":"+0.7820330262184143","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":"Q2009646$65D1EE0E-B32B-4824-AA42-259534332F23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4d575b5ed888ba7cc948c248fd2648ada24969a","datavalue":{"value":{"entity-type":"item","numeric-id":2179353,"id":"Q2179353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b810dcc2adc10a317f943231e387651029c367a","datavalue":{"value":{"amount":"+0.7691810727119446","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":"Q2009646$E2DD6350-9414-40E2-89DE-55DEC2187886","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2009646$BC9C1C1B-B03B-4B0E-ACD0-AC07F700ABB8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2009646","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2009646"}}}}}