19 citations · 81 across the 20 of their papers we have counts for
24 papers
Finite model theory for pseudovarieties and universal algebra: preservation, definability and complexity
Lucy Ham, Marcel Jackson
We explore new interactions between finite model theory and classical streams of universal algebra and semigroup theory. A key result is an example of finite algebras whose variety…
Flat extensions of groups and limit varieties of ai-semirings
Miaomiao Ren, Marcel Jackson, Xianzhong Zhao +1
The present paper is a continuation of \cite{jrz} and is devoted to the study of limit varieties of additively idempotent semirings. A limit variety is a nonfinitely based variety…
Qualitative representations of chromatic algebras
Badriah Al Juaid, Marcel Jackson, James Koussas +1
Conventional Ramsey-theoretic investigations for edge-colourings of complete graphs are framed around avoidance of certain configurations. Motivated by considerations arising in th…
Nonfinitely based ai-semirings with finitely based semigroup reducts
Marcel Jackson, Miaomiao Ren, Xianzhong Zhao
We present some general results implying nonfinite axiomatisability of many additively idempotent semirings with finitely based semigroup reducts. The smallest is a -element com…
Restriction in Program Algebra
Marcel Jackson, Tim Stokes
We present axiomatisations for a number of partial function signatures that include domain restriction, modelled as a right normal band operation. Other operations considered are o…
From to to
Marcel Jackson, Wen Ting Zhang
The variety generated by the Brandt semigroup can be defined within the variety generated by the semigroup by the single identity . Ed…
Override and update
Marcel Jackson, Tim Stokes
Override and update are natural constructions for combining partial functions, which arise in various program specification contexts. We use an unexpected connection with combinato…
Domain and range for angelic and demonic compositions
Marcel Jackson, Szabolcs Mikulas
We give finite axiomatizations for the varieties generated by representable domain--range algebras when the semigroup operation is interpreted as angelic or demonic composition, re…
Algebras defined by equations
Peter M Higgins, Marcel Jackson
We show that a class of algebras is closed under the taking of homomorphic images and direct products if and only if the class consists of all algebras that satisfy a set of (gener…
Axiomatisability and hardness for universal Horn classes of hypergraphs
Lucy Ham, Marcel Jackson
We characterise finite axiomatisability and intractability of deciding membership for universal Horn classes generated by finite loop-free hypergraphs.
All or nothing: toward a promise problem dichotomy for constraint problems
Lucy Ham, Marcel Jackson
A finite constraint language is a finite set of relations over some finite domain . We show that intractability of the constraint satisfaction problem $\operatorna…
Low growth equational complexity
Marcel Jackson
The equational complexity function of an equational class of algebras bounds the size of equation required to determine member…
Algebraic foundations for qualitative calculi and networks
Robin Hirsch, Marcel Jackson, Tomasz Kowalski
A qualitative representation is like an ordinary representation of a relation algebra, but instead of requiring , as we do for ordinary representations, we…
On the atoms of algebraic lattices arising in -theory
Attila Egri-Nagy, Marcel Jackson, John Rhodes +1
We determine many of the atoms of the algebraic lattices arising in -theory of finite semigroups.
Flexible constraint satisfiability and a problem in semigroup theory
Marcel Jackson
We examine some flexible notions of constraint satisfaction, observing some relationships between model theoretic notions of universal Horn class membership and robust satisfiabili…
Infinite irredundant equational axiomatisability for a finite monoid
Marcel Jackson
It is shown that a finite monoid can have an infinite irredundant basis of equations.
Monoid varieties with extreme properties
Marcel Jackson, Edmond W. H. Lee
Finite monoids that generate monoid varieties with uncountably many subvarieties seem rare, and surprisingly, no finite monoid is known to generate a monoid variety with countably…
The algebra of functions with antidomain and range
Robin Hirsch, Marcel Jackson, Szabolcs Mikulás
We give complete, finite quasiequational axiomatisations for algebras of unary partial functions under the operations of composition, domain, antidomain, range and intersection. Th…
Monoids with tests and the algebra of possibly non-halting programs
Marcel Jackson, Tim Stokes
We study the algebraic theory of computable functions, which can be viewed as arising from possibly non-halting computer programs or algorithms, acting on some state space, equippe…
Natural dualities, nilpotence and projective planes
Marcel Jackson
We use an interpretation of projective planes to show the inherent nondualisability of some finite semigroups. The method is sufficiently flexible to demonstrate the nondualisabili…
A finer reduction of constraint problems to digraphs
Jakub Bulín, Dejan Delic, Marcel Jackson +1
It is well known that the constraint satisfaction problem over a general relational structure A is polynomial time equivalent to the constraint problem over some associated digraph…
On the reduction of the CSP dichotomy conjecture to digraphs
Jakub Bulin, Dejan Delic, Marcel Jackson +1
It is well known that the constraint satisfaction problem over general relational structures can be reduced in polynomial time to digraphs. We present a simple variant of such a re…
Complexity and polymorphisms for digraph constraint problems under some basic constructions
Marcel Jackson, Tomasz Kowalski, Todd Niven
The role of polymorphisms in determining the complexity of constraint satisfaction problems is well established. In this context we study the stability of CSP complexity and polymo…
The algebra of adjacency patterns: Rees matrix semigroups with reversion
Marcel Jackson, Mikhail Volkov
We establish a surprisingly close relationship between universal Horn classes of directed graphs and varieties generated by so-called adjacency semigroups which are Rees matrix sem…