Complexity of realization of Boolean functions from some classes connected with finite grammars by formulas of alternation depth 3 / S. A. Lozhkin, V. A. Konovodov. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2014. № 3. P. 14-19 [Moscow Univ. Math. Bulletin. Vol. 72, N 2, 2017. P. 0].
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.