Symmetric Function Essential Variable Subfunction Identification Minor Essential Arity Gap Gap Index Separable Set
Issue Date:
2012
Publisher:
Institute of Mathematics and Informatics Bulgarian Academy of Sciences
Citation:
Serdica Journal of Computing, Vol. 6, No 4, (2012), 419p-436p
Abstract:
Given an n-ary k-valued function f, gap(f) denotes the essential arity gap of f which is the minimal number of essential variables in f
which become fictive when identifying any two distinct essential variables in f.
In the present paper we study the properties of the symmetric function
with non-trivial arity gap (2 ≤ gap(f)). We prove several results concerning
decomposition of the symmetric functions with non-trivial arity gap with
its minors or subfunctions. We show that all non-empty sets of essential
variables in symmetric functions with non-trivial arity gap are separable. ACM Computing Classification System (1998): G.2.0.