Research Repository

Functional clones and expressibility of partition functions

Bulatov, Andrei and Goldberg, Leslie Ann and Jerrum, Mark and Richerby, David and Živný, Stanislav (2017) 'Functional clones and expressibility of partition functions.' Theoretical Computer Science, 687. pp. 11-39. ISSN 0304-3975

BGJRZ2017-Functional_clones.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (553kB) | Preview


We study functional clones, which are sets of non-negative pseudo-Boolean functions (functions {0,1}k→R≥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.

Item Type: Article
Uncontrolled Keywords: Functional clones; Expressibility; Partition functions; Constraint satisfaction problems
Divisions: Faculty of Science and Health
Faculty of Science and Health > Computer Science and Electronic Engineering, School of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 23 Jul 2021 07:23
Last Modified: 21 Jan 2022 11:36

Actions (login required)

View Item View Item