Publications

Export 37 results:
Sort by: Author Title Type [ Year  (Asc)]
2018
Araújo, J., M. Kinyon, J. Konieczny, and A. Malheiro. "Decidability and Independence of Conjugacy Problems in Finitely Presented Monoids." Theoretical Computer Science. 731 (2018): 88-98. AbstractWebsite

There have been several attempts to extend the notion of conjugacy from groups to monoids.
The aim of this paper is study the decidability and independence of conjugacy problems
for three of these notions (which we will denote by $\sim_p$, $\sim_o$, and $\sim_c$) in
certain classes of finitely presented monoids. We will show that in the class of polycyclic monoids,
$p$-conjugacy is ``almost'' transitive, $\sim_c$ is strictly included in $\sim_p$, and
the $p$- and $c$-conjugacy problems are decidable with linear compexity.
For other classes of monoids, the situation is more complicated.
We show that there exists a monoid $M$ defined by a finite complete
presentation such that the $c$-conjugacy problem for $M$ is undecidable, and
that for finitely presented monoids, the $c$-conjugacy problem and the word
problem are independent, as are the $c$-conjugacy and $p$-conjugacy problems.

Cain, A. J., and A. Malheiro. "Identities in plactic, hypoplactic, sylvester, Baxter, and related monoids." The Electronic Journal of Combinatorics. 25.3 (2018): P3.30 (19 pages). AbstractWebsite

This paper considers whether non-trivial identities are satisfied by certain ‘plactic-like’ monoids that, like the plactic monoid, are closely connected with combinatorics. New results show that the hypoplactic, sylvester, Baxter, stalactic, and taiga monoids satisfy identities. The existing state of knowledge is discussed for the plactic and Bell monoids.

2019
Cain, A. J., and A. Malheiro. "Combinatorics of cyclic shifts in plactic, hypoplactic, sylvester, Baxter, and related monoids." Journal of Algebra. 535 (2019): 159-224. Abstract

The cyclic shift graph of a monoid is the graph whose vertices are elements of the monoid and whose edges link elements that differ by a cyclic shift. This paper examines the cyclic shift graphs of `plactic-like' monoids, whose elements can be viewed as combinatorial objects of some type: aside from the plactic monoid itself (the monoid of Young tableaux), examples include the hypoplactic monoid (quasi-ribbon tableaux), the sylvester monoid (binary search trees), the stalactic monoid (stalactic tableaux), the taiga monoid (binary search trees with multiplicities), and the Baxter monoid (pairs of twin binary search trees). It was already known that for many of these monoids, connected components of the cyclic shift graph consist of elements that have the same
evaluation (that is, contain the same number of each generating symbol). This paper focusses on the maximum diameter of a connected component of the cyclic shift graph of these monoids in the rank-$n$ case. For the hypoplactic monoid, this is $n-1$; for the sylvester and taiga monoids, at least $n-1$ and at most $n$; for the stalactic monoid, $3$ (except for ranks $1$ and $2$, when it is respectively $0$ and $1$); for the plactic monoid, at least $n-1$ and at most $2n-3$. The current state of knowledge, including new and previously-known results, is summarized in a table.

Cain, Alan J., António Malheiro, and Fábio M. Silva. "Combinatorics of patience sorting monoids." Discrete Mathematics. 342.9 (2019): 2590-2611. AbstractWebsite

This paper makes a combinatorial study of the two monoids and the two types of tableaux that arise from the two possible generalizations of the Patience Sorting algorithm from permutations (or standard words) to words. For both types of tableaux, we present Robinson--Schensted--Knuth-type correspondences (that is, bijective correspondences between word arrays and certain pairs of semistandard tableaux of the same shape), generalizing two known correspondences: a bijective correspondence between standard words and certain pairs of standard tableaux, and an injective correspondence between words and pairs of tableaux.

We also exhibit formulas to count both the number of each type of tableaux with given evaluations (that is, containing a given number of each symbol). Observing that for any natural number $n$, the $n$-th Bell number is given by the number of standard tableaux containing $n$ symbols, we restrict the previous formulas to standard words and extract a formula for the Bell numbers. Finally, we present a `hook length formula' that gives the number of standard tableaux of a given shape and deduce some consequences.

Cain, A. J., R. D. Gray, and A. Malheiro. "Crystal monoids & crystal bases: Rewriting systems and biautomatic structures for plactic monoids of types An, Bn, Cn, Dn, and G2." Journal of Combinatorial Theory, Series A. 162 (2019): 406-466. AbstractWebsite

This paper constructs presentations via finite complete rewriting systems for plactic monoids of types $A_n$, $B_n$, $C_n$, $D_n$, and $G_2$, using a unified proof strategy that depends on Kashiwara's crystal bases and analogies of Young tableaux, and on Lecouvey's presentations for these monoids. As corollaries, we deduce that plactic monoids of these types have finite derivation type and satisfy the homological finiteness properties left and right $\mathrm{FP}_\infty$. These rewriting systems are then applied to show that plactic monoids of these types are biautomatic.

Malheiro, António, and José Francisco Reis. "Identification of proofs via syzygies." Philosophical Transactions of the Royal Society A. 377.2140 (2019). AbstractWebsite

In 1900, Hilbert gave a lecture at the International Congress of Mathematicians in Paris, for which he prepared 23 problems that mathematicians should solve during the twentieth century. It was found that there was a note on a 24th Problem focusing on the problem of simplicity of proofs. One of the lines of research that was generated from this problem was the identification of proofs. In this article, we present a possible method for exploring the identification of proofs based on the membership problem original from the theory of polynomial rings. To show this, we start by giving a complete worked-out example of a membership problem, that is, the problem of checking if a given polynomial belongs to an ideal generated by finitely many polynomials. This problem can be solved by considering Gröbner bases and the corresponding reductions. Each reduction is a simplification of the polynomial and it corresponds to a rewriting step. In proving that a polynomial is a member of an ideal, a rewriting process is used, and many different such processes can be considered. To better illustrate this, we consider a graph where each rewriting step corresponds to an edge, and thus a path corresponds to a rewriting process. In this paper, we consider the identification of paths, within the context of the membership problem, to propose a criterion of identification of proofs.
This article is part of the theme issue ‘The notion of ‘simple proof’ - Hilbert’s 24th problem’.

Cain, A. J., A. Malheiro, and F. M. Silva. "The monoids of the patience sorting algorithm." International Journal of Algebra and Computation. 29.01 (2019): 85-125. AbstractWebsite

The left patience sorting (lPS) monoid, also known in the literature as the Bell monoid, and the right patient sorting (rPS) monoid are introduced by defining certain congruences on words. Such congruences are constructed using insertion algorithms based on the concept of decreasing subsequences.
Presentations for these monoids are given.

Each finite-rank rPS monoid is shown to have polynomial growth and to satisfy a non-trivial identity (dependent on its rank), while the infinite rank rPS monoid does not satisfy a non-trivial identity. The lPS monoids of finite rank have exponential growth and thus do not satisfy non-trivial identities. The
complexity of the insertion algorithms is discussed.

rPS monoids of finite rank are shown to be automatic and to have recursive complete presentations. When the rank is $1$ or $2$, they are also biautomatic. lPS monoids of finite rank are shown to have finite complete presentations and to be biautomatic.

2022
Cain, Alan J., António Malheiro, and Duarte Ribeiro. "Identities and bases in the hypoplactic monoid." Communications in Algebra. 50 (2022): 146-162. AbstractWebsite
n/a
Can, M.B., Casimiro Malheiro A. & A. "Idempotent Varieties of Incidence Monoids and Bipartite Posets." Algebra and Representation Theory (2022). AbstractWebsite

The algebraic variety defined by the idempotents of an incidence monoid is investigated. Its irreducible components are determined. The intersection with an antichain submonoid is shown to be the union of these irreducible components. The antichain monoids of bipartite posets are shown to be orthodox semigroups. The Green’s relations are explicitly determined, and applications to conjugacy problems are described. In particular, it is shown that two elements in the antichain monoid are primarily conjugate in the monoid if and only if they belong to the same -class and their multiplication by an idempotent of the same -class gives conjugate elements in the group.

A. J. Cain, M. Johnson, Kambites Malheiro M. A. "Representations and identities of plactic-like monoids." Journal of Algebra. 606 (2022): 819-850. AbstractWebsite

We exhibit faithful representations of the hypoplactic, stalactic, taiga, sylvester, Baxter and right patience sorting monoids of each finite rank as monoids of upper triangular matrices over any semiring from a large class including the tropical semiring and fields of characteristic 0. By analysing the image of these representations, we show that the variety generated by a single hypoplactic (respectively, stalactic or taiga) monoid of rank at least 2 coincides with the variety generated by the natural numbers together with a fixed finite monoid (respectively, F) and forms a proper subvariety of the variety generated by the plactic monoid of rank 2.

In Press
Alan J. Cain, António Malheiro, Duarte Ribeiro. "Identities and bases in the sylvester and Baxter monoids." Journal of Algebraic Combinatorics (In Press).
Submitted
Cain, Alan J., Ricardo P. Guilherme, and António Malheiro. "Quasi-crystals for arbitrary root systems and associated generalizations of the hypoplactic monoid." (Submitted). AbstractWebsite

n/a