Properties and applications of monotone Boolean functions and stack filters

We examine various structural properties of idempotent monotone Boolean functions. The free distributive lattice (FDL) provides a useful framework for studying this class of functions. Algorithms for testing functions for idempotence and generating a sub-lattice consisting of reversely symmetric monotone Boolean functions are given. Some classes of functions such as compact functions and matroid functions are studied in the context of partial derivatives of Boolean functions. Finally, a statistical approach provides a method of obtaining an asymptotic formula for the size of the free distributive lattice. The generation and enumeration of FDL is discussed. Next, we introduce a system for machine recognition of musical patterns. The problem is put into a pattern recognition framework in the sense that an error between a target pattern and scanned pattern is minimized. The error takes into account pitch and rhythm information. The pitch error measure consists of an absolute (objective) error and a perceptual error. The latter depends on an algorithm for establishing the tonal context which is based on Krumhansl\u27s key-finding algorithm. The sequence of maximum correlations that it outputs is smoothed with a cubic spline and is used to determine weights for perceptual and absolute pitch errors. Statistically significant maximum correlations are used to create the assigned key sequence, which is then median filtered to improve the structure of the output of the key finding algorithm. Several examples are presented and various applications of this system are discussed. Finally, connections between complexity of rhythm patterns and free distributive lattices are discussed