Return to search

Minimální reprezentace víceintervalových booleovských funkcí / Minimální reprezentace víceintervalových booleovských funkcí

When we interpret the input vector of a Boolean function as a binary number, we define interval Boolean function fn [a,b] so that fn [a,b](x) = 1 if and only if a ≤ x ≤ b. Disjunctive normal form is a common way of representing Boolean functions. Minimization of DNF representation of an interval Boolean function can be per- formed in linear time. The natural generalization to k-interval functions seems to be significantly harder to tackle. In this thesis, we discuss the difficulties with finding an optimal solution and introduce a 2k-approximation algorithm.

Identiferoai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:331787
Date January 2015
CreatorsBártek, Filip
ContributorsKučera, Petr, Gregor, Petr
Source SetsCzech ETDs
LanguageEnglish
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/masterThesis
Rightsinfo:eu-repo/semantics/restrictedAccess

Page generated in 0.0013 seconds