Title. Automatic complexity of monotone Boolean functions
Speaker. Bjørn Kjos-Hanssen
Institution. Department of Mathematics, University of Hawai’i, HI
Abstract. Champarnaud and Pin (1989) found the maximum complexity, in terms of finite automata, of a Boolean function on n variables. We study the special case of monotone functions. It is inspired by an application to complexity of financial securities. Mathematically we relate it to a certain lattice homomorphism problem.