On asymptotic estimates of the complexity of circuit realization of languages (Q2563374)

The author introduces a) the notion of complexity for the words in the alphabet \(B=\{ 0,1 \}\) analogously to the case of Boolean functions, and b) Shannon's function for sets of words, i. e. languages. Then the asymptotic equality of the Snannon's function to its lower bound is shown under some sufficient conditions. If the asymptotic equality is true the language is called standard. Sufficient conditions are given for a language to be standard, and two types of languages are shown to be standard.