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. DOI https://doi.org/10.1016/j.tcs.2017.05.001
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. DOI https://doi.org/10.1016/j.tcs.2017.05.001
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. DOI https://doi.org/10.1016/j.tcs.2017.05.001
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: | Unnamed user with email elements@essex.ac.uk |
| Depositing User: | Unnamed user with email elements@essex.ac.uk |
| Date Deposited: | 23 Jul 2021 07:23 |
| Last Modified: | 30 Oct 2024 16:50 |
| URI: | http://repository.essex.ac.uk/id/eprint/25616 |
Available files
Filename: BGJRZ2017-Functional_clones.pdf
Licence: Creative Commons: Attribution-Noncommercial-No Derivative Works 3.0