RUS  ENG
Full version
JOURNALS // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika // Archive
Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2014 Number 3, Pages 14–19 (Mi vmumm317)
This article is cited in 1 paper

Mathematics

Complexity of realization of Boolean functions from some classes related to finite grammars by formulas of alternation depth $3$

S. A. Lozhkin, V. A. Konovodov

Lomonosov Moscow State University, Faculty of Computational Mathematics and Cybernetics

Abstract: The realization complexity of Boolean functions associated with finite grammars in the class of formulae of alternation depth 3 is studied. High accuracy asymptotic bounds are obtained for the corresponding Shannon function.

Key words: Boolean formulae, complexity, alternation depth, Shannon function, high accuracy asymptotic bounds.

UDC: 519.714

Received: 13.02.2013


 English version: Moscow University Mathematics Bulletin, Moscow University Måchanics Bulletin, 2014, 69:3, 100–105

Bibliographic databases:

© Steklov Math. Inst. of RAS, 2025