Publicación:
Using Extended Logical Primitives for Efficient BDD Building

Vista sencilla de ítem
dc.contributor.authorFernández Amoros, David José
dc.contributor.authorBra, Sergio
dc.contributor.authorAranda Escolástico, Ernesto
dc.contributor.authorHeradio Gil, Rubén
dc.date.accessioned2024-12-11T11:47:08Z
dc.date.available2024-12-11T11:47:08Z
dc.date.issued2020
dc.descriptionThe registered version of this article, first published in “Mathematics, 8, 2020", is available online at the publisher's website: MDPI, https://doi.org/10.3390/math8081253 La versión registrada de este artículo, publicado por primera vez en “Mathematics, 8, 2020", está disponible en línea en el sitio web del editor: MDPI, https://doi.org/10.3390/math8081253
dc.description.abstractBinary 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.en
dc.description.versionversión publicada
dc.identifier.citationFernandez-Amoros, D., Bra, S., Aranda-Escolástico, E., & Heradio, R. (2020). Using Extended Logical Primitives for Efficient BDD Building. Mathematics, 8(8), 1253. https://doi.org/10.3390/math8081253
dc.identifier.doihttps://doi.org/10.3390/math8081253
dc.identifier.issn2227-7390
dc.identifier.urihttps://hdl.handle.net/20.500.14468/24820
dc.journal.issue8
dc.journal.titleMathematics
dc.journal.volume8
dc.language.isoen
dc.page.initial1253
dc.publisherMDPI
dc.relation.centerE.T.S. de Ingeniería Informática
dc.relation.departmentIngeniería de Software y Sistemas Informáticos
dc.rightsinfo:eu-repo/semantics/openAccess
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/deed.es
dc.subject12 Matemáticas::1203 Ciencia de los ordenadores ::1203.17 Informática
dc.subject.keywordsbinary decision diagramsen
dc.subject.keywordssoftware product linesen
dc.subject.keywordscircuit testingen
dc.subject.keywordsconfigurable systemsen
dc.titleUsing Extended Logical Primitives for Efficient BDD Buildingen
dc.typeartículoes
dc.typejournal articleen
dspace.entity.typePublication
relation.isAuthorOfPublication60bb7374-7021-4fda-b2cb-ef7f923c64f4
relation.isAuthorOfPublication19c0c538-4e7e-4de5-afd9-6ff1a8bbf88e
relation.isAuthorOfPublication38af03ae-439e-45a8-8383-80340d20f7cb
relation.isAuthorOfPublication.latestForDiscovery60bb7374-7021-4fda-b2cb-ef7f923c64f4
Archivos
Bloque original
Mostrando 1 - 1 de 1
Miniatura
Nombre:
FernandezAmoros_David_Using_Extended.pdf
Tamaño:
458.61 KB
Formato:
Adobe Portable Document Format
Descargar
Bloque de licencias
Mostrando 1 - 1 de 1
No hay miniatura disponible
Nombre:
license.txt
Tamaño:
3.62 KB
Formato:
Item-specific license agreed to upon submission
Descripción:
Descargar
Colecciones
Artículos y papers