{"entities":{"Q798296":{"pageid":800144,"ns":120,"title":"Item:Q798296","lastrevid":64455441,"modified":"2026-04-11T19:59:39Z","type":"item","id":"Q798296","labels":{"en":{"language":"en","value":"Replaceability and computational equivalence for monotone boolean functions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3869224"}},"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":"Q798296$319D0197-D3F1-46CD-8A2E-1BE2E026C759","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1da44c88299dd6ec4b996e451a4dbfb266fba20f","datavalue":{"value":{"text":"Replaceability and computational equivalence for monotone boolean functions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q798296$00347A50-B996-48E7-A33B-5E6EA798D47A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"914f8a56e723b960d0d49ef738bd397bdaf444a2","datavalue":{"value":"0545.94022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q798296$877A6FDB-C8AA-4738-965A-A207E7FBEAFA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0757d204ec64dc217e6117eef966cbe0e96e9331","datavalue":{"value":"10.1007/BF00288777","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q798296$27675061-6D26-46C2-9C38-6D065A9346B0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a1be098be8e821ce27943f7fe4d1b06cd7698157","datavalue":{"value":{"entity-type":"item","numeric-id":798295,"id":"Q798295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q798296$4CEAA827-6C45-4BEA-B43D-4D55DA3D1044","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q798296$C41ABED4-6DF9-4840-ABC8-E4266BDBBB6B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q798296$324425A7-9976-477A-89DE-F0BA1830C232","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bf3493b66f1ac0450d712a03a8a37a3d90b9d348","datavalue":{"value":"Replacement rules have played an important role in the study of monotone boolean function complexity. In this paper, notions of replaceability and computational equivalence are formulated in an abstract algebraic setting, and examined in detail for finite distributive lattices - the appropriate algebraic context for monotone boolean functions. It is shown that when computing an element f of a finite distributive lattice D, the elements of D partition into classes of computationally equivalent elements, and define a quotient of D in which all intervals of the form [\\(t\\wedge f,t\\vee f]\\) are boolean. This quotient is an abstract simplicial complex with respect to ordering by replaceability. Other results include generalisations and extensions of known theorems concerning replacement rules for monotone boolean networks. Possible applications of computational equivalence in developing upper and lower bounds on monotone boolean function complexity are indicated, and new directions of research, both abstract mathematical and computational, are suggested.","type":"string"},"datatype":"string"},"type":"statement","id":"Q798296$3C86B5D0-6F69-4AF9-81B6-B3DCF5F6CDCD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1e903e68a16880f66ed79a0863889f1b2d3c837c","datavalue":{"value":"94C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q798296$3F306D11-E6C1-4ADA-8EE9-828DEFB67D83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q798296$5475BA80-625A-48A0-8D07-9DC14DF2CC0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ce5b74470053f031a57488d42a2b289573daad5a","datavalue":{"value":"06D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q798296$8963431E-F1A4-40FC-8D6F-E56A864D8177","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"232b249138001ce1afa095386cce3a39dd964fe3","datavalue":{"value":"3869224","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q798296$E5F647E0-4F2A-4144-A5B6-D3D9D8E1ED89","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2e02ff72b5ec7051af7557af9ece6f3c42154371","datavalue":{"value":"monotone boolean function complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q798296$4E6B953C-E8F1-42DF-9F28-D9F960D0DB7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a4ba14eed269b39421c8227a1dfbd573d0345e3","datavalue":{"value":"replaceability","type":"string"},"datatype":"string"},"type":"statement","id":"Q798296$47551B3B-0647-4CED-95DD-427F1907CC0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e06d08b1a2858b1491444255904f57bce2c0f6fe","datavalue":{"value":"computational equivalence","type":"string"},"datatype":"string"},"type":"statement","id":"Q798296$24BD0E20-9049-4532-BB67-4FB5F607394A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"076beb5883c561d34b7647deb1e2796c6e71f0b4","datavalue":{"value":"finite distributive lattices","type":"string"},"datatype":"string"},"type":"statement","id":"Q798296$6D174008-C133-4CD7-92B4-4E22DBD6EE9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"010226dbba1812a6bdba52f06d6df772264815f1","datavalue":{"value":"abstract simplicial complex","type":"string"},"datatype":"string"},"type":"statement","id":"Q798296$28E215EF-F8C6-437B-A618-938BCAA6DB7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ebfd8cbcbd234fd52b2c1037ce5690556a861e6","datavalue":{"value":"monotone boolean networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q798296$B2F936EE-7147-4A40-9501-559A67890760","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":"Q798296$B1514C51-120F-4CBD-943F-6716AF47ACAF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b824bc8fff4efeae95786f061556499a6a2c1ba","datavalue":{"value":{"entity-type":"item","numeric-id":3218067,"id":"Q3218067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q798296$F3DF2B59-E249-4DE4-A94A-1958E6070806","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"024ceacef20630dcfc833e3dfb1447d4af15581b","datavalue":{"value":{"entity-type":"item","numeric-id":4067157,"id":"Q4067157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q798296$8AA5FE3C-093C-4152-A35B-8E881F86673C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9680255befb21596b72ab28ea65296e19b25623","datavalue":{"value":{"entity-type":"item","numeric-id":4195009,"id":"Q4195009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q798296$EDF6CAFB-2C13-438B-8BFB-81D3D7A37974","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a7f95a181a122f35ae18fd86fcaee76950d7cde","datavalue":{"value":{"entity-type":"item","numeric-id":5532570,"id":"Q5532570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q798296$7333517B-CEE7-4F54-9E04-9381DB4A2C8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47ad6861c78fd4390c0613c4ab63948d956f71fd","datavalue":{"value":{"entity-type":"item","numeric-id":5639727,"id":"Q5639727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q798296$F6C75D4B-BD87-4724-A36C-0B16D5640F2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"febe18a8bb8e7377d5dd6f028103ec1a3068042d","datavalue":{"value":{"entity-type":"item","numeric-id":1224550,"id":"Q1224550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q798296$79651717-1484-449B-9291-D883CD832CF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc9e6bcc7d90a33873dcafb49526b39cfba617fe","datavalue":{"value":{"entity-type":"item","numeric-id":1218267,"id":"Q1218267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q798296$E0262FDB-D681-448A-9675-8B91A77BF316","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f08aea2375da56a8a7d87cd0bcc8ed91b9c89ac9","datavalue":{"value":{"entity-type":"item","numeric-id":1835900,"id":"Q1835900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q798296$9D935F5A-2A5D-4204-AEB7-BF813798C4C1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d14150a40d56272f516b5824af2ec39ae648f867","datavalue":{"value":{"entity-type":"item","numeric-id":1094870,"id":"Q1094870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a0a0cbba635dc8ebe0111849ad32ded04bf3fda","datavalue":{"value":{"amount":"+0.8722446","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q798296$5D55190B-84C9-4F9B-A6D4-EB2B7D4FCA91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ede4c1281789a457e1b08796b344c2c6b20ad334","datavalue":{"value":{"entity-type":"item","numeric-id":3352968,"id":"Q3352968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b977db83dffabb769baf624a3ad161dc188ea611","datavalue":{"value":{"amount":"+0.87160563","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q798296$E396554A-021A-41D9-A97A-3712E54A1ABB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af67bc2cb274044ff1b89c5ef782f2933396d971","datavalue":{"value":{"entity-type":"item","numeric-id":1176917,"id":"Q1176917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bf855e7ba9f58cf7e3444ce06334f1d727783e6","datavalue":{"value":{"amount":"+0.86624396","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q798296$58CD7A03-6583-4FD9-B0B3-D9AE05C70B45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a00d0f99364b03a4d62ccffd44a575b00091e21","datavalue":{"value":{"entity-type":"item","numeric-id":1099134,"id":"Q1099134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"06b8b9596bc0efb93eaf1f55423c9cf9448a9c93","datavalue":{"value":{"amount":"+0.8617445","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q798296$510604BF-544B-47B7-830A-49108CED1AE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26ecac5c5c4c2ce3242aa3619590051ba9c28fbe","datavalue":{"value":{"entity-type":"item","numeric-id":1121854,"id":"Q1121854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5bac0d84052b3ff75eb2703b50b7f4d11a542f50","datavalue":{"value":{"amount":"+0.8617344","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q798296$11CB7ABF-A735-427B-9D3A-65635F68A645","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c45f191408e9449af385d135395ab67a14b686dd","datavalue":{"value":{"entity-type":"item","numeric-id":3218067,"id":"Q3218067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8db58a9aee59e8747b14114d8fb4a4e27e80da18","datavalue":{"value":{"amount":"+0.8609804","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q798296$5EE07B31-2582-4170-9314-BBBB298BA532","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc666b90fbbe93cb694ef67eb317332736f5eab5","datavalue":{"value":{"entity-type":"item","numeric-id":5205818,"id":"Q5205818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a54664fc94d9ee53ac1964e1a77efe6ab535882","datavalue":{"value":{"amount":"+0.8604058","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q798296$A28506C0-FE33-48D1-9CC8-5A2935C8098D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9559cf010eb387eab5f147b12df20e21ba75a824","datavalue":{"value":{"entity-type":"item","numeric-id":5111133,"id":"Q5111133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a54664fc94d9ee53ac1964e1a77efe6ab535882","datavalue":{"value":{"amount":"+0.8604058","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q798296$8EEFDF8D-51F1-4195-BF7D-C95BC5FFD2EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc7f5f680c589ecac91d4a5ee87a789fb4d40816","datavalue":{"value":{"entity-type":"item","numeric-id":5491236,"id":"Q5491236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe74885d0eefb903d125a5d9fc29d5168eab7695","datavalue":{"value":{"amount":"+0.85889566","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q798296$E3B0F27A-9ECC-4030-BEF8-916819BF2F18","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Replaceability and computational equivalence for monotone boolean functions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Replaceability_and_computational_equivalence_for_monotone_boolean_functions"}}}}}