GENERATING BOOLEAN MU-EXPRESSIONS

In this paper, we consider the class of Boolean mu-functions, which ar e the Boolean functions definable by mu-expressions (Boolean expressio ns in which no variable occurs more than once). We present an algorith m which transforms a Boolean formula E into an equivalent mu-expressio n-if possible-in time linear in parallel to E parallel to times 2(nm), where parallel to E parallel to is the size of E and n(m) is the numb er of variables that occur more than once in E. As an application, we obtain a polynomial time algorithm for Mundici's problem of recognizin g mu-functions from k-formulas [17]. Furthermore, we show that recogni zing Boolean mu-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.