We observe a number of connections between recent developments in the study of constraint satisfaction problems, irredundant axiomatisation and the study of topological quasivarieties. Several restricted forms of a conjecture of Clark, Davey, Jackson and Pitkethly are solved: for example we show that if, for a finite relational structure M, the class of M-colourable structures has no finite axiomatisation in first order logic, then there is no set (even infinite) of first order sentences characterising the continuously M-colourable structures amongst compact (...) totally disconnected relational structures. We also refute a rather old conjecture of Gorbunov by presenting a finite structure with an infinite irredundant quasi-identity basis. (shrink)

In this article we establish the undecidability of representability and of finite representability as algebras of binary relations in a wide range of signatures. In particular, representability and finite representability are undecidable for Boolean monoids and lattice ordered monoids, while representability is undecidable for Jónsson's relation algebra. We also establish a number of undecidability results for representability as algebras of injective functions.

Let S be a signature of operations and relations definable in relation algebra, let R be the class of all S-structures isomorphic to concrete algebras of binary relations with concrete interpretations for symbols in S, and let F be the class of S-structures isomorphic to concrete algebras of binary relations over a finite base. To prove that membership of R or F for finite S-structures is undecidable, we reduce from a known undecidable problem—here we use the tiling problem, the partial (...) group embedding problem and the partial group finite embedding problem to prove undecidability of finite membership of R or F for various signatures S. It follows that the equational theory of R is undecidable whenever S includes the boolean operators and composition. We give an exposition of the reduction from the tiling problem and the reduction from the group embedding problem, and summarize what we know about the undecidability of finite membership of R and of F for different signatures S. (shrink)

We describe which subdirectly irreducible flat algebras arise in the variety generated by an arbitrary class of flat algebras with absorbing bottom element. This is used to give an elementary translation of the universal Horn logic of algebras, and more generally still, partial structures into the equational logic of conventional algebras. A number of examples and corollaries follow. For example, the problem of deciding which finite algebras of some fixed type have a finite basis for their quasi-identities is shown to (...) be equivalent to the finite identity basis problem for the finite members of a finitely based variety with definable principal congruences. (shrink)

We provide complete classifications of algebras of partial maps for a significant swathe of combinations of operations not previously classified. Our focus is the many subsidiary operations that arise in recent considerations of the ‘override’ and ‘update’ operations arising in specification languages. These other operations turn out to have an older pedigree: domain restriction, set subtraction and intersection. All signatures considered include domain restriction, at least as a term. Combinations of the operations are classified and given complete axiomatizations with and (...) without the presence of functional composition. Each classification is achieved by way of providing a concrete representation of the corresponding abstract algebras as partial maps acting on special kinds of filters determined with respect to various induced orders. In contrast to many negative results in the broader area, all of the considered combinations lead to finite axiomatizations. (shrink)