Compression with wildcards: Abstract simplicial complexes

Marcel Wild

Despite the more handy terminology of abstract simplicial complexes SC, in its core this article is about antitone Boolean functions. Given the maximal faces (=facets) of SC, our main algorithm, called Facets-To-Faces, outputs SC in a compressed format. The degree of compression of Facets-To-Faces, which is programmed in high-level Mathematica code, compares favorably to both the Mathematica command BooleanConvert, and to the BDD's provided by Python. A novel way to calculate the face-numbers from the facets is also presented. Both algorithms can be parallelized and are applicable (e.g.) to reliability analysis, combinatorial topology, and frequent set mining.

Knowledge Graph



Sign up or login to leave a comment