{"entities":{"Q1878402":{"pageid":1889144,"ns":120,"title":"Item:Q1878402","lastrevid":69177291,"modified":"2026-04-13T05:16:54Z","type":"item","id":"Q1878402","labels":{"en":{"language":"en","value":"Ordered binary decision diagrams and the Shannon effect"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2093409"}},"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":"Q1878402$BE84DBF8-6513-4C4C-B8A0-EF47C9075C76","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b48642ebbc05f68aa1bc2d9f821e6ff49255dbc4","datavalue":{"value":{"text":"Ordered binary decision diagrams and the Shannon effect","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1878402$A802208A-FA2F-468E-A059-128DFDEDC395","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6097212678b3621637fbcb5c6ccd551722e31cb5","datavalue":{"value":"1062.94075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1878402$6EDB7667-2C67-497A-9C43-4F1D836E21F6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5055b67a4ac6df55f565a1a0df1229a5db061b6d","datavalue":{"value":{"entity-type":"item","numeric-id":1607072,"id":"Q1607072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$1356273A-2DD7-4828-825C-C169EDA24410","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7f7828d89a9ab7dcac53cfa0b07091daf4925321","datavalue":{"value":{"entity-type":"item","numeric-id":171728,"id":"Q171728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$CF0C2E9A-F6F5-4E7D-AA9E-A0689849BD4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"afee67896574e0646c3ab5dc5b7fef009a143542","datavalue":{"value":{"entity-type":"item","numeric-id":247943,"id":"Q247943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$1CAADFC1-4E66-4842-AC1F-DEAFFC5F419D","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":"Q1878402$4F092F93-68C2-47A7-9FE4-8C99E0A680DA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"dad9e6929b84d2aa86589bcc6be2d26ada8b5576","datavalue":{"value":{"time":"+2004-08-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1878402$FA242EC2-D97E-4631-9E00-D76B9E919807","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6feafccf8ab8b50d91b75b630376158a3a91fb86","datavalue":{"value":"The state-of-the-art data structures for Boolean functions are known as ordered binary decision diagrams (OBDDs). An OBDD is an acyclic digraph with one root and two terminals 0 and 1. This paper is devoted to theoretical investigations on the size of the OBDD of a Boolean function which has been chosen according to the uniform distribution. Using counting arguments, \\textit{H. Liaw} and \\textit{C. Lin} [IEEE Trans. Comput. 41, 661--664 (1992)] showed that the expected optimal OBDD size in this model is never more than a constant factor apart from the worst-case OBDD size of any function on \\(n\\) variables. Later \\textit{I. Wegener} [IEEE Trans. Comput. 43, 1262--1269 (1994; Zbl 1068.68685)] showed that the two quantities in fact coincide up to terms of lower order, if the number of variables is uniformly distributed in \\([2^{h},2^{h+1}-1]\\) and \\(h\\) goes to infinity. The phenomenon that almost all functions have the same OBDD size as the hardest functions up to a factor of \\(1+o(1)\\) is called the strong Shannon effect for random Boolean functions and OBDDs. The authors show that the strong Shannon effect is not valid for all \\(n\\). More precisely, the strong Shannon effect does not hold within intervals of constant width around the values \\(n=2^{h}+h\\), where \\(h\\) is a natural number, but it does hold outside these intervals. Their analysis uses a large deviation inequality that follows from Azuma's martingale inequality, and Chv\u00e1tal's bound on the hypergeometric distribution. This new approach proposes a generalization of OBDDs called ordered Kronecker functional decision diagrams (OKFDDs).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1878402$BF2F46F7-3C50-4621-9A66-4E5EAB72083C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1878402$30D167A6-6F82-4D45-B9D9-1A626A280075","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"09f3eb9b2932c3fdc120e877804d57f4cb2d94e9","datavalue":{"value":"06E30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1878402$CEF7C95A-B8A6-40BC-90C7-BB49AE2B6911","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1878402$4C7B1CD5-11F0-4B34-89A9-8DE033CD1692","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9f0beb5cd4916457748ab94e676d8de02b948ecf","datavalue":{"value":"2093409","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1878402$628299EB-B551-4A12-BEA4-FAE648794878","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5670d071866a3d53f623260620b05efb6ac7d49b","datavalue":{"value":"binary decision diagram","type":"string"},"datatype":"string"},"type":"statement","id":"Q1878402$05B3D530-2403-419A-9F3D-E275A20B0EB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d5bdb91ff2d9f461eed3becd47807e6259a9b1f","datavalue":{"value":"random Boolean function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1878402$E032C868-8DA6-4660-A279-C96162BF4E0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4752b484d49c9a2b93e0a9e10ae2fe7e85c97cb7","datavalue":{"value":"probabilistic analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1878402$33BB0DD4-DF7A-4D1E-AA1C-4553E82552E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"31b42010bcc53199c3a1d46bccdad5ee249cce7c","datavalue":{"value":"Shannon effect","type":"string"},"datatype":"string"},"type":"statement","id":"Q1878402$E2FFE2FA-21A8-42CC-B087-F4E18F65CF41","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$90BF7B68-5ADB-4510-ADCD-E9BD6A5AEA39","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"1bc012cf10551bf42bb05efd85ce69678e698524","datavalue":{"value":{"entity-type":"item","numeric-id":16622,"id":"Q16622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$E168747E-8DCB-4C1F-B1FA-9E23E6294E76","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":"Q1878402$FC9E1A3C-020C-492E-8E37-A2FC29FAF1F5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"329cb54788a93e398d6de3c33626abf807d31fd4","datavalue":{"value":"https://doi.org/10.1016/j.dam.2003.02.003","type":"string"},"datatype":"url"},"type":"statement","id":"Q1878402$2C7DAA93-4C16-44A2-84F7-72AA28111CD9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b6b38b2980f31de1aebc05efa9d6fd4e7b1b8a6e","datavalue":{"value":"W2031729686","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1878402$94003A4D-8DF5-4B78-A048-551618D86A07","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb508e5f7735364f1eef93fc0bb58e13f4eebeb6","datavalue":{"value":{"entity-type":"item","numeric-id":4645202,"id":"Q4645202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$E9420A78-582B-4A3A-BA1C-466AD4DB5D70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a25cb2b7c4b0e1fbf01fe9284c5c60664f98f2e4","datavalue":{"value":{"entity-type":"item","numeric-id":1908345,"id":"Q1908345"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$DAAA4293-D937-49D8-A1D5-9585982BE01F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50324ccb6206134f253ce476b8660b15930be48f","datavalue":{"value":{"entity-type":"item","numeric-id":673087,"id":"Q673087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$16405CAE-6461-4969-ADFC-A50A104E4C0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d0863918228d158fae088a6efc6f79f2c8e8057","datavalue":{"value":{"entity-type":"item","numeric-id":3724245,"id":"Q3724245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$D3E5D508-7DB3-4B0D-A33A-3F0957544630","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e9d760b56e81829535236b574ab4988cdae3b4b","datavalue":{"value":{"entity-type":"item","numeric-id":3417010,"id":"Q3417010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$D0C099BC-B349-460F-8E27-5121ACE60D11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c6c338f74f8724c3697d5b86b62f3375f4fb35b","datavalue":{"value":{"entity-type":"item","numeric-id":1253482,"id":"Q1253482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$E6F65FF9-6753-4B68-BC81-21C073CB0AE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2f8e628120e37a7c3e15f88b344869a76ec6bc8","datavalue":{"value":{"entity-type":"item","numeric-id":4325354,"id":"Q4325354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$A32A4164-B03E-4BDB-9302-BD3A7960C551","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b7988c704034e177d52c75fa599b21cdd056785","datavalue":{"value":{"entity-type":"item","numeric-id":4420806,"id":"Q4420806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$115B599F-93B8-4CB5-B502-769EFAC62D00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5e3a589df52b5b59a3ffc403954bc73d11c67c9","datavalue":{"value":{"entity-type":"item","numeric-id":4705326,"id":"Q4705326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$B8F707E1-A796-41DB-9D3A-F91E435A7070","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f248e065a96b9c6740809bd7ed036b829b97a5eb","datavalue":{"value":{"entity-type":"item","numeric-id":1607073,"id":"Q1607073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$F2D972AA-B1CE-4BE9-9BA6-A2FEDB0F55B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97591262ba872768ae74f8df649b42e9c5c697cb","datavalue":{"value":{"entity-type":"item","numeric-id":4420060,"id":"Q4420060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$7E0918FE-D9B1-442B-AFAB-0D80CDCA101D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38a504233a997a0376458e299e1a23ac6f83ce5c","datavalue":{"value":{"entity-type":"item","numeric-id":4847396,"id":"Q4847396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$3A8C7F6B-160F-4CEF-927B-3264AF3FFAB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3cc7e67abd48f121e29aac8a912fb842edee7fb","datavalue":{"value":{"entity-type":"item","numeric-id":5375349,"id":"Q5375349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$151FCBBA-06B5-4FF5-9142-1FE138051FF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8428f0fc96b22b52390f3bd7ced5caaf0972d20","datavalue":{"value":{"entity-type":"item","numeric-id":4864698,"id":"Q4864698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$01EC23DE-B79A-4670-969F-54F6815DFBE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9914395de143df926d2aecbb3bff4b2c2c78612","datavalue":{"value":{"entity-type":"item","numeric-id":4219538,"id":"Q4219538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$DF508BD3-4880-49BD-A964-15F287D1FEDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34101ed4e8ce2c8bca9fc7197b2b3a43ba98e34d","datavalue":{"value":{"entity-type":"item","numeric-id":1854498,"id":"Q1854498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$594D0163-BDCF-4DB5-9DCA-F57F9FC63D48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b7444e974a633833efedd6059662195a8c31635","datavalue":{"value":{"entity-type":"item","numeric-id":4419798,"id":"Q4419798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1878402$0A53867C-9D0F-4FCA-872E-0C32C8FE49A0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8a528153ac583ecbfbecb3d36d7569a55a0cbf6f","datavalue":{"value":"10.1016/J.DAM.2003.02.003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1878402$3660363C-83B0-45F8-A5D4-6DC0836B8796","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85051722761fbec9019a04dca4a47a2658cbe695","datavalue":{"value":{"entity-type":"item","numeric-id":4412138,"id":"Q4412138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"221d18f4f2e92cb9a87b13eaa2ad5fa124343478","datavalue":{"value":{"amount":"+0.8854589462280273","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":"Q1878402$44F65EA1-EDD5-4E83-B0AC-8092F7B748B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a2c9918ba4b1fc0dd70bff404640f480f488df3d","datavalue":{"value":{"entity-type":"item","numeric-id":1390857,"id":"Q1390857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad0202bb181f856146e5a8802f986452104d1ba3","datavalue":{"value":{"amount":"+0.885003924369812","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":"Q1878402$00960734-5098-4C6E-A37B-1ACD6BEF619C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c50b715c23ea0b1141b9edcc72913cca92cba22","datavalue":{"value":{"entity-type":"item","numeric-id":4487092,"id":"Q4487092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf69d4fc94d13a835a7301b7ce0f2941ec4c4407","datavalue":{"value":{"amount":"+0.8504311442375183","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":"Q1878402$CA40A3A1-7BD5-4553-98AD-523E6E32571C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f90b3a656f101e8301d557a9a9ad894f14ae8ba","datavalue":{"value":{"entity-type":"item","numeric-id":4705323,"id":"Q4705323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c0d581e72ec4e1b51b7984e0402a67408a85fce","datavalue":{"value":{"amount":"+0.8306472897529602","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":"Q1878402$DD305984-F729-4B87-940C-2CE08BE45A1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4790a1492f6e007c2ab89259245f47db30064e7f","datavalue":{"value":{"entity-type":"item","numeric-id":4419798,"id":"Q4419798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be7602d4be4f09cd69ae34f3abfb6f8c994a4152","datavalue":{"value":{"amount":"+0.8289102911949158","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":"Q1878402$0C43E371-D5A0-479C-98F5-980E14BBE33E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Ordered binary decision diagrams and the Shannon effect","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Ordered_binary_decision_diagrams_and_the_Shannon_effect"}}}}}