Compression with Wildcards: All k-Models of a Binary Decision Diagram
Contemporary Mathematics · 28.04.2026 · 2702-2720
DOI: 10.37256/cm.7320266889 ↗Kurz gefasst
Fachartikel in der Zeitschrift Contemporary Mathematics, online erschienen am 28.04.2026. Verfasst von Marcel Wild und 1 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
A bitstring of length n is an element of {0, 1} n . Further the bitstring (say) (0, 0, 1, 0, 1, 1,0) has Hamming-weight 3, since 3 times "1" occurs. A function of type : {0, 1} n → {0, 1} is a Boolean function, and a bitstring y ∈ {0, 1} n with (y) = 1 is a model of . Given a Binary Decision Diagram B of a Boolean function , it is well known that all N models of can be enumerated in polynomial total time, i.e. in time polynomial in n and |B| and N (here |B| is the size of B). Furthermore, upon using don't-care symbols, the enumeration can be rendered in a compressed fashion. We show that likewise all models of fixed Hamming-weight k can be enumerated in polynomial total time and in compressed fashion.
Zitieren
APA
Wild, M., & Semegni, Y. (2026). Compression with Wildcards: All k-Models of a Binary Decision Diagram. Contemporary Mathematics, 2702-2720. https://doi.org/10.37256/cm.7320266889
Vancouver
Wild M, Semegni Y. Compression with Wildcards: All k-Models of a Binary Decision Diagram. Contemporary Mathematics. 2026:2702-2720. doi:10.37256/cm.7320266889
BibTeX
@article{Wild2026,
author = {Wild, Marcel and Semegni, Yves},
title = {Compression with Wildcards: All k-Models of a Binary Decision Diagram},
journal = {Contemporary Mathematics},
year = {2026},
pages = {2702--2720},
doi = {10.37256/cm.7320266889}
}
EUVIMED