- UHRA Home
- Browsing by Author
Browsing by Author "Carvalho, Catarina"
Now showing items 1-18 of 18
-
Bruck-Reilly extensions of direct products of monoids and completely (0-)simple semigroups
Carvalho, Catarina (2009-08) -
Caterpillar duality for constraint satisfaction problems
Carvalho, Catarina; Dalmau, Víctor; Krokhin, Andrei (Institute of Electrical and Electronics Engineers (IEEE), 2008) -
CD(4) has bounded width
Carvalho, Catarina; Dalmau, Víctor; Marković, Petar; Maróti, Miklós (2009)We prove that the constraint languages invariant under a short sequence of J\'onsson terms (containing at most three non-trivial ternary terms) are tractable by showing that they have bounded width. This improves the ... -
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 ... -
CSP duality and trees of bounded pathwidth
Carvalho, Catarina; Dalmau, Víctor; Krokhin, Andrei (2010)We study non-uniform constraint satisfaction problems definable in monadic Datalog stratified by the use of non-linearity. We show how such problems can be described in terms of homomorphism dualities involving trees of ... -
Finite generation of P-semigroups with almost G-invariant idempotents
Carvalho, Catarina (World Scientific Publishing, 2007-06) -
Finite presentability of Bruck-Reilly extensions of Clifford monoids
Carvalho, Catarina (2007-10)Let M be a Clifford monoid and let θ be an endomorphism of M. We prove that if the Bruck–Reilly extension BR(M, θ) is finitely presented then M is finitely generated. This allows us to derive necessary and sufficient ... -
A finitely presented monoid with a non-finitely generated group of units
Carvalho, Catarina; Ruskuc, Nik (2007-08)We exhibit an example of a monoid defined by finitely many generators and defining relations, the group of units of which is not finitely generated -
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 ... -
On Algebras with many symmetric operations
Carvalho, Catarina; Krokhin, Andrei (2016-08-01)We show that, for each finite algebra A, either it has symmetric term operations of all arities or else some finite algebra in the variety generated by A has two automorphisms without a common fixed point. We also show ... -
On finite presentability of Bruck-Reilly extensions of a monoid with respect to an endomorphism and its powers.
Carvalho, Catarina; Ruskuc, Nik (2007-09)Let M be a monoid and let θ be an endomorphism of M. We prove that if the Bruck–Reilly extension BR(M, θ) is finitely presented, then the Bruck–Reilly extension BR(M, θm) is also finitely presented for all m ⩾ 1 -
On Maltsev digraphs
Carvalho, Catarina; Egri, L.; Jackson, M.; Niven, T. (2011)We study digraphs preserved by a Maltsev operation, Maltsev digraphs. We show that these digraphs retract either onto a directed path or to the disjoint union of directed cycles, showing that the constraint satisfaction ... -
On Maltsev Digraphs
Carvalho, Catarina; Egri, Laszlo; Jackson, Marcel; Niven, Todd (2015-02-25)We study digraphs preserved by a Maltsev operation: Maltsev digraphs. We show that these digraphs retract either onto a directed path or to the disjoint union of directed cycles, showing in this way that the constraint ... -
On presentations of Bruck-Reilly extensions
Carvalho, Catarina (2009)We first consider the class of monoids in which every left invertible element is also right invertible, and prove that if a monoid belonging to this class admits a finitely presented Bruck–Reilly extension then it is ... -
Presentations of Inverse Semigroups their Kernels and Extensions
Carvalho, Catarina; Gray, Robert; Ruskuc, Nik (2011)Let S be an inverse semigroup and let π:S→T be a surjective homomorphism with kernel K. We show how to obtain a presentation for K from a presentation for S, and vice versa. We then investigate the relationship between the ... -
Two new homomorphism dualities and lattice operations
Carvalho, Catarina; Dalmau, Victor; Krokhin, Andrei (2011)The study of constraint satisfaction problems definable in various fragments of Datalog has recently gained considerable importance. We consider constraint satisfaction problems that are definable in the smallest natural ...