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. 69, N 3, 2014.].
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.