Minor complexity of discrete functions. Issue 1 (17th August 2020) - Shtrakov, Slavcho
Abstract : In this paper we study a class of complexity measures, induced by a new data structure for representing k -valued functions (operations), called minor decision diagram. When assigning values to some variables in a function the resulting functions are called subfunctions, and when identifying some variables the resulting functions are called minors. The sets of essential variables in subfunctions of f are called separable in f . We examine the maximal separable subsets of variables and their conjugates, introduced in the paper, proving that each such set has at least one conjugate. The essential arity gap g a p ( f ) of the function f is the minimal number of essential variables in f which become fictive when identifying distinct essential variables in f . We also investigate separable sets of variables in functions with non-trivial arity gap. This allows us to solve several important algebraic, computational and combinatorial problems about the finite-valued functions.