Essential Arity Gap of Boolean Functions

Shtrakov, Slavcho. "Essential Arity Gap of Boolean Functions." Serdica Journal of Computing 2.3 (2008): 249-266. <http://eudml.org/doc/11465>.

@article{Shtrakov2008,
abstract = {In this paper we investigate the Boolean functions with maximum essential arity gap. Additionally we propose a simpler proof of an important theorem proved by M. Couceiro and E. Lehtonen in [3]. They use Zhegalkin’s polynomials as normal forms for Boolean functions and describe the functions with essential arity gap equals 2. We use to instead Full Conjunctive Normal Forms of these polynomials which allows us to simplify the proofs and to obtain several combinatorial results concerning the Boolean functions with a given arity gap. The Full Conjunctive Normal Forms are also sum of conjunctions, in which all variables occur.},
author = {Shtrakov, Slavcho},
journal = {Serdica Journal of Computing},
keywords = {Essential Variable; Identification Minor; Essential Arity Gap; Boolean function; essential variable; identification minor; essential arity gap},
language = {eng},
number = {3},
pages = {249-266},
publisher = {Institute of Mathematics and Informatics Bulgarian Academy of Sciences},
title = {Essential Arity Gap of Boolean Functions},
url = {http://eudml.org/doc/11465},
volume = {2},
year = {2008},
}

TY - JOUR
AU - Shtrakov, Slavcho
TI - Essential Arity Gap of Boolean Functions
JO - Serdica Journal of Computing
PY - 2008
PB - Institute of Mathematics and Informatics Bulgarian Academy of Sciences
VL - 2
IS - 3
SP - 249
EP - 266
AB - In this paper we investigate the Boolean functions with maximum essential arity gap. Additionally we propose a simpler proof of an important theorem proved by M. Couceiro and E. Lehtonen in [3]. They use Zhegalkin’s polynomials as normal forms for Boolean functions and describe the functions with essential arity gap equals 2. We use to instead Full Conjunctive Normal Forms of these polynomials which allows us to simplify the proofs and to obtain several combinatorial results concerning the Boolean functions with a given arity gap. The Full Conjunctive Normal Forms are also sum of conjunctions, in which all variables occur.
LA - eng
KW - Essential Variable; Identification Minor; Essential Arity Gap; Boolean function; essential variable; identification minor; essential arity gap
UR - http://eudml.org/doc/11465
ER -