Interval Representations of 2-Monotonic and Threshold Boolean Functions

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F06%3A00002641" target="_blank" >RIV/00216208:11320/06:00002641 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Interval Representations of 2-Monotonic and Threshold Boolean Functions
Original language description
Threshold, 2-monotonic and interval Boolean functions constitute special classes of Boolean functions for which it is easy to decide many problems which are intractable for general Boolean functions. In our article we show that positive interval functions are a proper subset of positive threshold functions. Then we prove one property of 2-monotonic functions which is related to testing whether a 2-monotonic function is an interval function. Based on this we construct an algorithm which recognizes in linear time whether given positive threshold function is a positive interval function.
Czech name
Intervalové reprezentace 2-monotonních a prahových booleovských funkcí
Czech description
Prahové, 2-monotonní a intervalové booleovské funkce tvoří speciální třídy booleovských funkcí, pro které je snadné rozhodnout mnoho problémů, které jsou nezvládnutelné pro obecné booleovské funkce. V článku ukazujeme, že positivní intervalové funkce jsou vlastní podmnožinou positivních prahových funkcí. Potom dokážeme vlastnost 2-monotonních funkcí vztahující se k testování, zda je daná 2-monotonní funkce také funkcí intervalovou. Dále prezentujeme algoritmus, který na základě této vlastnosti v lineárním času zjistí, zda daná positivní prahová funkce je intervalová.

Project
<a href="/en/project/GD201%2F05%2FH014" target="_blank" >GD201/05/H014: Collegium Informaticum</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2006
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proceedings of the 15th Annual Conference of Doctoral Students - WDS 2006
ISBN
80-86732-84-3
ISSN
—
e-ISSN
—
Number of pages
5
Pages from-to
167-171
Publisher name
MATFYZPRESS
Place of publication
Praha
Event location
Praha
Event date
Jan 1, 2006
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)