Functional Clones and Expressibility of Partition Functions

Abstract

We study functional clones, which are sets of non-negative pseudo-Boolean functions (functions $\{0,1{\}}^k\to {\mathbb{R}}_{\ge 0}$) closed under (essentially) multiplication, summation and limits. Functional clones naturally form a lattice under set inclusion and are closely related to counting Constraint Satisfaction Problems (CSPs). We identify a sublattice of interesting functional clones and investigate the relationships and properties of the functional clones in this sublattice.

42 pages, 6 figures; minor corrections

References in corpus (2)

• Simple universal models capture all classical spin physics
• Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP

Cited by in corpus (3)

• A full dichotomy for Holant${}^c$, inspired by quantum computation
• Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
• Holant clones and the approximability of conservative holant problems