Decision lists and related Boolean functions

dc.contributor.authorEiter, Thomas
dc.contributor.authorIbaraki, Toshihide
dc.contributor.authorMakino, Kazuhisa
dc.date.accessioned2022-09-12T09:38:46Z
dc.date.available1998-07-13T22:00:00Z
dc.date.available2022-09-12T09:38:46Z
dc.date.issued1998
dc.description.abstractWe consider Boolean functions represented by decision lists, and study their relationships to other classes of Boolean functions. It turns out that the elementary class of 1­decision lists has interesting relationships to independently defined classes such as disguised Horn functions, readonce functions, nested differences of concepts, threshold functions, and 2­monotonic functions. In particular, 1­decision lists coincide with fragments of the mentioned classes. We further investigate the recognition problem for this class, as well as the extension problem in the context of partially defined Boolean functions (pdBfs). We show that finding an extension of a given pdBf in the class of 1­decision lists is possible in linear time. This improves on previous results. Moreover, we present an algorithm for enumerating all such extensions with polynomial delay.en
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:hebis:26-opus-298
dc.identifier.urihttps://jlupub.ub.uni-giessen.de//handle/jlupub/7567
dc.identifier.urihttp://dx.doi.org/10.22029/jlupub-7001
dc.language.isoende_DE
dc.relation.ispartofseriesIFIG Research Report; 9804 / 1998
dc.rightsIn Copyright*
dc.rights.urihttp://rightsstatements.org/page/InC/1.0/*
dc.subject.ddcddc:004de_DE
dc.titleDecision lists and related Boolean functionsen
dc.typeworkingPaperde_DE
local.affiliationFB 07 - Mathematik und Informatik, Physik, Geographiede_DE
local.opus.fachgebietInformatikde_DE
local.opus.id29
local.opus.instituteInstitut für Informatikde_DE

Dateien

Originalbündel
Gerade angezeigt 1 - 1 von 1
Lade...
Vorschaubild
Name:
IfigReport9804.pdf
Größe:
346.81 KB
Format:
Adobe Portable Document Format