TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

On the arity gap of finite functions: Results and applications

Tutkimustuotos: Katsausartikkelivertaisarvioitu

Standard

On the arity gap of finite functions : Results and applications. / Couceiro, Miguel; Lehtonen, Erkko.

julkaisussa: Journal of Multiple-Valued Logic and Soft Computing, Vuosikerta 27, Nro 2-3, 2016, s. 193-207.

Tutkimustuotos: Katsausartikkelivertaisarvioitu

Harvard

Couceiro, M & Lehtonen, E 2016, 'On the arity gap of finite functions: Results and applications', Journal of Multiple-Valued Logic and Soft Computing, Vuosikerta. 27, Nro 2-3, Sivut 193-207.

APA

Couceiro, M., & Lehtonen, E. (2016). On the arity gap of finite functions: Results and applications. Journal of Multiple-Valued Logic and Soft Computing, 27(2-3), 193-207.

Vancouver

Couceiro M, Lehtonen E. On the arity gap of finite functions: Results and applications. Journal of Multiple-Valued Logic and Soft Computing. 2016;27(2-3):193-207.

Author

Couceiro, Miguel ; Lehtonen, Erkko. / On the arity gap of finite functions : Results and applications. Julkaisussa: Journal of Multiple-Valued Logic and Soft Computing. 2016 ; Vuosikerta 27, Nro 2-3. Sivut 193-207.

Bibtex - Lataa

@article{63db159c74534ef0a4b9f53685018f7c,
title = "On the arity gap of finite functions: Results and applications",
abstract = "Let A be a finite set and B an arbitrary set with at least two elements. The arity gap of a function f : An → B is the minimum decrease in the number of essential variables when essential variables of f are identified. A non- Trivial fact is that the arity gap of such B-valued functions on A is at most |A|. Even less trivial to verify is the fact that the arity gap of B-valued functions on A with more than |A| essential variables is at most 2. These facts ask for a classification of B-valued functions on A in terms of their arity gap. In this paper, we survey what is known about this problem. We present a general characterization of the arity gap of B-valued functions on A and provide explicit classifications of the arity gap of Boolean and pseudo-Boolean functions. Moreover, we reveal unsettled questions related to this topic, and discuss links and possible applications of some results to other subjects of research.",
author = "Miguel Couceiro and Erkko Lehtonen",
year = "2016",
language = "English",
volume = "27",
pages = "193--207",
journal = "Journal of Multiple-Valued Logic and Soft Computing",
issn = "1542-3980",
publisher = "Old City Publishing",
number = "2-3",

}

RIS (suitable for import to EndNote) - Lataa

TY - JOUR

T1 - On the arity gap of finite functions

T2 - Results and applications

AU - Couceiro, Miguel

AU - Lehtonen, Erkko

PY - 2016

Y1 - 2016

N2 - Let A be a finite set and B an arbitrary set with at least two elements. The arity gap of a function f : An → B is the minimum decrease in the number of essential variables when essential variables of f are identified. A non- Trivial fact is that the arity gap of such B-valued functions on A is at most |A|. Even less trivial to verify is the fact that the arity gap of B-valued functions on A with more than |A| essential variables is at most 2. These facts ask for a classification of B-valued functions on A in terms of their arity gap. In this paper, we survey what is known about this problem. We present a general characterization of the arity gap of B-valued functions on A and provide explicit classifications of the arity gap of Boolean and pseudo-Boolean functions. Moreover, we reveal unsettled questions related to this topic, and discuss links and possible applications of some results to other subjects of research.

AB - Let A be a finite set and B an arbitrary set with at least two elements. The arity gap of a function f : An → B is the minimum decrease in the number of essential variables when essential variables of f are identified. A non- Trivial fact is that the arity gap of such B-valued functions on A is at most |A|. Even less trivial to verify is the fact that the arity gap of B-valued functions on A with more than |A| essential variables is at most 2. These facts ask for a classification of B-valued functions on A in terms of their arity gap. In this paper, we survey what is known about this problem. We present a general characterization of the arity gap of B-valued functions on A and provide explicit classifications of the arity gap of Boolean and pseudo-Boolean functions. Moreover, we reveal unsettled questions related to this topic, and discuss links and possible applications of some results to other subjects of research.

UR - http://www.scopus.com/inward/record.url?scp=84979953947&partnerID=8YFLogxK

M3 - Review Article

VL - 27

SP - 193

EP - 207

JO - Journal of Multiple-Valued Logic and Soft Computing

JF - Journal of Multiple-Valued Logic and Soft Computing

SN - 1542-3980

IS - 2-3

ER -