Бакоев,
Валентин
(2018)
Ordinances of the vectors of the ndimensional Boolean cube in accordance with their weights
Book of Abstracts of 14SMAK, Kragujevac, Serbia, May 16 – 19, 2018, p. 103; ISBN 9788660090555; https://imi.pmf.kg.ac.rs/kongres
The problem "Given a Boolean function f of n variables by its Truth Table vector, denoted by TT(f). Find (if exists) a vector $\alpha \in \{0,1\}^n$ of minimal (or maximal) weight, such that $f(\alpha)= 1$." arises in computing the algebraic degree of Boolean functions or vectorial Boolean functions called Sboxes. The solutions to this problem have useful generalizations and applications (for example, in generating all subsets of a given set in accordance with their cardinalities, or in generating combinations etc.). To find effective solutions we examine the ways of ordering the vectors of the Boolean cube in accordance with their weights. The notion "kth layer" of the ndimensional Boolean cube is involved in the definition and examination of the "weight order" relation. It is compared with the known relation "precedes". We enumerate the maximum chains for both relations. An algorithm that generates the vectors of the ndimensional Boolean cube in accordance with their weights is developed. The lexicographic order is chosen as a second criterion for an ordinance of the vectors of equal weights. The algorithm arranges the vectors in a unique way called a weightlexicographic order. It is represented by the (serial) numbers of the vectors, instead of the vectors itself. Its time and space complexities are $\Theta (2^n)$, i.e., of linear type with respect to the size of the output. The obtained results are summarized and added as a new sequence (A294648) in the OEIS.
Доклад
Boolean cube, binary vector, serial number, weight, relation, lexicographic order, weight order, maximum chain enumerating, sequence, weightlexicographic order generating
Природни науки, математика и информатика
Природни науки, математика и информатика
Информатика и компютърни науки
Natural sciences, mathematics and informatics
Natural sciences, mathematics and informatics
Informatics and Computer Science
Издадено
21254
Валентин Бакоев
