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

Preview

Text BGJRZ2017-Functional_clones.pdf - Accepted Version Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (553kB) | Preview

Abstract

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
URI:	http://repository.essex.ac.uk/id/eprint/25616

Actions (login required)

View Item