Thumbnail - Request a copy

GAP vs. PAG

Waldhauser, Tamás; Lehtonen, Erkko; Couceiro, Miguel (2012), GAP vs. PAG, ISMVL '12 Proceedings of the 2012 IEEE 42nd International Symposium on Multiple-Valued Logic, IEEE : Washington, p. 268-273. http://dx.doi.org/10.1109/ISMVL.2012.11

Type
Communication / Conférence
Date
2012
Conference title
IEEE 42nd International Symposium on Multiple-Valued Logic (ISMVL2012)
Conference date
2012-05
Conference city
Victoria
Conference country
Canada
Book title
ISMVL '12 Proceedings of the 2012 IEEE 42nd International Symposium on Multiple-Valued Logic
Publisher
IEEE
Published in
Washington
ISBN
978-0-7695-4673-5
Pages
268-273
Publication identifier
Metadata
Show full item record
Author(s)
Waldhauser, Tamás
Lehtonen, Erkko cc
Couceiro, Miguel
Abstract (EN)
We propose a parametrized version of arity gap. The parametrized arity gap gap (f, l) of an n-ary function f measures the minimum decrease in the number of essential variables of f when l consecutive identifications of pairs of essential variables are performed. We determine gap(f, l) for an arbitrary function f and a positive integer l. We also propose other variants of arity gap and discuss further problems pertaining to the effect of identification of variables on the number of essential variables of functions.
Subjects / Keywords
Arity gap; parametrized arity gap; essential variable; simple minor; variable identification minor