PFPeter Fenner

Peter Fenner

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Peter Fenner has a total of 2 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Identities in unitriangular and gossip monoids

    by Marianne Johnson, Peter Fenner


  • Open Access

    Identities in unitriangular and gossip monoids

    by Marianne Johnson, Peter Fenner

    We establish a criterion for a semigroup identity to hold in the monoid of $n \times n$ upper unitriangular matrices with entries in a commutative semiring $S$. This criterion is combinatorial modulo the arithmetic of the multiplicative identity element of $S$. In the case where $S$ is idempotent, the generated variety is the variety $\mathbf{J_{n-1}}$, which by a result of Volkov is generated by any one of: the monoid of unitriangular Boolean matrices, the monoid $R_n$ of all reflexive relations on an $n$ element set, or the Catalan monoid $C_n$. We propose $S$-matrix analogues of these latter two monoids in the case where $S$ is an idempotent semiring whose multiplicative identity element is the `top' element with respect to the natural partial order on $S$, and show that each generates $\mathbf{J_{n-1}}$. As a consequence we obtain a complete solution to the finite basis problem for lossy gossip monoids.

  • Open Access

    NP-completeness in the gossip monoid

    by Peter Fenner, Marianne Johnson, Mark Kambites

    Gossip monoids form an algebraic model of networks with exclusive, transient connections in which nodes, when they form a connection, exchange all known information. They also arise naturally in pure mathematics, as the monoids generated by the set of all equivalence relations on a given finite set under relational composition. We prove that a number of important decision problems for these monoids (including the membership problem, and hence the problem of deciding whether a given state of knowledge can arise in a network of the kind under consideration) are NP-complete. As well as being of interest in their own right, these results shed light on the apparent difficulty of establishing the cardinalities of the gossip monoids: a problem which has attracted some attention in the last few years.