On monotone multivalued functions: generating and estimating Dedekind numbers

Abstract

Monotone multivalued functions have been widely employed in discrete mathematics, multivalued logics and reliability theory, in special its particular case of monotone boolean functions. However, our interest in them came from the kind of monotone cellular automata studied in [1, 2, 3, 4, 7, 8, 9, 10, 11, 12, 13], where monotone multivalued functions play a fundamental role. At first, we present an algorithm that generates random examples of monotone multivalued functions. Our second algorithm provide an estimative for the number of monotone multivalued functions, which shall be called here Dedekind number. Our first algorithm provided examples that were used for testing routines that compute Galperin’s rates [9]. Moreover, it will facilitate the inductive reasoning concerning monotone cellular automata.