Generalizations of Swierczkowski's lemma and the arity gap of finite functions

Details Generalizations of Swierczkowski's lemma and the arity gap of finite functions Generalizations of Swierczkowski's lemma and the arity gap of finite functions

2007-12-11

arxiv.org/abs/0712.1753v2

Mathematics

Combinatorics

11 pages, proofs simplified, contents reorganized

Scientific paper

Swierczkowski's Lemma - as it is usually formulated - asserts that if f is an at least quaternary operation on a finite set A and every operation obtained from f by identifying a pair of variables is a projection, then f is a semiprojection. We generalize this lemma in various ways. First, it is extended to B-valued functions on A instead of operations on A and to essentially at most unary functions instead of projections. Then we characterize the arity gap of functions of small arities in terms of quasi-arity, which in turn provides a further generalization of Swierczkowski's Lemma. Moreover, we explicitly classify all pseudo-Boolean functions according to their arity gap. Finally, we present a general characterization of the arity gaps of B-valued functions on arbitrary finite sets A.

Affiliated with

Also associated with

No associations

Rating

Generalizations of Swierczkowski's lemma and the arity gap of finite functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Generalizations of Swierczkowski's lemma and the arity gap of finite functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generalizations of Swierczkowski's lemma and the arity gap of finite functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-474514