JavaScript is disabled for your browser. Some features of this site may not work without it.
Liebe Nutzerinnen und Nutzer in der Zeit von Montag 22.04. 9:00Uhr bis voraussichtlich Mitwoch 24.04. 9:00Uhr ist JLUpub aufgrund von Wartungsarbeiten nicht erreichbar. Danke für Ihr Verständnis.
Dear users, JLUpub will be unavailable from Monday 22.04. 9:00 a.m. until probably Wednesday 24.04. 9:00 a.m. due to maintenance work. Thank you for your understanding.
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.