This article is cited in 1 scientific paper (total in 1 paper)
The fundamental difference between depth and delay
V. M. Khrapchenko
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,…$, 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”.
PDF file (187 kB)
Discrete Mathematics and Applications, 2008, 18:4, 391–412
V. M. Khrapchenko, “The fundamental difference between depth and delay”, Diskr. Mat., 20:3 (2008), 51–72; Discrete Math. Appl., 18:4 (2008), 391–412
Citation in format AMSBIB
\paper The fundamental difference between depth and delay
\jour Diskr. Mat.
\jour Discrete Math. Appl.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
A. D. Korshunov, “Computational complexity of Boolean functions”, Russian Math. Surveys, 67:1 (2012), 93–165
|Number of views:|