Intervalová rozšíření částečně definovaných booleovských funkcí

Abstrakt

Intervalové funkce tvoří speciální podtřídu booleovských funkcí, pro které je snadné a rychlé zjistit jejich funkční hodnotu na vstupním vektoru. Jejich hodnota je true, pokud vstupní vektor reprezentuje číslo z intervalu [a,b]. Částečně definovaná booleovská funkce je dvojice (T,F) množin vektorů reprezentujících truepointy, resp. falsepointy.

V článku se zabýváme problémem hledání intervalového rozšíření dané pdBf, tedy intervalové funkce, která se s shoduje s pdBf v jejích truepointech i falsepointech. Sestrojíme polynomiální algoritmus řešící tento problém.

Klíčová slova

• Interval
• Extensions
• Partially
• Defined
• Boolean
• Functions