Free binary decision diagrams for the computation of EAR(n)

KARA, J a Daniel KRÁĽ. Free binary decision diagrams for the computation of EAR(n). COMPUTATIONAL COMPLEXITY. BASEL: BIRKHAUSER VERLAG AG, 2006, roč. 15, č. 1, s. 40-61. ISSN 1016-3328. Dostupné z: https://doi.org/10.1007/s00037-006-0206-5.

Základní údaje

Originální název

Free binary decision diagrams for the computation of EAR(n)

Autoři

KARA, J a Daniel KRÁĽ

Vydání

COMPUTATIONAL COMPLEXITY, BASEL, BIRKHAUSER VERLAG AG, 2006, 1016-3328

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 1.125

Označené pro přenos do RIV

Ne

DOI

https://doi.org/10.1007/s00037-006-0206-5

UT WoS

000237121400003

Klíčová slova anglicky

binary decision diagrams; free binary decision diagrams; Boolean functions

---

Anotace

V originále

Free binary decision diagrams (FBDDs) are graph-based data structures representing Boolean functions with the constraint (additional to binary decision diagram) that each variable is tested at most once during the computation. The function EARn is the following Boolean function defined for n x n Boolean matrices: EARn (M) = 1 iff the matrix M contains two equal adjacent rows. We prove that each FBDD computing EAR(n) has size at least 2(0.63log22n-O(log n log log n)) and we present a construction of such diagrams of size approximately 2(1.89 log22 n+O(log n)).