Generating Boolean \(\mu\)-expressions
type: Item
instance of: scholarly article
title: Generating Boolean \(\mu\)-expressions
zbMATH Open document ID: 0824.68109
author: Thomas Eiter
published in: Acta Informatica
publication date: 1995-06-21T00:00:00Z
review text: We consider the class of Boolean \(\mu\)-functions, which are the Boolean functions definable by \(\mu\)-expressions (Boolean expressions in which no variable occurs more than once). We present an algorithm which transforms a Boolean formula \(E\) into an equivalent \(\mu\)-expression -- if possible -- in time linear in \(\| E \|\) times \(2^{n_ m}\), where \(\| E \|\) is the size of \(E\) and \(n_ m\) is the number of variables that occur more than once in \(E\). As an application, we obtain a polynomial time algorithm for Mundici's problem of recognizing \(\mu\)-functions from \(k\)-formulas. Furthermore, we show that recognizing 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.
Mathematics Subject Classification ID: 68T27
zbMATH DE Number: 766458
zbMATH Keywords: propositional logic
zbMATH Keywords: recognition problem
zbMATH Keywords: polynomial algorithms
zbMATH Keywords: NP- completeness
zbMATH Keywords: Boolean functions
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 766458