Minor complexity of discrete functions. Issue 1 (17th August 2020)

• Record Type: Journal Article
• Authors: Shtrakov, Slavcho
• Is Part Of: Applied computing and informatics. Volume 17:Issue 1(2021)
• Page Start: 108
• Page End: 130
• Publication Date: 2020-08-17
• Subjects: Separable set -- Subfunction -- Identification minor -- Minor decision diagram -- Minor complexity; Information science -- Periodicals; Information storage and retrieval systems -- Periodicals; 004
• DOI: 10.1016/j.aci.2018.07.003
• Languages: English
• ISSNs: 2210-8327

Abstract

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.