Geodesic
The fundamental difference between depth and delay
Diskretnaya Matematika, Tome 20 (2008) no. 3, pp. 51-72

Voir la notice de l'article provenant de la source Math-Net.Ru

Earlier, it was proved that even for a minimal circuit the delay $T$ could be much less than the depth $D$. Namely, an infinite sequence of minimal circuits was constructed such that $T\log_2D+6$ and $D\to\infty$. This result would be more interesting if the inequality were true for all equivalent minimal circuits. In this paper, we present an infinite sequence of Boolean functions $F_k$, $k=1,2,\dots$, such that any minimal circuit for an arbitrary function $F_k$ has the depth and the delay obeying the inequality $T\log_2D+14$. This research was supported by the Program of Basic Research of Department of Applied Mathematics of Russian Academy of Sciences “Algebraic and Combinatorial Methods of Mathematical Cybernetics”, project “Design and Complexity of Control Systems”. 
@article{DM_2008_20_3_a5,
     author = {V. M. Khrapchenko},
     title = {The fundamental difference between depth and delay},
     journal = {Diskretnaya Matematika},
     pages = {51--72},
     publisher = {mathdoc},
     volume = {20},
     number = {3},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2008_20_3_a5/}
}
TY  - JOUR
AU  - V. M. Khrapchenko
TI  - The fundamental difference between depth and delay
JO  - Diskretnaya Matematika
PY  - 2008
SP  - 51
EP  - 72
VL  - 20
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2008_20_3_a5/
LA  - ru
ID  - DM_2008_20_3_a5
ER  - 
%0 Journal Article
%A V. M. Khrapchenko
%T The fundamental difference between depth and delay
%J Diskretnaya Matematika
%D 2008
%P 51-72
%V 20
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2008_20_3_a5/
%G ru
%F DM_2008_20_3_a5
V. M. Khrapchenko. The fundamental difference between depth and delay. Diskretnaya Matematika, Tome 20 (2008) no. 3, pp. 51-72. http://geodesic.mathdoc.fr/item/DM_2008_20_3_a5/