Publikace na Matematicko-fyzikální fakulta |
2006
Abstrakt
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á.