- UHRA Home
- Browsing by Author
Browsing by Author "Martin, Barnaby"
Now showing items 1-4 of 4
-
The complexity of quantified constraints using the algebraic formulation
Carvalho, Catarina; Martin, Barnaby; Zhuk, Dmitriy (2017-11-07) -
The complexity of quantified constraints: Collapsibility, switchability and the algebraic formulation
Carvalho, Catarina; Madelaine, Florent; Martin, Barnaby; Zhuk, Dmitriy (2023-01-18)Let A be an idempotent algebra on a finite domain. By mediating between results of Chen and Zhuk, we argue that if A satisfies the polynomially generated powers property (PGP) and B is a constraint language invariant under ... -
From complexity to algebra and back: : digraph classes, collapsibility and the PGP
Carvalho, Catarina; Madelaine, Florent; Martin, Barnaby (Institute of Electrical and Electronics Engineers (IEEE), 2015-08-03)Inspired by computational complexity results for the quantified constraint satisfaction problem, we study the clones of idem potent polymorphisms of certain digraph classes. Our first results are two algebraic dichotomy, ... -
The lattice and semigroup structure of multipermutations
Carvalho, Catarina; Martin, Barnaby (2021-11-10)We study the algebraic properties of binary relations whose underlying digraph is smooth, that is, has no source or sink. Such objects have been studied as surjective hyper-operations (shops) on the corresponding vertex ...