Decision lists and related Boolean functions
|
Report:
Institut für Informatik, IFIG Research Report 9804, April 1998
Institut:
Institut für Informatik, JLU Giessen, Arndtstr. 2, D-35392 Giessen
Erscheinungsjahr:
1998
Abstract:
We 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 1decision lists has interesting relationships
to independently defined classes such as disguised Horn functions, readonce
functions, nested differences of concepts, threshold functions, and 2monotonic
functions. In particular, 1decision 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 1decision lists is possible in linear
time. This improves on previous results. Moreover, we present an algorithm
for enumerating all such extensions with polynomial delay.
Sprache:
englisch
Dateiformat:
PostScript (gzip compressed)
Sachgruppe der DNB:
28 Informatik
Eingabedatum:
14.07.98
Zurück zum Anfang | Zur "Giessener Elektronischen Bibliothek" |
Fragen und Kommentare an: geb@bibsys.uni-giessen.de | Zuletzt geändert am 17.06.1999 |