{"entities":{"Q5936459":{"pageid":8113261,"ns":120,"title":"Item:Q5936459","lastrevid":47630725,"modified":"2026-01-02T06:36:16Z","type":"item","id":"Q5936459","labels":{"en":{"language":"en","value":"Efficient algorithms on distributive lattices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1613398"}},"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":"Q5936459$F7184C6E-B277-4B65-861B-4D639669ACF2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ebeb37b9d7e6b62fb481511a35315815d2990279","datavalue":{"value":{"text":"Efficient algorithms on distributive lattices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5936459$F89E9F20-2C2A-405A-805A-70205EF60134","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c07b05a8d7aa64b828ea252289c4d35cfa19ad0a","datavalue":{"value":"0983.06009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936459$55ECD6C4-E483-4A08-B913-24BEB08760CB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ccd5c39a61298041cc6aa921d9cf9936750a6854","datavalue":{"value":"10.1016/S0166-218X(00)00258-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936459$5A07602F-EDCC-4382-95C2-0FD737B74F8E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a5c8cc91a6365154cae56745f535bf7dd30d2aa3","datavalue":{"value":{"entity-type":"item","numeric-id":187126,"id":"Q187126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936459$151C0A7A-4FEC-4490-A5F0-58BCFEF6F653","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1c36e3055f1cdb90938a8115244dfe4ccfd60c2f","datavalue":{"value":{"entity-type":"item","numeric-id":187127,"id":"Q187127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936459$60CA2681-B20F-4491-A5DC-46D5FF3343BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1814572f6f5cc98a1bdac6b4fecbd84381c8ff3","datavalue":{"value":{"entity-type":"item","numeric-id":187128,"id":"Q187128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936459$8B341F25-9EA7-4C54-9EBA-6EBFBD094D21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"99c543f5e7aa390a02715829bddfee3fa37ecf14","datavalue":{"value":{"entity-type":"item","numeric-id":6074591,"id":"Q6074591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936459$2DF530A1-D52B-4482-9830-BD3F6B7EF374","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936459$FD269831-9A7C-4652-8013-7167A5637A65","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"98a818dd251e9aa1c67eb9fd23225d737b796e1d","datavalue":{"value":{"time":"+2002-01-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5936459$8E58A055-3571-4739-A51C-07389513C144","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d5f0604424a8eeee31bdcc1f682d539d56a01b0c","datavalue":{"value":"This paper continues \\textit{M. Habib} and \\textit{L. Nourine}'s paper ``Tree structure for distributive lattices and its applications'' [Theor. Comput. Sci. 165, No. 2, 391-405 (1996; Zbl 0887.68016)], where a new representation of distributive lattices by an ideal tree was suggested. This paper gives a linear time algorithm that for an ideal tree of a distributive lattice \\(L\\) computes a covering relation of \\(L\\). Further algorithms that for a given poset \\(P\\) compute an ideal tree of the ideal lattice completion of \\(P\\) in \\(O(\\Delta (P)|V|)\\) time and \\(O (|V|)\\) space (\\(\\Delta (P)\\) is the maximum indegree in \\(P\\) and \\(V\\) is the underlying set of the ideal tree of the order lattice completion of \\(P\\)) and a list of all order ideals of \\(P\\) such that each ideal is listed twice and adjacent ideals differ in at most two vertices (so-called combinatorial Grey code \\((1,2)\\)) are presented. The latter algorithm needs \\(O(\\Delta (P)i(P))\\) time and \\(O(w(P)|P|)\\) space (\\(i(P)\\) is the number of all order ideals of \\(P\\) and \\(w(P)\\) is the width of \\(P\\)).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936459$173E1A51-6A5F-4599-A359-1E89EDF29292","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e77d710fff360ac5f5e834555bc2a388abb806e6","datavalue":{"value":{"entity-type":"item","numeric-id":409252,"id":"Q409252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936459$A5492DB7-CEF3-422E-8BBF-5414962CADAC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ce5b74470053f031a57488d42a2b289573daad5a","datavalue":{"value":"06D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936459$014CEBBF-80D4-4FD1-ADA7-3A425A02C00B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936459$E2230DE2-FDE8-4DBD-9653-E0EE7CC6D066","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936459$35EA5082-DA72-46BB-8212-38C3857B1EC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0c3cdafa68da1cd8441c02cae1d4f7b344a92c14","datavalue":{"value":"94B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936459$12AAA8F9-92B1-4153-8ACA-AD945C5E881B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b866e402f5014483b4503b8d00715b0300fbc39a","datavalue":{"value":"1613398","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936459$259F4021-48F9-4CE5-B7BB-1C8156819C10","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"762a112ef0429a3655234c3e246a242461dca9bf","datavalue":{"value":"poset","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936459$0B44669B-7645-4343-AEB0-E06E6A4B9A1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"804e1d9b648f753b6db951a26f7e76351269ee09","datavalue":{"value":"ideal lattice","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936459$DD5E5203-8C6D-4164-9163-FEEE0F5DC993","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a43bc3e7b55679d1164eb2feea01cbda49001ffb","datavalue":{"value":"covering relation","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936459$618AC923-F5D3-49EE-8085-9E313FC723E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b5d2ed9e2a007aa7125a42427017ee80c49fbc8","datavalue":{"value":"list of all order ideals","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936459$BEC4FD90-9344-450B-94CA-00624935FDB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c27a8414208eba22b391b2c3a982e6e5e1d84b","datavalue":{"value":"linear time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936459$D9F68B2F-0848-4A1F-8EA0-FD1D8DE7F856","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96c1e880b32ea8b3dac57a173b38c6b2b43fd91f","datavalue":{"value":"ideal tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q5936459$DFBBA17E-1087-4560-800F-285DB59047FF","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":"Q5936459$D3A2E246-7819-4361-B226-9B02F383BE29","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cdc57cf2ba5617fc074cae34fef64910590e17f4","datavalue":{"value":{"entity-type":"item","numeric-id":5331549,"id":"Q5331549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936459$DEBD663D-B144-45DA-BD2A-DBFD8D67AC60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd2814a1fcdc7203d341baa5129d69e076839780","datavalue":{"value":{"entity-type":"item","numeric-id":5581652,"id":"Q5581652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936459$9CFDEC69-436C-42F7-9586-0D08A35C3E0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5c558f67392ec96604f888a847cc9a7ef879482","datavalue":{"value":{"entity-type":"item","numeric-id":3360658,"id":"Q3360658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936459$647DFE75-D98E-400C-95ED-90DB4026E2AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"025b2a408265c64babd878aaa0b7060b1a5203c7","datavalue":{"value":{"entity-type":"item","numeric-id":5044769,"id":"Q5044769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936459$0484B229-7832-4A3B-98AF-38FB2300ED47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5ddc74540eb05642bbf4d8044f544a32da40023","datavalue":{"value":{"entity-type":"item","numeric-id":1183948,"id":"Q1183948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936459$5424BB01-BD6A-4251-8540-03F1FD472DEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936459$3BAC9093-4047-408F-B2B5-B72F7C4CAD3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8595d4f26a52290653218492b3013dec22ef40cf","datavalue":{"value":{"entity-type":"item","numeric-id":1366682,"id":"Q1366682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936459$1056D708-7078-47FB-8BFD-071A57B7B9B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6ab9018939e7b8393d9fd43876866c450d286ea","datavalue":{"value":{"entity-type":"item","numeric-id":4366874,"id":"Q4366874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936459$779A2494-3F72-4B56-BB4D-5E8FBFB34D74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54174cdf9c6fd6f8482267ff71f0506a13a7f6ad","datavalue":{"value":{"entity-type":"item","numeric-id":3141536,"id":"Q3141536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936459$183E895C-BF15-479A-B4EC-361C1A949189","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936459$E01B08E3-1D4A-439F-A950-80A759383310","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f4f1456d4c20b84028ce7a4f350de1b0a3b0d1f","datavalue":{"value":{"entity-type":"item","numeric-id":1318347,"id":"Q1318347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936459$3C12B3D8-7A78-4E27-A2A5-AE66DB706AE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2a05a9238b4e94bb781552ef0f2d45656df3d8f","datavalue":{"value":{"entity-type":"item","numeric-id":4291563,"id":"Q4291563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936459$4BEC2181-55E4-4019-86D0-254BD1A0F943","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a3e46746f28dfe839ad39ab11e599d1851204a1","datavalue":{"value":{"entity-type":"item","numeric-id":3902521,"id":"Q3902521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936459$567AD157-C88B-4011-991C-43619D5F83B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d676e7da7d14f9f76edbc14b8dcd731caa5f6a5c","datavalue":{"value":{"entity-type":"item","numeric-id":4376203,"id":"Q4376203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936459$A0180F25-57E2-455E-8324-0E61324BD38C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb00d0b38a30a9efcc2e710ef5ece605f977bf75","datavalue":{"value":{"entity-type":"item","numeric-id":1086160,"id":"Q1086160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5936459$41AAE519-FB05-4DFD-BA10-27A1035421A2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0ad8eefe44c07f1c2d9b8743e44da4a9b79612aa","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(00)00258-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q5936459$16F2847B-C298-475F-B694-0B2CCCB7AB35","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b1114484fe2e937edd1e3ee957b9669505aa1430","datavalue":{"value":"W2049890507","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5936459$5B4DAF30-C774-4564-976F-3040F0ABA775","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5fd146dc1e104b45199e7ba27d7509031f2efa20","datavalue":{"value":{"entity-type":"item","numeric-id":1366682,"id":"Q1366682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cdf95f87dd20dffc8d80c82886a8fb272e24fe98","datavalue":{"value":{"amount":"+0.8774679899215698","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":"Q5936459$33ABA619-DACC-407F-B7C3-C308057F4244","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62f43b0ff27066f3c812e5e7891d310ed9aadbc2","datavalue":{"value":{"entity-type":"item","numeric-id":1606994,"id":"Q1606994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7fa1e2b49277f8774f6d2da5d8efafe46faa998","datavalue":{"value":{"amount":"+0.8771640658378601","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":"Q5936459$A0067EE3-5699-4840-BC35-604E89291F6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3afbc0baa1dca17b9f10f4149f953602da6e4ce2","datavalue":{"value":{"entity-type":"item","numeric-id":810071,"id":"Q810071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09fc3767c4273175cab8b2f509c25816b0157b2d","datavalue":{"value":{"amount":"+0.8239601254463196","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":"Q5936459$0582364F-A3DD-40BD-9121-58915A0C14F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f64677c1778ee01d7aeaf01f67631beab1eb8ed9","datavalue":{"value":{"entity-type":"item","numeric-id":4850326,"id":"Q4850326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92213ab012c12f81ae5b31f9ba508779180d2af1","datavalue":{"value":{"amount":"+0.8100363612174988","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":"Q5936459$327BFFE0-3A63-4DB1-9E0B-6A2E0560D558","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12b81d7233a37d016b1c76bf085b3126cee13b39","datavalue":{"value":{"entity-type":"item","numeric-id":4607917,"id":"Q4607917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92213ab012c12f81ae5b31f9ba508779180d2af1","datavalue":{"value":{"amount":"+0.8100363612174988","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":"Q5936459$5578ABD1-BDBD-45F0-8CF6-A16D31F8CCEA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5936459","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5936459"}}}}}