Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Hinweis zum Urheberrecht

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URL: http://geb.uni-giessen.de/geb/volltexte/1998/29/


Decision lists and related Boolean functions

Eiter, Thomas ; Ibaraki, Toshihide ; Makino, Kazuhisa


pdf-Format: Dokument 1.pdf (347 KB)
ps gepackt: class="frontdoor">Dokument1.gz (132 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
Universität Justus-Liebig-Universität Gießen
Institut: Institut für Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: ResearchPaper (Forschungsbericht, Arbeitspapier)
Zeitschrift, Serie: IFIG Research Report ; 9804 / 1998
Sprache: Englisch
Erstellungsjahr: 1998
Publikationsdatum: 14.07.1998
Kurzfassung auf Englisch: 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 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.