Geodesic
On the structure, complexity, and depth of the circuits over the basis $\{ \, \vee\} $ realizing step Boolean functions
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 162 (2020) no. 3, pp. 335-349 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The step Boolean function is a function of the algebra of logic of $n$ Boolean variables, $n =1,2,\ldots$, reducing to $1$ on all of the sets of an $n$-dimensional unit cube, the ordinal numbers of which are not lower than the given set. In this paper, the problem of synthesis of circuits over the basis $\{ \&, \vee\} $ realizing step Boolean functions was considered. The optimized structure of the given circuits was studied with regard to complexity and depth. Step functions often appear in theoretical and applied tasks as an auxiliary subfunctions. For instance, an $n$-bit adder contains such a subfunction.
Keywords: Boolean circuits, basis $\{ \&, \vee\} $, step Boolean functions, complexity and depth minimization, structure of minimal circuits. 
@article{UZKU_2020_162_3_a7,
     author = {S. A. Lozhkin and D. S. Kinzhikeyeva},
     title = {On the structure, complexity, and depth of the circuits over the basis $\{ \&, \vee\} $ realizing step {Boolean} functions},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {335--349},
     year = {2020},
     volume = {162},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a7/}
}
TY  - JOUR
AU  - S. A. Lozhkin
AU  - D. S. Kinzhikeyeva
TI  - On the structure, complexity, and depth of the circuits over the basis $\{ \&, \vee\} $ realizing step Boolean functions
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2020
SP  - 335
EP  - 349
VL  - 162
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a7/
LA  - ru
ID  - UZKU_2020_162_3_a7
ER  - 
%0 Journal Article
%A S. A. Lozhkin
%A D. S. Kinzhikeyeva
%T On the structure, complexity, and depth of the circuits over the basis $\{ \&, \vee\} $ realizing step Boolean functions
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2020
%P 335-349
%V 162
%N 3
%U http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a7/
%G ru
%F UZKU_2020_162_3_a7
S. A. Lozhkin; D. S. Kinzhikeyeva. On the structure, complexity, and depth of the circuits over the basis $\{ \&, \vee\} $ realizing step Boolean functions. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 162 (2020) no. 3, pp. 335-349. http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a7/

[1] Khrapchenko V. M., “Asymptotic estimation of addition time of a parallel adder”, Probl. Kibern., 19, 1967, 107–122 (In Russian)

[2] Grinchuk M. I., “Sharpening an upper bound on the adder and comparator depths”, J. Appl. Ind. Math., 3:1, 61–67 | DOI | MR | MR | Zbl

[3] Lupanov O. B., Asymptotic Estimates of Complexity of Control Systems, Izd. Mosk. Univ., M., 1989, 138 pp. (In Russian)

[4] Lozhkin S. A., Lectures on Principles of Cybernetics, Izd. Otd. Fak. VMiK MGU, M., 2004, 253 pp. (In Russian)

[5] Lozhkin S. A., Kinzhikeyeva D. S., “On the structure, complexity, and depth of the circuits over the basis $\{ \, \vee\} $ realizing step Boolean functions”, Problems of Theoretical Cybernetics, Proc. Virtual Semin. XIX Int. Conf., ed. Zhuravlev Yu.I., Izd. Kazan. Univ., Kazan, 2020, 72–75 (In Russian) | MR

[6] Kinzhikeyeva D. S., Methods for synthesis of circuits from certain classes realizing step functions, estimates of their complexity and depth, Master's Thesis, Mosk. Gos. Univ. im. M.V. Lomonosova, Fak. Vychisl. Mat. Kibern., Kafedra Mat. Kibern., M., 2020, 27 pp. (In Russian)

[7] Vlaskin V. M., On the complexity and depth of circuits realizing step functions, Graduation Thesis, Mosk. Gos. Univ. im. M.V. Lomonosova, Fak. Vychisl. Mat. Kibern., Kafedra Mat. Kibern., M., 1995, 13 pp. (In Russian)