BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Marcel Jackson

Marcel Jackson appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.LOmath.COLogic in Computer Sciencemath.GRComputational ComplexityDiscrete MathematicsArtificial Intelligence

Catalog footprint

What is connected

17works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

17 published item(s)

preprint2022arXiv

Flat extensions of groups and limit varieties of ai-semirings

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 whose proper subvarieties are all finitely based. We present concrete constructions for one infinite family of limit additively idempotent semiring varieties, and one further ad hoc example. Each of these examples can be generated by a finite flat semiring, with the infinite family arising by a way of a complete characterisation of limit varieties that can be generated by the flat extension of a finite group. We also demonstrate the existence of other examples of limit varieties of additively idempotent semirings, including one further continuum-sized family, each with no finite generator, and two further ad hoc examples. While an explicit description of these latter examples is not given, one of the examples is proved to contain only trivial flat semirings.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Qualitative representations of chromatic algebras

Conventional Ramsey-theoretic investigations for edge-colourings of complete graphs are framed around avoidance of certain configurations. Motivated by considerations arising in the field of Qualitative Reasoning, we explore edge colourings that in addition to forbidding certain triangle configurations also require others to be present. These conditions have natural combinatorial interest in their own right, but also correspond to qualitative representability of certain nonassociative relation algebras, which we will call chromatic.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Low growth equational complexity

The equational complexity function $β_\mathscr{V}:\mathbb{N}\to\mathbb{N}$ of an equational class of algebras $\mathscr{V}$ bounds the size of equation required to determine membership of $n$-element algebras in $\mathscr{V}$. Known examples of finitely generated varieties $\mathscr{V}$ with unbounded equational complexity have growth in $Ω(n^c)$, usually for $c\geq \frac{1}{2}$. We show that much slower growth is possible, exhibiting $O(\log_2^3(n))$ growth amongst varieties of semilattice ordered inverse semigroups and additive idempotent semirings. We also examine a quasivariety analogue of equational complexity, and show that a finite group has polylogarithmic quasi-equational complexity function, bounded if and only if all Sylow subgroups are abelian.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

From $A$ to $B$ to $Z$

The variety generated by the Brandt semigroup ${\bf B}_2$ can be defined within the variety generated by the semigroup ${\bf A}_2$ by the single identity $x^2y^2\approx y^2x^2$. Edmond Lee asked whether or not the same is true for the monoids ${\bf B}_2^1$ and ${\bf A}_2^1$. We employ an encoding of the homomorphism theory of hypergraphs to show that there is in fact a continuum of distinct subvarieties of ${\bf A}_2^1$ that satisfy $x^2y^2\approx y^2x^2$ and contain ${\bf B}_2^1$. A further consequence is that the variety of ${\bf B}_2^1$ cannot be defined within the variety of ${\bf A}_2^1$ by any finite system of identities. Continuing downward, we then turn to subvarieties of ${\bf B}_2^1$. We resolve part of a further question of Lee by showing that there is a continuum of distinct subvarieties all satisfying the stronger identity $x^2y\approx yx^2$ and containing the monoid $M({\bf z}_\infty)$, where ${\bf z}_\infty$ denotes the infinite limit of the Zimin words ${\bf z}_0=x_0$, ${\bf z}_{n+1}={\bf z}_n x_{n+1}{\bf z}_n$.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Algebras defined by equations

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 (generally simultaneous) equations. For classes of regular semigroups in particular this allows an interpretation of a universal algebraic nature that is formulated entirely in terms of the associative binary operation of the semigroup, which serves as an alternative to the approach via so called e-varieties. In particular we prove that classes of Inverse semigroups, Orthodox semigroups, and $E$-solid semigroups are equational in our sense.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Algebraic foundations for qualitative calculi and networks

A qualitative representation $ϕ$ is like an ordinary representation of a relation algebra, but instead of requiring $(a; b)^ϕ= a^ϕ| b^ϕ$, as we do for ordinary representations, we only require that $c^ϕ\supseteq a^ϕ| b^ϕ\iff c\geq a ; b$, for each $c$ in the algebra. A constraint network is qualitatively satisfiable if its nodes can be mapped to elements of a qualitative representation, preserving the constraints. If a constraint network is satisfiable then it is clearly qualitatively satisfiable, but the converse can fail. However, for a wide range of relation algebras including the point algebra, the Allen Interval Algebra, RCC8 and many others, a network is satisfiable if and only if it is qualitatively satisfiable. Unlike ordinary composition, the weak composition arising from qualitative representations need not be associative, so we can generalise by considering network satisfaction problems over non-associative algebras. We prove that computationally, qualitative representations have many advantages over ordinary representations: whereas many finite relation algebras have only infinite representations, every finite qualitatively representable algebra has a finite qualitative representation; the representability problem for (the atom structures of) finite non-associative algebras is NP-complete; the network satisfaction problem over a finite qualitatively representable algebra is always in NP; the validity of equations over qualitative representations is co-NP-complete. On the other hand we prove that there is no finite axiomatisation of the class of qualitatively representable algebras.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Complexity and polymorphisms for digraph constraint problems under some basic constructions

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 polymorphism properties under some basic graph theoretic constructions. As applications we observe a collapse in the applicability of algorithms for CSPs over directed graphs with both a total source and a total sink: the corresponding CSP is solvable by the "few subpowers algorithm" if and only if it is solvable by a local consistency check algorithm. Moreover, we find that the property of "strict width" and solvability by few subpowers are unstable under first order reductions. The analysis also yields a complete characterisation of the main polymorphism properties for digraphs whose symmetric closure is a complete graph.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Monoids with tests and the algebra of possibly non-halting programs

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, equipped with operations of composition, {\em if-then-else} and {\em while-do} defined in terms of a Boolean algebra of conditions. It has previously been shown that there is no finite axiomatisation of algebras of partial functions under these operations alone, and this holds even if one restricts attention to transformations (representing halting programs) rather than partial functions, and omits {\em while-do} from the signature. In the halting case, there is a natural "fix", which is to allow composition of halting programs with conditions, and then the resulting algebras admit a finite axiomatisation. In the current setting such compositions are not possible, but by extending the notion of {\em if-then-else}, we are able to give finite axiomatisations of the resulting algebras of (partial) functions, with {\em while-do} in the signature if the state space is assumed finite. The axiomatisations are extended to consider the partial predicate of equality. All algebras considered turn out to be enrichments of the notion of a (one-sided) restriction semigroup.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Natural dualities, nilpotence and projective planes

We use an interpretation of projective planes to show the inherent nondualisability of some finite semigroups. The method is sufficiently flexible to demonstrate the nondualisability of (asymptotically) almost all finite semigroups as well as to give a fresh proof of the Quackenbush-Szabó result that any finite group with a nonabelian Sylow subgroup is nondualisable. A novel feature is that the ostensibly different notions of nilpotence for semigroups, nilpotence for groups, and the property of being nonorthodox for a completely 0-simple semigroup are unified by way of a single construction. We also give a semigroup example of two dualisable finite semigroups whose direct product is inherently nondualisable.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The algebra of functions with antidomain and range

We give complete, finite quasiequational axiomatisations for algebras of unary partial functions under the operations of composition, domain, antidomain, range and intersection. This completes the extensive programme of classifying algebras of unary partial functions under combinations of these operations. We look at the complexity of the equational theories and provide a nondeterministic polynomial upper bound. Finally we look at the problem of finite representability and show that finite algebras can be represented as a collection of unary functions over a finite base set provided that intersection is not in the signature.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the reduction of the CSP dichotomy conjecture to digraphs

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 reduction and use it to show that the algebraic dichotomy conjecture is equivalent to its restriction to digraphs and that the polynomial reduction can be made in logspace. We also show that our reduction preserves the bounded width property, i.e., solvability by local consistency methods. We discuss further algorithmic properties that are preserved and related open problems.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

The algebra of adjacency patterns: Rees matrix semigroups with reversion

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 semigroups over the trivial group with the unary operation of reversion. In particular, the lattice of subvarieties of the variety generated by adjacency semigroups that are regular unary semigroups is essentially the same as the lattice of universal Horn classes of reflexive directed graphs. A number of examples follow, including a limit variety of regular unary semigroups and finite unary semigroups with NP-hard variety membership problems.

0 citations0 reviewsNo code linkedOpen access