Recognition of interval Boolean functions |
| |
Authors: | Ond?ej ?epek David Kronus Petr Ku?era |
| |
Affiliation: | (1) Institute of Finance and Administration (VŠFS), Prague, Czech Republic;(2) Department of Theoretical Computer Science and Mathematical Logic, Faculty of Mathematics and Physics, Charles University, Malostranské náměstí 25, Prague, Czech Republic |
| |
Abstract: | Interval functions constitute a special class of Boolean functions for which it is very easy and fast to determine their functional
value on a specified input vector. The value of an n-variable interval function specified by interval a,b] (where a and b are n-bit binary numbers) is true if and only if the input vector viewed as an n-bit number belongs to the interval a,b]. In this paper we study the problem of deciding whether a given disjunctive normal form represents an interval function
and if so then we also want to output the corresponding interval. For general Boolean functions this problem is co-NP-hard.
In our article we present a polynomial time algorithm which works for monotone functions. We shall also show that given a
Boolean function f belonging to some class which is closed under partial assignment and for which we are able to solve the satisfiability problem in polynomial time,
we can also decide whether f is an interval function in polynomial time. We show how to recognize a “renamable” variant of interval functions, i.e., their
variable complementation closure. Another studied problem is the problem of finding an interval extension of partially defined
Boolean functions. We also study some other properties of interval functions.
|
| |
Keywords: | Boolean function DNF pdBf Knowledge compression |
本文献已被 SpringerLink 等数据库收录! |
|