{"entities":{"Q2520717":{"pageid":2531460,"ns":120,"title":"Item:Q2520717","lastrevid":52700738,"modified":"2026-01-23T07:32:07Z","type":"item","id":"Q2520717","labels":{"en":{"language":"en","value":"Embedding ordered sets into distributive lattices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6664958"}},"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":"Q2520717$7BAC093B-7484-471B-B62D-834794D6B477","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4342aaf56320b04fa0e898caeb05fdd4ff470107","datavalue":{"value":{"text":"Embedding ordered sets into distributive lattices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2520717$93268421-DCA2-4D40-BA0C-DB64E10287E0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6d4f15d43cc11a5aa0f7ea1266f5612a7dde2a57","datavalue":{"value":"1357.06002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2520717$443D9BFC-7677-49CB-B60D-1D3B755AC379","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"91b6b698483070eb9571d7e886ea35f2e2f3c341","datavalue":{"value":{"entity-type":"item","numeric-id":1826929,"id":"Q1826929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2520717$A1E99A15-BBA9-4338-BE56-1F6632250935","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e2599ed8061d57585b4363072a1afceea2452436","datavalue":{"value":{"entity-type":"item","numeric-id":172073,"id":"Q172073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2520717$572F196E-F0AC-430E-B932-C61CA5F1BDD3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"81dc7daf8e9d74fc43b1651d3815e34e62e970ab","datavalue":{"value":{"time":"+2016-12-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2520717$91CEA8A3-AC65-4C8F-AF0A-805200F83360","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dcc83bfe16305b0ef15073676ed35cfcc3f96111","datavalue":{"value":"In this paper, the author investigates the decision problem:  DistPO: Given a finite ordered set, is it embeddable into a distributive lattice with preservation of existing meets and joins?  The main result of the paper is that DistPO is NP-complete. The NP-hardness is achieved by a polynomial reduction to the 3SAT decision problem to DistPO and membership in NP is proved by presenting a suitable NP-algorithm. The author also shows that the results above extend to the bounded case, i.e., to the decision problem:  BoundedDistPO: Given a finite bounded ordered set, is it embeddable into a bounded distributive lattice with preservation of existing meets and joins?  The requirement that all existing finite meets and joins are preserved could be weakened so that only joins of sets up to size \\(k\\) and meets of sets up to size \\(p\\) are preserved where \\(k, l\\geq 2\\). The author shows that NP-completeness holds in the case \\(k\\geq 3\\) and \\(l\\geq 2\\). The case \\(k=l=2\\) is left open.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2520717$D298A365-3E09-4697-B375-545F4FBB59EF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ce5b74470053f031a57488d42a2b289573daad5a","datavalue":{"value":"06D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2520717$6B73B219-F236-4B1F-9775-FD433669AD8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2520717$C7F71E8D-0DEF-4748-941F-D44A2CAF95BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2520717$F0DB8551-DF9E-4688-AB87-83051E3E9CE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2520717$23509F38-B83C-450E-8643-55C9FA92A9DE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b4610a231bff94df1788437848cafdf5114a2403","datavalue":{"value":"6664958","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2520717$B77C4194-A040-4349-904E-CE5BFB193E04","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8b4012ccbdab023048a01bfc8f94bd23553d1d4","datavalue":{"value":"ordered set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2520717$C0624731-C533-401D-89DC-9DA185688CF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5579ddf023a56f4856a8ee584af99380d23fb1f8","datavalue":{"value":"distributive lattice","type":"string"},"datatype":"string"},"type":"statement","id":"Q2520717$B19F713E-30AB-49F8-9C7E-00B95B0F435A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2520717$0676A0F0-7060-4647-A268-1E4BA89C40F5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4f825707c2076b8a425a834771e1fad6bc90e750","datavalue":{"value":{"entity-type":"item","numeric-id":186040,"id":"Q186040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2520717$6249A3EF-0351-4BF6-AC59-21AD5EF19E37","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":"Q2520717$A199BA62-AF80-40A0-89DE-814F7AF4AA92","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"510ebbf57c022952125eb9b7611dc629ebc0b7a0","datavalue":{"value":"https://doi.org/10.1007/s11083-015-9376-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q2520717$A84FD96F-DC56-4448-B769-620BF8596626","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a3c397341dbf8e0c2af4880faf3fea7d19aa194f","datavalue":{"value":"W2246642039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2520717$1E6CF6CA-41A8-40B7-B452-A2BA61A4E4B6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"24142b57c6761c6b6a80a739e070b0f32af01f14","datavalue":{"value":{"entity-type":"item","numeric-id":3116854,"id":"Q3116854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2520717$5D91473B-C82C-4100-AC43-02BE2D981DD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ba4f5628b9493b3dc4e9b69bc068cb07ae68c2f","datavalue":{"value":{"entity-type":"item","numeric-id":4530231,"id":"Q4530231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2520717$60C9C092-82F4-4445-917B-BBEF5B114439","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eee68ae9c8981e1dda6abeeaac4a13264b59ce87","datavalue":{"value":{"entity-type":"item","numeric-id":466925,"id":"Q466925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2520717$F2A24EAC-C3C9-47A4-B6AA-A6D004D18C62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e51d4f52c58fd9bcc34b0f848e68839b303b42c9","datavalue":{"value":{"entity-type":"item","numeric-id":4525257,"id":"Q4525257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2520717$CFD3D64A-605F-49B0-AFCE-E12FCD88B607","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55caca84b95088f5e871ceb44d25fd97d2ac8afd","datavalue":{"value":{"entity-type":"item","numeric-id":1379157,"id":"Q1379157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2520717$F6FFCD80-88A6-4F87-A616-5F9C15E01E20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ce973fb94bb1c7e17bec7452c2f943e4f111d46","datavalue":{"value":{"entity-type":"item","numeric-id":5768906,"id":"Q5768906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2520717$F856A084-BE0C-4FC0-BFC2-4FC3334023DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aec2f93588785d0bce2756b9344ef62959c52e3f","datavalue":{"value":{"entity-type":"item","numeric-id":603886,"id":"Q603886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2520717$1FB0D4C7-3A52-4FD5-B40D-2101B9011C2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1937d1d0cc70b12648d00e23473402179d6b243c","datavalue":{"value":{"entity-type":"item","numeric-id":1611302,"id":"Q1611302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2520717$471A0986-ABEC-400F-8111-5F05920A3797","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea79bf0b8998e59df4aaa18289fafa2fe7f354f5","datavalue":{"value":{"entity-type":"item","numeric-id":3392275,"id":"Q3392275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2520717$E12A9F7D-A917-4630-9592-643955C3CC26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fcfd47c3fe9e0f097b76c7c78a15869fd96ffd9","datavalue":{"value":{"entity-type":"item","numeric-id":4004146,"id":"Q4004146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2520717$9653222A-D7A1-4CE5-ACA7-DE9FFBAD86AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14f316bda1db96a4382c7a9143b182e390b18612","datavalue":{"value":{"entity-type":"item","numeric-id":3663349,"id":"Q3663349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2520717$90810383-35E1-453A-B21C-B532751DDC09","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"af76cdc2192433c34b4f61056629379b84a4ffd1","datavalue":{"value":"10.1007/S11083-015-9376-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2520717$4FD9AB14-8D28-4365-ADA2-0204C4D4A29B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9575467aac5dc6a0062eadf5b2f2d637805d9bbc","datavalue":{"value":{"entity-type":"item","numeric-id":5499652,"id":"Q5499652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52863dfd2944222496630c9623fae9e1f8e092b6","datavalue":{"value":{"amount":"+0.8067368865013123","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":"Q2520717$11C4EE54-47AA-47D8-89F2-029B50183678","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"636d9728edcbd4aa5b38165738eaf2bcc7e1105d","datavalue":{"value":{"entity-type":"item","numeric-id":4560229,"id":"Q4560229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc2084e1a95f4714c639c24dd81b411b4df58c79","datavalue":{"value":{"amount":"+0.755492091178894","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":"Q2520717$DF90D6CB-4BA6-4517-A413-6D41C9A506D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c6a8420ee35a7390c2d6c6beab166ed2948a63b","datavalue":{"value":{"entity-type":"item","numeric-id":1375909,"id":"Q1375909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bfe467785707d1297ba8787c223b23eb74ad8338","datavalue":{"value":{"amount":"+0.7323938608169556","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":"Q2520717$C0070C0B-3C64-4966-9078-FAEBF7D704F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"044e4709e0d9d8fa1369cf6aa801df22d4d787ba","datavalue":{"value":{"entity-type":"item","numeric-id":3778007,"id":"Q3778007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36c4b72e864fcd9822a2bc9e6e52b7a3f995654e","datavalue":{"value":{"amount":"+0.7271358370780945","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":"Q2520717$68AFCB06-33B5-40BA-A5E6-255C0C7F71A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd24d5d34b4a5ef60aaa10bdb6efe1367228ee81","datavalue":{"value":{"entity-type":"item","numeric-id":1354627,"id":"Q1354627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42b6f0a177a0c69abcb70889edccb20d5c7c8528","datavalue":{"value":{"amount":"+0.7241396307945251","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":"Q2520717$95E50314-75F0-44F3-AD0B-1014C8E71018","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2520717","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2520717"}}}}}