×

zbMATH — the first resource for mathematics

Lower bounds on the multiplicative complexity of symbolic sequences determined by monotone symmetric Boolean functions. (Russian) Zbl 0931.68082
Schemata of the concatenation which realize binary words determined by monotone symmetric Boolean functions (and elementary symmetric Boolean functions) are considered. The lower bounds obtained are equal to the known upper bounds up to a constant.
MSC:
68R15 Combinatorics on words
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
68Q45 Formal languages and automata
PDF BibTeX XML Cite