Generating Boolean \mu-expressions |
| |
Authors: | Thomas Eiter |
| |
Affiliation: | (1) Information Systems Department, Technical University of Vienna, Paniglgasse 16, A-1040 Vienna, Austria |
| |
Abstract: | In this paper, we consider the class of Boolean -functions, which are the Boolean functions definable by -expressions (Boolean expressions in which no variable occurs more than once). We present an algorithm which transforms a Boolean formulaE into an equivalent -expression-if possible-in time linear in E times
, where E is the size ofE andn
m
is the number of variables that occur more than once inE. As an application, we obtain a polynomial time algorithm for Mundici's problem of recognizing -functions fromk-formulas 17]. Furthermore, we show that recognizing Boolean -functions is co-NP-complete for functions essentially dependent on all variables and we give a bound close to co-NP for the general case. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|