{"entities":{"Q2853188":{"pageid":2863908,"ns":120,"title":"Item:Q2853188","lastrevid":51846401,"modified":"2026-01-20T08:15:25Z","type":"item","id":"Q2853188","labels":{"en":{"language":"en","value":"Polymorphisms of small digraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6217144"}},"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":"Q2853188$348F6BCB-F157-42A0-871B-24F2A7EA4C56","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b170b951556a9a7175d356c360162d4c065acb61","datavalue":{"value":"1289.05446","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2853188$A678E206-D2CA-44EB-BA60-2CC9F216D724","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"612ceaee2e01226be6266b6156f9145d1fae19d0","datavalue":{"value":{"entity-type":"item","numeric-id":494632,"id":"Q494632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2853188$697900FB-FEAB-4911-BE40-58C31B036D87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f5ff4cf6f989469eee73caf1aa9de9fad60ad8c5","datavalue":{"value":{"entity-type":"item","numeric-id":397856,"id":"Q397856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2853188$E9D1A706-79C1-4CDE-A89E-8899489EB056","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e1b5304373ae38bc09a24211814db713fe903318","datavalue":{"value":{"time":"+2013-10-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2853188$43F2F6DF-9B68-4AD0-BD51-D06C16E334D4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2853188$A69EF441-A70F-4825-97E2-419B6D73AF94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2853188$8797BFA9-BA23-44CB-AE00-17C0F2AC0C4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"92a555e3a541c9f0978c54443cf0a96e2a43c4df","datavalue":{"value":"08A02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2853188$CC404292-BC14-44B8-83EA-B1F9DCB8C868","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2853188$72D85F25-9036-4BEA-AE17-2FC36628A502","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"20bb5571a1bc4300de51d23c463eb631840cb343","datavalue":{"value":"08A70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2853188$D5598F44-4D63-47A4-94ED-EF5B7DAE70BE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"21c790499174b59d7b990d6f117b828840c5dc1f","datavalue":{"value":"6217144","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2853188$CD9580C0-8F18-43FD-8A28-F64EC21FE250","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"40e665e07277b013cc533c5e93264dc338081f96","datavalue":{"value":"polymorphisms of digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2853188$A2BF9E52-8495-46CA-91A0-4C6B1BB9EDF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a348f9efcaabdd35d491583f05dde8d8e0eb673","datavalue":{"value":"constraint satisfaction problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2853188$7B4DE7D7-D20A-47B0-91E2-F578782AB245","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":"Q2853188$7ABDFC89-D30B-49B9-AC3F-9703C06F693D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"492e5ae8a9b4b9e2f5b2071d7257877e14e6fd8b","datavalue":{"value":{"text":"Polymorphisms of small digraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2853188$172E7C2F-E545-43D3-AE33-FD1E5EC35F36","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"56456d7321f276f72950c7e586874f0e37ab84a0","datavalue":{"value":{"entity-type":"item","numeric-id":4985272,"id":"Q4985272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2853188$1064E66F-CAA1-4542-B3BA-7CD49934236F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1f50721ffec989e48d8faa0872bdb8d26cda7bec","datavalue":{"value":"Constraint satisfaction problems (CSP) form a rich class of algorithmic problems with applications in many areas of computer science. As abstract problems, CSPs are homomorphism problems for relational structures.NEWLINENEWLINE The authors provide a report on results obtained by computer testing the existence of various types of polymorphisms for small digraphs, since a digraph can be seen as a relational structure with one binary relation. The authors choose to check for polymorphisms important in CSP such as Mal'tsev polymorphism, near-unanimity polymorphisms (up to arity 5), edge polymorphisms (up to arity 5), semilattice polymorphism, and so on. The existence of these polymorphisms is checked for all non-isomorphic digraphs with up to 5 vertices, as well as for some randomly chosen digraphs on 6, 7 and 8 vertices.NEWLINENEWLINE The authors also find a digraph on six vertices such that the complexity of its retraction problem is unknown with current techniques and show that this is the smallest such example.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2853188$5CC23783-615A-4982-BA16-1A85D1C40D19","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c08f63fdb5b5316380cae4341c8bf7ef7e685d38","datavalue":{"value":{"entity-type":"item","numeric-id":5298320,"id":"Q5298320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5582b2feb024e4dbd413aef8cbbdeba5c44bfd2f","datavalue":{"value":{"amount":"+0.8416088819503784","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":"Q2853188$C0C4C0A4-EBAA-4F53-B596-A222FCBB9A0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b19f20b8d135ec262cf04e6adcab604172b21b88","datavalue":{"value":{"entity-type":"item","numeric-id":3460423,"id":"Q3460423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45c5060a79692bb6683c85766ce46e51f11c1204","datavalue":{"value":{"amount":"+0.7984898686408997","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":"Q2853188$E07A4575-B98E-4830-BCF4-840E08277404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b34a42074bc0788f0e2e10ed398d7b64830bb0df","datavalue":{"value":{"entity-type":"item","numeric-id":4973888,"id":"Q4973888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c381cc3be4c7215b9750deb0ae582f1f9e7c96b","datavalue":{"value":{"amount":"+0.7898061871528625","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":"Q2853188$34081AFC-DA76-454B-A91C-C159415CB981","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25b6458f6ba74343f8675191ab38a392fb9568b4","datavalue":{"value":{"entity-type":"item","numeric-id":5415454,"id":"Q5415454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be0d14b5b54f8e57f9f8b17595f9d49e68840ada","datavalue":{"value":{"amount":"+0.7724906802177429","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":"Q2853188$2E65B63F-1D7A-49A0-9628-EB893C8ED0D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4a3f7023ab7e6418298faa55e123e99cb898c51","datavalue":{"value":{"entity-type":"item","numeric-id":4993603,"id":"Q4993603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41d74a0a852b6d0d67c392cc175cddfd396b5f87","datavalue":{"value":{"amount":"+0.7638176083564758","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":"Q2853188$3C5AC66F-0CC1-4C8F-A91C-456D84C39F7B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2853188","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2853188"}}}}}