On the Shannon function for the generation of Boolean matrices
The author establishes asymptotically exact formulas for the complexity (Shannon) functions of generating Boolean \(p\times q\) matrices and symmetric Boolean matrices of order \(q\) that express the number of elements in functional circuits \(S(r,p,q)\) and terms in the corresponding formulas \(F(r,p,q)\) using at most \(r\)-place disjunction and conjunctions. The relation to similar graph complexity problems is mentioned.
scientific article; zbMATH DE number 1256304