{"entities":{"Q311532":{"pageid":313299,"ns":120,"title":"Item:Q311532","lastrevid":60908880,"modified":"2026-04-10T19:54:47Z","type":"item","id":"Q311532","labels":{"en":{"language":"en","value":"Fast M\u00f6bius inversion in semimodular lattices and ER-labelable posets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6626790"}},"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":"Q311532$7898C668-59DA-4461-9243-A003EE375C03","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3ad55881149bd64924137326c965b139f2679c32","datavalue":{"value":{"text":"Fast M\u00f6bius inversion in semimodular lattices and ER-labelable posets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q311532$6341E516-DA14-4CBB-97C0-956B07EF5F97","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aac82f57bb6fa97bcdfadd4b29ac35ee4b7de6a9","datavalue":{"value":"1377.06006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q311532$DB4CDC2E-EC5B-4D85-A87C-7AF5D8019385","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9292ff12e4171a5091c022d8ddfe9a9a84e01eef","datavalue":{"value":{"entity-type":"item","numeric-id":262280,"id":"Q262280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311532$5F9B3D5A-36D8-4942-B90C-39DC6139F186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8266cb84aafd53ebbffb3b97a4643131348717a2","datavalue":{"value":{"entity-type":"item","numeric-id":311530,"id":"Q311530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311532$B2F7D2E5-579B-449C-B2D1-CF6882F95915","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ea9ddc2f8ada2584f88a28db39ee22d5b1579ed2","datavalue":{"value":{"entity-type":"item","numeric-id":311531,"id":"Q311531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311532$B2504DED-3326-4FFC-AD0C-615F36D2EBC6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311532$4A685FE1-1A2C-454F-A328-4A60FBA756B0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b5855202242268e2d32d9cba2484fa0b5d8a8d40","datavalue":{"value":{"time":"+2016-09-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q311532$C2D27F28-AF45-418F-94BC-22075C13A8FC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a5d33ac2e72dfdb83c89134950332ad7d9a05391","datavalue":{"value":"https://arxiv.org/abs/1603.03889","type":"string"},"datatype":"url"},"type":"statement","id":"Q311532$FE98C55D-7E15-4851-AB94-8EBB803D4E4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"d60326db2b2f8cb160ce9c980fd149bb711fcdae","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p26","type":"string"},"datatype":"url"},"type":"statement","id":"Q311532$C8CB579E-F747-48F0-AA80-283147DD4097","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"47e5c6d08b39e79bdd0bccfaeec11db7eee63b87","datavalue":{"value":"06C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q311532$B0C57AD9-D5C7-40B5-B49F-9067B04FD9C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f3d0b1de78ad0e32d646815f9dc7561538cada7","datavalue":{"value":"06A07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q311532$5364F71D-9151-4693-A239-2F16ED1673E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q311532$B992EF46-9334-4AAE-9FD7-5EE5D23DC288","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a5372688a0d668805df5d9ffd1da58833a0f595","datavalue":{"value":"68R05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q311532$C553E998-6223-4F8D-9552-3D79373A17DE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"20e190190684302cd828db66744010a44e3f7e93","datavalue":{"value":"6626790","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q311532$7DA15F2E-17A0-4047-9231-90353261D1C2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"020dcd602d93acb62a2ccabd471119c076b75e9d","datavalue":{"value":"M\u00f6bius inversion","type":"string"},"datatype":"string"},"type":"statement","id":"Q311532$B61C4D32-E006-410A-B7B7-FFAF1FAF4BEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6674112915463e4f8a1d08f7591bbaf813951be9","datavalue":{"value":"semimodular lattice","type":"string"},"datatype":"string"},"type":"statement","id":"Q311532$F9B5C351-9ADC-4A18-B0FB-4DC5994D6811","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c1f591f010288bc20bb4c9833e9915b9d6f2768","datavalue":{"value":"ER-labelable poset","type":"string"},"datatype":"string"},"type":"statement","id":"Q311532$B0216C35-4103-45C1-81CD-FCC826973194","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a461cfcc1c525c3e05a3716cbb9b308cdf61f148","datavalue":{"value":{"entity-type":"item","numeric-id":1175934,"id":"Q1175934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311532$2BA1BACB-5BBC-4EE4-9A49-E79E41344128","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":"Q311532$B8FDB920-182C-40C7-9D1D-D881A967FC1A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f6f0e024114319e5eb6aae9883a0233df2f35ab","datavalue":{"value":{"entity-type":"item","numeric-id":3549598,"id":"Q3549598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311532$DBE01655-21DF-4B86-BB24-20ABBA91BC8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8dfa9fab47d2bf83141e541b1d2f7d1f2882078d","datavalue":{"value":{"entity-type":"item","numeric-id":4962203,"id":"Q4962203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311532$7FB0E04F-09FB-493A-A62E-C6B5FE7448B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80a37fe777904b2e0aa6381ec42c255c2193e426","datavalue":{"value":{"entity-type":"item","numeric-id":4889962,"id":"Q4889962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311532$4512BD90-86BB-418B-B842-2078DB486689","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a6077e2e54fd6a54fd3728489a248cfff870e3c","datavalue":{"value":{"entity-type":"item","numeric-id":4331740,"id":"Q4331740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311532$73751C6B-2C7C-434E-9FDA-A0CD88FA5009","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":"Q311532$108956A5-50E8-481D-9AB1-DD81C7119CD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75eafa87c266a7c18e3ace9e65b49c59b5f5be5c","datavalue":{"value":{"entity-type":"item","numeric-id":3162101,"id":"Q3162101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311532$27EE2664-9C5B-469A-AF91-E66333493D56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f9970631683775d00fcaae20189428e655730f8","datavalue":{"value":{"entity-type":"item","numeric-id":2843340,"id":"Q2843340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311532$036C43CE-9230-4C9F-8EF8-AF155ACF6499","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d08ad8e3b476e03b8e9a0c62d17c2f47ac999fa1","datavalue":{"value":{"entity-type":"item","numeric-id":4014208,"id":"Q4014208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311532$269E1147-06BC-4729-839B-0B778AA2F97A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cd6924295ed9218e032e51db2460d0e4970ce79","datavalue":{"value":{"entity-type":"item","numeric-id":986071,"id":"Q986071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311532$5DC64335-148D-49E0-B405-EB0E9DA8A3E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e33dc7e2933adc0b52e7b1b33d156be32b3b641d","datavalue":{"value":{"entity-type":"item","numeric-id":5417641,"id":"Q5417641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311532$7D47D405-516C-4B55-B3CE-DF97BE4F4474","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2bb6206a01597a9f278350081d9fd8c6c0319ff","datavalue":{"value":{"entity-type":"item","numeric-id":2558874,"id":"Q2558874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311532$7B51DC2E-9B40-46A7-93B1-A71C91C36793","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33ebd623f6b8e57b27792095bc1a5f936ffa53ab","datavalue":{"value":{"entity-type":"item","numeric-id":3748279,"id":"Q3748279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311532$0209203D-EBB7-470A-8CB4-FEC433771088","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51e06cd08b21ba41692bb65b88d6aafecf32e6a8","datavalue":{"value":{"entity-type":"item","numeric-id":4726175,"id":"Q4726175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q311532$C463A1FE-86FB-4766-843D-C602FEDA990F","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"50b19890e838edb09babee08dd5e5dd0ddfd6891","datavalue":{"value":"bafkreiex2zwpxk7m7gajmygzpjdqj6h4losss5epjlvrkqk3wa5j6vae3u","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q311532$99EE6809-07A2-4BE1-B612-48D85710B6C1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6d4d057dcb981ed1c204e90025364926a791cce2","datavalue":{"value":"Fast methods for computing both zeta and M\u00f6bius transformations in finite posets or lattices are important for many algorithms of combinatorial nature. Generally, the authors seek to minimize the length of the programs.NEWLINENEWLINELet \\((P;\\leq)\\) be a finite poset and let \\(f:P\\rightarrow A\\) be a map to an abelian group \\(A.\\) The \\textit{zeta transformation} of \\(f\\) is the function \\(g:P\\rightarrow A\\) such that for all \\(y\\in P,\\) \\(g(y)=\\sum(f(x): x\\leq y)\\) is true. For a given poset, the computation from \\(f\\) to its zeta transformation \\(g\\) can be represented as a \\textit{straigt-line program}, which means that a sequence of elementary pairwise arithmetic operations can be executed in turn, without loops or conditional statements. Since the zeta transformation is always invertible, the authors construct a short straight-line program also for the inverse transformation, called the M\u00f6bius transformation.NEWLINENEWLINEThe complexity of the given poset is characterized by three quantities: the number of elements \\(v=|P|,\\) the number of join-irreducible elements \\(n=|I|\\) and the number of edges \\(e=|E|\\) of Hasse diagram of \\(P.\\) In addition to this, an \\textit{edge labeling} \\(\\lambda:E\\rightarrow Z\\), or labeling with \\textit{rising chains}, can be given.NEWLINENEWLINEThe authors present four new algorithms for fast zeta and M\u00f6bius transformations. More precisely: (1) In a semimodular lattice with \\(e\\) edges, the join irreducible elements can be ordered so that Algorithm 1 (for zeta transformation) generates exactly \\(e\\) additions. Algorithm 2 (for M\u00f6bius transformation) is similar. Subtraction replaces the addition. (2) In an ER-labelable poset that has \\(e\\) edges, the zeta transformation can be computed in \\(e\\) additions and the M\u00f6bius transformation in \\(e\\) subtractions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q311532$9C67DC5C-3A32-4D87-A3FB-AFCD34DC5EBF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c96f31c21c599df4912deaf373beaff916e5fa6","datavalue":{"value":{"entity-type":"item","numeric-id":5743488,"id":"Q5743488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff317c47c7a638c939c537c8cfdfbfaa326ab039","datavalue":{"value":{"amount":"+0.8825874328613281","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":"Q311532$FF16E5CC-F821-4EAD-8C1D-704C179F7065","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3887436224fbac122f76103186469b3b0ecfe68c","datavalue":{"value":{"entity-type":"item","numeric-id":4962203,"id":"Q4962203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cd794841a05a5ba11965a594e2252adc68e84fa","datavalue":{"value":{"amount":"+0.8825350403785706","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":"Q311532$E0758B5B-A554-44E0-9DA8-72F7CC9A9B13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e886209a38fa9a391b57ea9f22e1a13020eb52c","datavalue":{"value":{"entity-type":"item","numeric-id":1087570,"id":"Q1087570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84924bfb89352836507a79a6bf918afd136fe643","datavalue":{"value":{"amount":"+0.7287779450416565","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":"Q311532$E3AEB27A-14A9-4FF2-95C6-FD8CFCB4F2F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fa9fe85711ab1136dadbc4bd09928efb542113e","datavalue":{"value":{"entity-type":"item","numeric-id":1355470,"id":"Q1355470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ce4535ae962ddd7a4992c83fa17dcb7c9b83136","datavalue":{"value":{"amount":"+0.724107563495636","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":"Q311532$008754E3-23A9-45FF-80B3-5DDC4FF8A9AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8dc0b34d687f5e27a78a27d0eb8d462b98cc3a20","datavalue":{"value":{"entity-type":"item","numeric-id":4014208,"id":"Q4014208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bed1f2b8eff55378901328c8fdb6381246a04ce4","datavalue":{"value":{"amount":"+0.7129545211791992","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":"Q311532$3684A130-2AF8-481E-9412-4DB48E1CC602","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Fast M\u00f6bius inversion in semimodular lattices and ER-labelable posets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Fast_M%C3%B6bius_inversion_in_semimodular_lattices_and_ER-labelable_posets"}}}}}