k-DNF a acyklická rozšíření částečně definovaných booleovských funkcí

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F05%3A00000679" target="_blank" >RIV/00216208:11320/05:00000679 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

k-DNF and Acyclic Extensions of pdBfs

Popis výsledku v původním jazyce

The problem of finding an extension of a partially defined Boolean function (pdBf) is the problem of finding a Boolean function, which correctly classifies given data. That means that in general we are given two sets of Boolean vectors - truepoints and falsepoints - and we want to decide if there exists an extension - a Boolean function, that on all given truepoints has function value true and on all given falsepoints has function value false. In the case of positive answer we also want to find some representation of some extension. In our contribution we will show that it is NP-complete to decide whether there exists an acyclic extension for a given pdBf. We will also present a polynomial algorithm for finding a k-DNF extension (for fixed k) and provethat with respect to asymptotic time complexity it is the optimal procedure for solving this problem.

Název v anglickém jazyce

k-DNF and Acyclic Extensions of pdBfs

Popis výsledku anglicky

The problem of finding an extension of a partially defined Boolean function (pdBf) is the problem of finding a Boolean function, which correctly classifies given data. That means that in general we are given two sets of Boolean vectors - truepoints and falsepoints - and we want to decide if there exists an extension - a Boolean function, that on all given truepoints has function value true and on all given falsepoints has function value false. In the case of positive answer we also want to find some representation of some extension. In our contribution we will show that it is NP-complete to decide whether there exists an acyclic extension for a given pdBf. We will also present a polynomial algorithm for finding a k-DNF extension (for fixed k) and provethat with respect to asymptotic time complexity it is the optimal procedure for solving this problem.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GD201%2F05%2FH014" target="_blank" >GD201/05/H014: Collegium Informaticum</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2005

Kód důvěrnosti údajů

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

Název statě ve sborníku

MIS 2005

ISBN

80-86732-70-3

ISSN

—

e-ISSN

—

Počet stran výsledku

11

Strana od-do

38-48

Název nakladatele

MFF

Místo vydání

Praha

Místo konání akce

Praha

Datum konání akce

1. 1. 2005

Typ akce podle státní příslušnosti

CST - Celostátní akce

Kód UT WoS článku

—