|
Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 2009, Number 2, Pages 72–75
(Mi vmumm866)
|
|
|
|
This article is cited in 4 scientific papers (total in 4 papers)
Short notes
Depth of $\alpha$-completions of systems of Boolean functions
D. V. Truschin Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
Abstract:
A problem of implementation of Boolean functions by $\alpha$-formulas is considered. These formulas are such that each subformula contains not more that one nontrivial principal subformula. The depth is considered as a complexity measure of a formula. Upper and lower polynomial estimates of Shannon functions for $\alpha$-supplements of finite systems of Boolean functions are obtained.
Key words:
Boolean function, formula, complexity, depth.
Received: 26.09.2008
Citation:
D. V. Truschin, “Depth of $\alpha$-completions of systems of Boolean functions”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2009, no. 2, 72–75
Linking options:
https://www.mathnet.ru/eng/vmumm866 https://www.mathnet.ru/eng/vmumm/y2009/i2/p72
|
|