Generalized polymorphisms

Publication date 17 May 2023

Abstract: We determine all

m

-ary Boolean functions

f_{0}, l d o t s, f_{m}

and

n

-ary Boolean functions

g_{0}, l d o t s, g_{n}

satisfying the equation [ f_0(g_1(z_{11},ldots,z_{1m}),ldots,g_n(z_{n1},ldots,z_{nm})) = g_0(f_1(z_{11},ldots,z_{n1}),ldots,f_m(z_{1m},ldots,z_{nm})), ] for all Boolean inputs

z_{i j} : i i n [n], j i n [m]

. This extends characterizations by Dokow and Holzman (who considered the case

g_{0} = c d o t s = g_{n}

) and by Chase, Filmus, Minzer, Mossel and Saurabh (who considered the case

g_{1} = c d o t s = g_{n}

).

This page was built for publication: Generalized polymorphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6436933)