ORCID Profile
0000-0002-8149-1141
Current Organisation
La Trobe University
Does something not look right? The information on this page has been harvested from data sources that may not be up to date. We continue to work with information providers to improve coverage and quality. To report an issue, use the Feedback Form.
Research Topics
In Research Link Australia (RLA), "Research Topics" refer to ANZSRC FOR and SEO codes. These topics are either sourced from ANZSRC FOR and SEO codes listed in researchers' related grants or generated by a large language model (LLM) based on their publications.
Top 5 Research Topics
ANZSRC Field of Research (FoR)
Pure Mathematics | Combinatorics and Discrete Mathematics (excl. Physical Combinatorics) | Mathematical Logic And Formal Languages | Mathematical Logic, Set Theory, Lattices And Combinatorics | Group Theory and Generalisations | Mathematics Not Elsewhere Classified | Analysis Of Algorithms And Complexity | Mathematical Logic, Set Theory, Lattices and Universal Algebra | Group Theory And Generalisations (Incl. Topological Groups And Lie | Computation Theory and Mathematics | Computational Logic and Formal Languages
ANZSRC Socio-Economic Objective (SEO)
Mathematical sciences | Expanding Knowledge in the Information and Computing Sciences | Expanding Knowledge in the Mathematical Sciences |
Related Links
Publications
INTERPRETING GRAPH COLORABILITY IN FINITE SEMIGROUPS
Publisher: World Scientific Pub Co Pte Lt
Date: 02-2006
DOI: 10.1142/S0218196706002846
Abstract: We show that a number of natural membership problems for classes associated with finite semigroups are computationally difficult. In particular, we construct a 55-element semigroup S such that the finite membership problem for the variety of semigroups generated by S interprets the graph 3-colorability problem.
Undecidable problems for completely 0-simple semigroups
Publisher: Elsevier BV
Date: 10-2009
On Maltsev Digraphs
Publisher: The Electronic Journal of Combinatorics
Date: 25-02-2015
DOI: 10.37236/4419
Abstract: 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 satisfaction problem for Maltsev digraphs is in logspace, L. We then generalize results from Kazda (2011) to show that a Maltsev digraph is preserved not only by a majority operation, but by a class of other operations (e.g., minority, Pixley) and obtain a $O(|V_G|^4)$-time algorithm to recognize Maltsev digraphs. We also prove analogous results for digraphs preserved by conservative Maltsev operations which we use to establish that the list homomorphism problem for Maltsev digraphs is in L. We then give a polynomial time characterisation of Maltsev digraphs admitting a conservative 2-semilattice operation. Finally, we give a simple inductive construction of directed acyclic digraphs preserved by a Maltsev operation, and relate them with series parallel digraphs.
Monoids with tests and the algebra of possibly non-halting programs
Publisher: Elsevier BV
Date: 03-2015
SEMIGROUPS WITH if–then–else AND HALTING PROGRAMS
Publisher: World Scientific Pub Co Pte Lt
Date: 11-2009
DOI: 10.1142/S0218196709005354
Abstract: The "if–then–else" construction is one of the most elementary programming commands, and its abstract laws have been widely studied, starting with McCarthy. Possibly, the most obvious extension of this is to include the operation of composition of programs, which gives a semigroup of functions (total, partial, or possibly general binary relations) that can be recombined using if–then–else. We show that this particular extension admits no finite complete axiomatization and instead focus on the case where composition of functions with predicates is also allowed (and we argue there is good reason to take this approach). In the case of total functions — modeling halting programs — we give a complete axiomatization for the theory in terms of a finite system of equations. We obtain a similar result when an operation of equality test and/or fixed point test is included.
Pathway dynamics can delineate the sources of transcriptional noise in gene expression
Publisher: eLife Sciences Publications, Ltd
Date: 12-10-2021
DOI: 10.7554/ELIFE.69324
Abstract: Single-cell expression profiling opens up new vistas on cellular processes. Extensive cell-to-cell variability at the transcriptomic and proteomic level has been one of the stand-out observations. Because most experimental analyses are destructive we only have access to snapshot data of cellular states. This loss of temporal information presents significant challenges for inferring dynamics, as well as causes of cell-to-cell variability. In particular, we typically cannot separate dynamic variability from within cells (‘intrinsic noise’) from variability across the population (‘extrinsic noise’). Here, we make this non-identifiability mathematically precise, allowing us to identify new experimental set-ups that can assist in resolving this non-identifiability. We show that multiple generic reporters from the same biochemical pathways (e.g. mRNA and protein) can infer magnitudes of intrinsic and extrinsic transcriptional noise, identifying sources of heterogeneity. Stochastic simulations support our theory, and demonstrate that ‘pathway-reporters’ compare favourably to the well-known, but often difficult to implement, dual-reporter method.
Natural dualities, nilpotence and projective planes
Publisher: Springer Science and Business Media LLC
Date: 25-06-2015
Low Growth Equational Complexity
Publisher: Cambridge University Press (CUP)
Date: 25-09-2018
DOI: 10.1017/S0013091518000354
Abstract: The equational complexity function $\\beta \\nu \\,:\\,{\\open N} \\to {\\open N}$ of an equational class of algebras bounds the size of equation required to determine the membership of n -element algebras in . Known ex les of finitely generated varieties with unbounded equational complexity have growth in Ω( n c ), usually for c ≥ (1/2). We show that much slower growth is possible, exhibiting $O(\\log_{2}^{3}(n))$ growth among 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.
A note onHSI-algebras and counterexamples to Wilkie's identity
Publisher: Springer Science and Business Media LLC
Date: 12-1996
DOI: 10.1007/BF01233923
On Maltsev Digraphs
Publisher: Springer Berlin Heidelberg
Date: 2011
The axiomatizability of topological prevarieties
Publisher: Elsevier BV
Date: 08-2008
On the atoms of algebraic lattices arising in 𝔮-theory
Publisher: World Scientific Pub Co Pte Lt
Date: 03-2017
DOI: 10.1142/S0218196717500084
Abstract: We determine many of the atoms of the algebraic lattices arising in [Formula: see text]-theory of finite semigroups.
Agreeable semigroups
Publisher: Elsevier BV
Date: 08-2003
The algebra of functions with antidomain and range
Publisher: Elsevier BV
Date: 06-2016
On the Reduction of the CSP Dichotomy Conjecture to Digraphs
Publisher: Springer Berlin Heidelberg
Date: 2013
The equational complexity of Lyndon’s algebra
Publisher: Springer Science and Business Media LLC
Date: 13-04-2011
A finer reduction of constraint problems to digraphs
Publisher: Centre pour la Communication Scientifique Directe (CCSD)
Date: 29-12-2015
DOI: 10.2168/LMCS-11(4:18)2015
Abstract: 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. We present a variant of this construction and show that the corresponding constraint satisfaction problem is logspace equivalent to that over A. Moreover, we show that almost all of the commonly encountered polymorphism properties are held equivalently on the A and the constructed digraph. As a consequence, the Algebraic CSP dichotomy conjecture as well as the conjectures characterizing CSPs solvable in logspace and in nondeterministic logspace are equivalent to their restriction to digraphs.
The Algebra of Adjacency Patterns: Rees Matrix Semigroups with Reversion
Publisher: Springer Berlin Heidelberg
Date: 2010
The Division Relation: Congruence Conditions and Axiomatisability
Publisher: Informa UK Limited
Date: 12-02-2010
Semilattice Pseudo-complements on Semigroups
Publisher: Informa UK Limited
Date: 31-12-2004
Relatively inherently nonfinitely q-based semigroups
Publisher: American Mathematical Society (AMS)
Date: 25-11-2008
All or Nothing: Toward a Promise Problem Dichotomy for Constraint Problems
Publisher: Springer International Publishing
Date: 2017
Author response: Pathway dynamics can delineate the sources of transcriptional noise in gene expression
Publisher: eLife Sciences Publications, Ltd
Date: 11-08-2021
The embeddability of ring and semigroup amalgams is undecidable
Publisher: Cambridge University Press (CUP)
Date: 10-2000
DOI: 10.1017/S1446788700002214
Abstract: We prove that there is no algorithm to determine when an amalgam of finite rings (or semigroups) can be embedded in the class of rings or in the class of finite rings (respectively, in the class of semigroups or in the class of finite semigroups). These results are in marked contrast with the corresponding problems for groups where every amalgam of finite groups can be embedded in a finite group.
Override and update
Publisher: Elsevier BV
Date: 03-2021
Finiteness Properties of Varieties and the Restriction to Finite Algebras
Publisher: Springer Science and Business Media LLC
Date: 03-2005
From A to B to Z
Publisher: Springer Science and Business Media LLC
Date: 31-03-2021
Algebraic foundations for qualitative calculi and networks
Publisher: Elsevier BV
Date: 05-2019
Constraint Satisfaction, Irredundant Axiomatisability and Continuous Colouring
Publisher: Springer Science and Business Media LLC
Date: 12-06-2013
FINITE SEMIGROUPS WITH INFINITE IRREDUNDANT IDENTITY BASES
Publisher: World Scientific Pub Co Pte Lt
Date: 06-2005
DOI: 10.1142/S0218196705002335
Abstract: We give the first ex les of finite semigroups whose identities have infinite irredundant bases.
An Invitation to C-semigroups
Publisher: Springer Science and Business Media LLC
Date: 2001
Erratum to: Finiteness properties of varieties and the restriction to finite algebras
Publisher: Springer Science and Business Media LLC
Date: 11-05-2017
Semilattices with closure
Publisher: Springer Science and Business Media LLC
Date: 11-2004
Finite Semigroups Whose Varieties Have Uncountably Many Subvarieties
Publisher: Elsevier BV
Date: 06-2000
General Algebra and Its Applications 2013 : Problem Session
Publisher: Springer Science and Business Media LLC
Date: 04-07-2015
MODAL RESTRICTION SEMIGROUPS: TOWARDS AN ALGEBRA OF FUNCTIONS
Publisher: World Scientific Pub Co Pte Lt
Date: 11-2011
DOI: 10.1142/S0218196711006844
Abstract: Restriction semigroups model algebras of partial maps under composition and domain. Here we consider restriction semigroups for which the usual Boolean operations on domains are modeled. Such algebras are capable of modeling the usual modal operators considered in dynamic logic. Indeed adding a natural functional variant of union to the signature gives a deterministic version of the modal semirings of Möller and Struth, but also a monoidal version of the classical restriction categories of Cockett and Manes. Other operations modeled are intersection and (in the finite case) functional iteration. In each case, axiomatizations of the concrete functional ex les are given, leading to algebraic models of partial maps incorporating all the domain-related and set-theoretic operations previously considered. Our algebras furnish natural algebraic semantics for the logics of deterministic computer programs, leading to new results for some variants of propositional dynamic logic.
On locally finite varieties with undecidable equational theory
Publisher: Springer Science and Business Media LLC
Date: 05-2002
DUALISABILITY OF FINITE SEMIGROUPS
Publisher: World Scientific Pub Co Pte Lt
Date: 08-2003
DOI: 10.1142/S0218196703001535
Abstract: We describe the inherently non-dualisable finite algebras from some semigroup related classes. The classes for which this problem is solved include the variety of bands, the pseudovariety of aperiodic monoids, commutative monoids, and (assuming a reasonable conjecture in the literature) the varieties of all finite monoids and finite inverse semigroups. The first ex le of an inherently non-dualisable entropic algebra is also presented.
Pathway dynamics can delineate the sources of transcriptional noise in gene expression
Publisher: Cold Spring Harbor Laboratory
Date: 30-09-2020
DOI: 10.1101/2020.09.30.319814
Abstract: Single-cell expression profiling has opened up new vistas on cellular processes. Among other important results, one stand-out observation has been the confirmation of extensive cell-to-cell variability at the transcriptomic and proteomic level. Because most experimental analyses are destructive we only have access to snapshot data of cellular states. This loss of temporal information presents significant challenges in inferring dynamics, as well as causes of cell-to-cell variability. In particular, we are typically unable to separate dynamic variability from within in idual systems (“intrinsic noise”) from variability across the population (“extrinsic noise”). Here we mathematically formalise this non-identifiability but we also use this to identify how new experimental set-ups coupled to statistical noise decomposition can resolve this non-identifiability. For single-cell transcriptomic data we find that systems subject to population variation invariably inflate the apparent degree of burstiness of the underlying process. Such identifiability problems can, in principle, be remedied by dual-reporter assays, which separates total gene expression noise into intrinsic and extrinsic contributions unfortunately, however, this requires pairs of strictly independent and identical gene reporters to be integrated into the same cell, which is difficult to implement experimentally in most systems. Here we demonstrate mathematically that, in some cases decomposition of transcriptional noise is possible with non-identical and not-necessarily independent reporters. We use our result to show that generic reporters lying in the same biochemical pathways (e.g. mRNA and protein) can replace dual reporters, enabling the noise decomposition to be obtained from only a single gene. Stochastic simulations are used to support our theory, and show that our “pathway-reporter” method compares favourably to the dual-reporter method.
Domain and range for angelic and demonic compositions
Publisher: Elsevier BV
Date: 02-2019
PRINCIPAL AND SYNTACTIC CONGRUENCES IN CONGRUENCE-DISTRIBUTIVE AND CONGRUENCE-PERMUTABLE VARIETIES
Publisher: Cambridge University Press (CUP)
Date: 08-2008
DOI: 10.1017/S144678870800061X
Abstract: We give a new proof that a finitely generated congruence-distributive variety has finitely determined syntactic congruences (or, equivalently, term finite principal congruences), and show that the same does not hold for finitely generated congruence-permutable varieties, even under the additional assumption that the variety is residually very finite.
Axiomatisability and hardness for universal Horn classes of hypergraphs
Publisher: Springer Science and Business Media LLC
Date: 20-04-2018
Small semigroup related structures with infinite properties
Publisher: Cambridge University Press (CUP)
Date: 06-2000
Partial Maps with Domain and Range: Extending Schein's Representation
Publisher: Informa UK Limited
Date: 22-07-2009
Algebras defined by equations
Publisher: Elsevier BV
Date: 08-2020
Undecidability of Algebras of Binary Relations
Publisher: Springer International Publishing
Date: 2021
Flat extensions of groups and limit varieties of additively idempotent semirings
Publisher: Elsevier BV
Date: 06-2023
On representing semigroups with subsemilattices
Publisher: Elsevier BV
Date: 02-2013
Some undecidable embedding problems for finite semigroups
Publisher: Cambridge University Press (CUP)
Date: 02-1999
DOI: 10.1017/S0013091500020058
Abstract: Let S be a finite semigroup, A be a given subset of S and L, R, H, D and J be Green's equivalence relations. The problem of determining whether there exists a supersemigroup T of S from the class of all semigroups or from the class of finite semigroups, such that A lies in an L or R -class of T has a simple and well known solution (see for ex le [7], [8] or [3]). The analogous problem for J or D relations is trivial if T is of arbitrary size, but undecidable if T is required to be finite [4] (even if we restrict ourselves to the case | A | = 2 [6]). We show that for the relation H , the corresponding problem is undecidable in both the class of finite semigroups (answering Problem 1 of [9]) and in the class of all semigroups, extending related results obtained by M. V. Sapir in [9]. An infinite semigroup with a subset never lying in a H -class of any embedding semigroup is known and, in [9], the existence of a finite semigroup with this property is established. We present two eight element ex les of such semigroups as well as other ex les satisfying related properties.
Small inherently nonfinitely based finite semigroups
Publisher: Springer Science and Business Media LLC
Date: 29-08-2001
Monoid varieties with extreme properties
Publisher: American Mathematical Society (AMS)
Date: 18-01-2018
DOI: 10.1090/TRAN/7091
Nonfinitely based ai-semirings with finitely based semigroup reducts
Publisher: Elsevier BV
Date: 12-2022
Flat algebras and the translation of universal Horn logic to equational logic
Publisher: Cambridge University Press (CUP)
Date: 03-2008
Abstract: 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, partial algebras, and more generally still, partial structures into the equational logic of conventional algebras. A number of ex les and corollaries follow. For ex le, 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 finiteiy based variety with definable principal congruences.
Proving symmetries by model transformation
Publisher: Springer Berlin Heidelberg
Date: 2011
Complexity and polymorphisms for digraph constraint problems under some basic constructions
Publisher: World Scientific Pub Co Pte Lt
Date: 11-2016
DOI: 10.1142/S0218196716500600
Abstract: 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 characterization of the main polymorphism properties for digraphs whose symmetric closure is a complete graph.
Mailbox¶Generalising congruence regularity for varieties
Publisher: Springer Science and Business Media LLC
Date: 10-2002
DOI: 10.1007/PL00012452
Edge colourings and qualitative representations of chromatic algebras
Publisher: Springer Science and Business Media LLC
Date: 13-06-2023
DOI: 10.1007/S10801-023-01251-5
Abstract: 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 .
Natural dualities for semilattice-based algebras
Publisher: Springer Science and Business Media LLC
Date: 21-11-2007
Restriction in Program Algebra
Publisher: Oxford University Press (OUP)
Date: 19-07-2022
Abstract: 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.
Finite degree: algebras in general and semigroups in particular
Publisher: Springer Science and Business Media LLC
Date: 08-06-2011
IDENTITIES IN THE ALGEBRA OF PARTIAL MAPS
Publisher: World Scientific Pub Co Pte Lt
Date: 12-2006
DOI: 10.1142/S0218196706003426
Abstract: We consider the identities of a variety of semigroup-related algebras modelling the algebra of partial maps. We show that the identities are intimately related to a weak semigroup deductive system and we show that the equational theory is decidable. We do this by giving a term rewriting system for the variety. We then show that this variety has many subvarieties whose equational theory interprets the full uniform word problem for semigroups and consequently are undecidable. As a corollary it is shown that the equational theory of Clifford semigroups whose natural order is a semilattice is undecidable.
Well-structured program equivalence is highly undecidable
Publisher: Association for Computing Machinery (ACM)
Date: 08-2012
Abstract: We show that strict deterministic propositional dynamic logic with intersection is highly undecidable, solving a problem in the Stanford Encyclopedia of Philosophy. In fact we show something quite a bit stronger. We introduce the construction of program equivalence, which returns the value ⊤ precisely when two given programs are equivalent on halting computations. We show that virtually any variant of propositional dynamic logic has a Π 1 1 -hard validity problem if it can express even just the equivalence of well-structured programs with the empty program skip. We also show, in these cases, that the set of propositional statements valid over finite models is not recursively enumerable, so there is not even an axiomatization for finitely valid propositions.
Undecidability of representability as binary relations
Publisher: Cambridge University Press (CUP)
Date: 12-2012
DOI: 10.2178/JSL.7704090
Abstract: 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.
Related Organisations
Related Funding Activities
ARC Future Fellowships - Grant ID: FT120100666
Start Date: 11-2012
End Date: 02-2019
Amount: $673,886.00
Funder: Australian Research Council
View Funded ActivityDiscovery Projects - Grant ID: DP0342459
Start Date: 2003
End Date: 12-2006
Amount: $193,036.00
Funder: Australian Research Council
View Funded ActivityDiscovery Projects - Grant ID: DP1094578
Start Date: 2010
End Date: 06-2017
Amount: $255,000.00
Funder: Australian Research Council
View Funded Activity