Polynomial decomposition of Boolean functions by images of homogeneous operators of nondegenerate functions
A function \(f:\{0,1\}^n\to\{0,1\}\) is said to be degenerate if \(\sum f(\alpha)=0\), where \(\alpha\) runs over \(\{0,1\}^n\) and \(\sum\) denotes the Boolean-ring sum. For each \(i\in\{1,\dots,n\}\), the operators \(p_i\) and \(d_i\) are defined by \[ \begin{aligned} p_if(x_1,\dots,x_n) & = f(x_1,\dots,\overline x_i,\dots, x_n)\qquad\text{and}\\ d_if(x_1,\dots,x_n) & = f(x_1,\dots,x_n)+ f(x_1,\dots,\overline x_i,\dots, x_n),\end{aligned} \] respectively. By a homogeneous operator is meant any composition \(t= t_n\cdots t_1\), where each \(t_i\in\{p_i,d_i,\text{identity}\}\). The authors prove that every Boolean function has a decomposition of the form indicated in the title. The exact result is too technical to be reproduced here. Reviewer's remark. The only non-Russian literature quoted by the authors consists of the well-known papers by Muller and Reed published in 1954.
- scientific article; zbMATH DE number 732057
- Polynomial expansions of Boolean functions in images of nonhomogeneous operators
- A polynomial decomposition of Boolean functions
- Polynomial expansions of Boolean functions with respect to nondegenerate functions
- scientific article; zbMATH DE number 3557812
- scientific article; zbMATH DE number 59496
- Some results on homogeneous symmetric polynomial-like Boolean functions
- scientific article; zbMATH DE number 4202197
- Homogeneous symmetric polynomial-like Boolean functions
- scientific article; zbMATH DE number 3922538
- A polynomial decomposition of Boolean functions
- Nondegenerate normal forms of Boolean functions.
- Polynomial expansions of Boolean functions with respect to nondegenerate functions
- scientific article; zbMATH DE number 732057 (Why is no real title available?)
- Polynomial expansions of Boolean functions in images of nonhomogeneous operators
This page was built for publication: Polynomial decomposition of Boolean functions by images of homogeneous operators of nondegenerate functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q677739)
