Description:
In this paper we study a class of complexity measures, induced by a new data structure for representingk-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 offare called separable inf.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 gapgap(f)of the functionfis the minimal number of essential variables infwhich become fictive when identifying distinct essential variables inf. 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.