{"entities":{"Q2893312":{"pageid":2904037,"ns":120,"title":"Item:Q2893312","lastrevid":51494645,"modified":"2026-01-18T12:23:37Z","type":"item","id":"Q2893312","labels":{"en":{"language":"en","value":"The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6048142"}},"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":"Q2893312$406E403D-518F-4FC4-B4E3-754D3358EE88","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6681b639023f9a048ec8624c6c373573a597ee01","datavalue":{"value":"1279.68171","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2893312$4F06CEAC-D35C-4B3C-8D57-B461CA6DE498","rank":"normal"}],"P16":[{"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":"Q2893312$BD36C864-8FBD-4F40-9BD9-2991676C0E1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d5f30f869988791147fdb3c4896ec3e1a83e8a48","datavalue":{"value":{"entity-type":"item","numeric-id":553301,"id":"Q553301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2893312$B7B1E6FC-8DEE-4C4E-ADFF-F1B5107E7C54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"acbe3fcdaa2e72f3bce067779bfee150bff0b503","datavalue":{"value":{"entity-type":"item","numeric-id":405317,"id":"Q405317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2893312$B5EBE5D2-4850-4139-B0FA-C5AC2F2104BA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f318557c66fd6d7ed4e56cf07066ee7032aec4a0","datavalue":{"value":{"time":"+2012-06-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2893312$32E9177A-2F3B-4B00-B744-AAE95EC48FBD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ed9802a640a1f710b3036c287a0a39660e178777","datavalue":{"value":"http://iospress.metapress.com/content/g461u042w2750v4g/fulltext.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q2893312$16757C49-ED16-4C4A-AABF-88449956E3A4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2893312$1557DF53-829A-4E94-B45E-D3C46C1EC959","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2893312$61A6664A-B229-43FE-8B4B-AF3A9B89021D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8f40b66b8ac3e2ee3a33738e8ef7ff3daa71d6a0","datavalue":{"value":"6048142","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2893312$2714AADD-262B-443D-AEE3-80C61A124FDC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9947e86031adb4cdbb200f2a9c08a77817d41858","datavalue":{"value":"prefix","type":"string"},"datatype":"string"},"type":"statement","id":"Q2893312$88B68043-9C3C-472D-99FE-6C9B45163F8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50dd6a4b3d569a6a654eac5603bc845df311df82","datavalue":{"value":"suffix","type":"string"},"datatype":"string"},"type":"statement","id":"Q2893312$E1781EBE-881A-4C7D-88A4-A7725E8BC12B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5905a10d668a74111ed97fdc58213f68080b9194","datavalue":{"value":"factor","type":"string"},"datatype":"string"},"type":"statement","id":"Q2893312$DF2E2A1C-BC92-40A9-90E4-1DF5024F742F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9129eb98e7541d9df8d83fe7856664ab823ed593","datavalue":{"value":"subword","type":"string"},"datatype":"string"},"type":"statement","id":"Q2893312$668274F4-C887-43A3-B533-67CAD6E9E57D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dce83b1053073b7f40b03d648c2f3334bcbff5cc","datavalue":{"value":"universality","type":"string"},"datatype":"string"},"type":"statement","id":"Q2893312$504F47E5-77A6-4881-A874-B0865E9D693C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a05cfd9da536bc8387292ab9359d3f7e9902a360","datavalue":{"value":"PSPACE-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q2893312$8565FB81-30EE-477C-9480-54EB809341BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ab14670fd645ceec284d741b18aecb5f5131180","datavalue":{"value":"decision problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2893312$A53A8D31-E725-4AA7-B0A9-94B8CCA2BDA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a862f016acc1e519aa7b6644887bfca464692961","datavalue":{"value":"polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q2893312$88BECD8C-7C09-4649-A266-4CFF285AB083","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"960b46905dadcd2a654332a1828c13a843d2c1e4","datavalue":{"value":"synchronizing word","type":"string"},"datatype":"string"},"type":"statement","id":"Q2893312$252D33FF-6E05-4A24-8077-2EFEB0BFBE26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b65caa91765e2cd64df517de4dd625db242407b8","datavalue":{"value":"synchronizing automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q2893312$6768ACA0-7BDA-495F-ACC0-40697F35871B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"927a37e60189b9a05de8fc61fa6e6687927ca21b","datavalue":{"value":"Restivo's conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q2893312$0F71F473-5340-4238-9264-923C2560FB77","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":"Q2893312$7B26735D-528C-466D-86C8-3D5C9E9E56FC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fdc39e6ee89a7440d6777da8a4cfbc85494f39e7","datavalue":{"value":{"text":"The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2893312$2809B7BC-04C5-4511-9191-9C5AF3627C15","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1529db038bde6a8aed76ac5e8432917aee1a9200","datavalue":{"value":{"entity-type":"item","numeric-id":2803574,"id":"Q2803574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2893312$6160F846-E0F7-4589-92AF-B3F145CD20C8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ccb472c63491933022c330fc0bbcd7c8644950c0","datavalue":{"value":{"entity-type":"item","numeric-id":443735,"id":"Q443735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8de825e5cd10440532c275f8427544aedc55fba2","datavalue":{"value":{"amount":"+0.7801427841186523","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":"Q2893312$1D5C052F-DDD9-433B-B56B-DD213BDDC8CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47c8f322a0f733bcf9d15a5f58a6f52d813ded29","datavalue":{"value":{"entity-type":"item","numeric-id":5200084,"id":"Q5200084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cd18595a1d4c3a8b10b81974cb7db5ff591e621","datavalue":{"value":{"amount":"+0.7730340361595154","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":"Q2893312$AAC6DEB8-702D-49EF-82F1-553ED72C57B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3ef39f2bb17b65e6e29094aad497736d55bc2db","datavalue":{"value":{"entity-type":"item","numeric-id":5250874,"id":"Q5250874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e1580fa9516da0d3a2f55646ba7375f07c02983","datavalue":{"value":{"amount":"+0.7651793956756592","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":"Q2893312$D948E4C3-4F7E-4F8F-9490-0CC7B438B01B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65918b5a41d836b3bda473212c1c80d6441a7a91","datavalue":{"value":{"entity-type":"item","numeric-id":3086930,"id":"Q3086930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07d1ca588a9f80f6ea72e2212fe727c31c4cc8bc","datavalue":{"value":{"amount":"+0.7605166435241699","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":"Q2893312$F0C76B10-78AD-4FC5-AE15-BCBD47297EC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9cdac1f883e481dad2c6ce60d3207fe4513e22a6","datavalue":{"value":{"entity-type":"item","numeric-id":5740416,"id":"Q5740416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3174f99f246c4fe6336b53c0a0ec6f4c98404ffc","datavalue":{"value":{"amount":"+0.7597105503082275","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":"Q2893312$6E4D4A94-37B6-4BE8-86D8-1A42ED53F20E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2893312","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2893312"}}}}}