EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Compression with Wildcards: All k-Models of a Binary Decision Diagram

Marcel Wild, Yves Semegni

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →