This article is cited in 3 papers

On the $id$-decompositions of the class $P_k$ over precomplete classes

S. S. Marchenkov


Abstract: We consider a representation of functions $f(x_1,\cdots,x_n)$ in $P_k$ in the form
$$ g(x_1,\dots,x_m,F^1_2,\dots,F^1_m,\dots,F^m_1,\dots,F^m_{m-1}), $$
where $2\le m\le n$ and $F^i_j=f(x_1,\dots,x_{j-1},x_i,x_{j+1},\dots,x_n)$ for $i\ne j$. We investigate the possibility of such representations with $g$ belonging to classes that are precomplete in $P_k$. We give upper bounds on the parameter $m$ in the representation.

UDC: 519.716

Received: 13.12.1991

 English version: Discrete Mathematics and Applications, 1993, 3:6, 587–599

Bibliographic databases:

• 
•