IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v8y2020i8p1253-d392714.html
   My bibliography  Save this article

Using Extended Logical Primitives for Efficient BDD Building

Author

Listed:
  • David Fernandez-Amoros

    (Deptment of Computer Systems and Software Engineering, Universidad Nacional de Educacion a Distancia (UNED), 28040 Madrid, Spain)

  • Sergio Bra

    (Deptment of Computer Systems and Software Engineering, Universidad Nacional de Educacion a Distancia (UNED), 28040 Madrid, Spain)

  • Ernesto Aranda-Escolástico

    (Deptment of Computer Systems and Software Engineering, Universidad Nacional de Educacion a Distancia (UNED), 28040 Madrid, Spain)

  • Ruben Heradio

    (Deptment of Computer Systems and Software Engineering, Universidad Nacional de Educacion a Distancia (UNED), 28040 Madrid, Spain)

Abstract

Binary Decision Diagrams (BDDs) have been used to represent logic models in a variety of research contexts, such as software product lines, circuit testing, and plasma confinement, among others. Although BDDs have proven to be very useful, the main problem with this technique is that synthesizing BDDs can be a frustratingly slow or even unsuccessful process, due to its heuristic nature. We present an extension of propositional logic to tackle one recurring phenomenon in logic modeling, namely groups of variables related by an exclusive-or relationship, and also consider two other extensions: one in which at least n variables in a group are true and another one for in which at most n variables are true. We add XOR, atLeast-n and atMost-n primitives to logic formulas in order to reduce the size of the input and also present algorithms to efficiently incorporate these constructions into the building of BDDs. We prove, among other results, that the number of nodes created during the process for XOR groups is reduced from quadratic to linear for the affected clauses. the XOR primitive is tested against eight logical models, two from industry and six from Kconfig-based open-source projects. Results range from no negative effects in models without XOR relations to performance gains well into two orders of magnitude on models with an abundance of this kind of relationship.

Suggested Citation

  • David Fernandez-Amoros & Sergio Bra & Ernesto Aranda-Escolástico & Ruben Heradio, 2020. "Using Extended Logical Primitives for Efficient BDD Building," Mathematics, MDPI, vol. 8(8), pages 1-17, July.
  • Handle: RePEc:gam:jmathe:v:8:y:2020:i:8:p:1253-:d:392714
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/8/8/1253/pdf
    Download Restriction: no

    File URL: https://www.mdpi.com/2227-7390/8/8/1253/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Heradio, Ruben & Perez-Morago, Hector & Alférez, Mauricio & Fernandez-Amoros, David & Alférez, Germán H., 2016. "Augmenting measure sensitivity to detect essential, dispensable and highly incompatible features in mass customization," European Journal of Operational Research, Elsevier, vol. 248(3), pages 1066-1077.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Na Liu & Pui-Sze Chow & Hongshan Zhao, 2020. "Challenges and critical successful factors for apparel mass customization operations: recent development and case study," Annals of Operations Research, Springer, vol. 291(1), pages 531-563, August.
    2. Choi, Tsan-Ming & Ma, Cheng & Shen, Bin & Sun, Qi, 2019. "Optimal pricing in mass customization supply chains with risk-averse agents and retail competition," Omega, Elsevier, vol. 88(C), pages 150-161.
    3. Vladimir Modrak & Zuzana Soltysova & Jan Modrak & Annamaria Behunova, 2017. "Reducing Impact of Negative Complexity on Sustainability of Mass Customization," Sustainability, MDPI, vol. 9(11), pages 1-16, November.
    4. Li, Wei & Sun, Hui & Tong, Meng & Mustafee, Navonil & Koh, Lenny, 2024. "Customizing customization in a 3D printing-enabled hybrid manufacturing supply chain," International Journal of Production Economics, Elsevier, vol. 268(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:8:y:2020:i:8:p:1253-:d:392714. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.