RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2006 Volume 18, Issue 4, Pages 73–83 (Mi dm73)

This article is cited in 1 paper

On circuits of functional elements of finite depth of branching

D. Yu. Cherukhin


Abstract: We introduce the notion of the depth of branching of a circuit of functional elements and consider classes of circuits of branching depth bounded by a constant. For these classes of circuits over various bases we obtain lower and upper bounds for complexity of a linear Boolean function. We construct infinitely decreasing sequences of measures of complexity for a fixed base and growing branching depth and for a fixed branching depth but varying base.

UDC: 519.7

Received: 15.03.2005

DOI: 10.4213/dm73


 English version:
Discrete Mathematics and Applications, 2006, 16:6, 577–587

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024