Contributed talks
Note: all information below is included in the book of abstracts.
Thomas Aird (University of Manchester)
Tuesday 4 July, 11:20–11:40 • Main auditorium (Session E)
Semigroup Identities and Varieties of Plactic Monoids
In this talk, we discuss what is known about the semigroup identities satisfied by the plactic monoid of rank n. We then investigate how the variety generated by the plactic monoid of rank n interacts with the variety generated by the monoid of n x n upper triangular tropical matrices. From this, we show that we can construct semigroup identities satisfied by the plactic monoid of rank n, which are shorter than those previously known.
Wolfram Bentz (Universidade Aberta)
Wednesday 5 July, 12:00–12:20 • Main auditorium (Session H)
Extending the congruences of transformation monoids to its products
Congruences for transformation monoids were first described in 1952, when Mal’cev determined the congruences of the monoid of all transformations on a finite set. Since then, congruences have been characterized in various other monoids of (partial) transformations, such as the monoid of all injective partial transformations, or the monoid of all partial transformations.
In this talk we show how we can extend these results to products of two such monoids. As it turns out, the congruence structure of the factors is still visible in the congruences of the product, but the variations introduced by having an extra component adds a high level of technical complexity which accounts for the difficulty in achieving this result.
This is a joint work with João Araújo (Universidade Nova de Lisboa/NOVAMATH) and Gracinda M.S. Gomes (Universidade de Lisboa/CEMAT).
Carl-Fredrik Nyberg Brodda (Université Gustave Eiffel)
Monday 3 July, 11:00–11:20 • Main auditorium (Session A)
One relation: the story so far
Algebraic objects with a single defining relation have a long and rich history in combinatorial algebra. From one-relator groups, to one-relator Lie algebras, to one-relation monoids and inverse one-relation monoids, these objects have played a central role in the development of new techniques, conjectures, and counterexamples for the past century. Of particular focus has been the word problem, the problem of deciding whether two words in the generators represent the same element or not. In this talk, I will present an overview of three types of one-relation objects: groups, monoids, and inverse monoids. I will present some of the main theorems, problems, and mysteries connected to the word problem in each area, and some of the fundamental ways that they are all interlinked. I will then present some recent work, over the past 5 years, by various authors to try and develop a general theory of one-relation inverse monoids. This will include joint work with I. Foniqi & R. D. Gray.
Matthew Brookes (University of St Andrews)
Wednesday 5 July, 11:40–12:00 • Living room (Session I)
A method to determine coherency of monoids
A monoid is right coherent if every finitely generated subact of every finitely presented right act has a finite presentation. This notion is analogous to that of coherent rings. We show that if a monoid contains a certain configuration of three elements then it is not right coherent. In particular, this demonstrates that infinite transformation and partition monoids are not right coherent.
This is joint work with Nik Ruškuc (St Andrews) and Victoria Gould (York).
André Carvalho (NOVA University of Lisbon & NOVA Math, Portugal)
Monday 3 July, 12:00–12:20 • Main auditorium (Session A)
Algebraic and context-free subsets of subgroups
Over the years, rational and recognizable subsets of groups have been studied from different points of view and they are natural generalizations of finitely generated and finite index subgroups, respectively. While playing a less relevant role in the literature, their context-free counterparts, respectively algebraic and context-free subsets, also yield interesting results.
In this talk, we will relate the structure of algebraic and context-free subsets of a group G and that of a finite index subgroup H. Then, we will show that a kind of Fatou property, previously studied by Berstel and Sakarovitch in the context of rational subsets and by Herbst in the context of algebraic subsets, holds for context-free subsets if and only if the group is virtually free. Finally, we will exhibit a counterexample to a question of Herbst concerning this property for algebraic subsets.
Alice Clayphan-Taylor (University of Manchester)
Tuesday 4 July, 11:00–11:20 • Main auditorium (Session E)
Congruences on 2 x 2 tropical matrices
We present a classification of the congruences on 2 x 2 tropical matrices and the similarities of these to the structure of congruences on n x n matrices over a field. We further give insight into why our classification of the 2 x 2 case might not extend to 3 x 3 tropical matrices.
José Carlos Costa (CMAT, Universidade do Minho)
Thursday 6 July, 11:40–12:00 • Main auditorium (Session K)
Asymptotic behavior of the overlap gap between left-infinite and right-infinite words
In a recent paper with C. Nogueira and M.L. Teixeira, we investigated periodicity on infinite words. Given a left-infinite word λ, a right-infinite word ρ and a positive integer n, we define g(n) to be n minus the maximum length of overlaps between the suffix of λ and the prefix of ρ of length n. We proved that the "overlap gap" function g has finite image if and only if λ and ρ are ultimately periodic words with a same root.
Luís Cruz-Filipe (University of Southern Denmark)
Thursday 6 July, 11:40–12:00 • Living room (Session L)
Mathematics and Symbolic AI
Symbolic AI is a collective term for the subfields of Artificial Intelligence that aim at modelling knowledge and reasoning. Methods of symbolic AI typically can provide explanations for their conclusions, making them of special interest for applications where being able to understand the results is essential. In this talk we briefly explore the connection between Mathematics and Symbolic AI, and how they can mutually benefit from each other.
Volker Diekert (University of Stuttgart)
Monday 3 July, 17:30–17:50 • Living room (Session D)
Decidability of membership problems for flat rational subsets of GL(2, Q)
The talk reports on an ongoing work with Pavel Semukhin and Igor Potapov from Liverpool (UK). We address the problem to decide membership for rational subsets in matrix groups. A positive answer is known for GL(2, Q) and for a subgroup G sitting between GL(2, Z) and GL(2, Q) for so-called flat rational sets. This family is an effective relative Boolean algebra which constitutes to date the borderline for decidability.
Mikhailo Dokuchaev (University of Sao Paulo)
Monday 3 July, 11:00–11:20 • Living room (Session B)
Group (co)homology related to partial representations
In a joint work with with Marcelo M. Alves and Dessislava Kochloukova we study (co)homology of a group $G$ based on partial representations, i.e. modules over the partial group algebra $\kpg$ over a field $\K$. In particular, we link the partial (co)homology of $G$ with coefficients in an irreducible (resp. indecomposible) $\kpg$-module with the ordinary (co)homology of a subgroup of $G.$ Furthermore, we compare the standard cohomological dimension $cd_{\K}(G)$ (over a field $\K$) with the partial cohomological dimension $cd_{\K}^{par}(G)$ (over $\K$) and show that $cd_{\K}^{par}(G) \geq cd_{\K}(G),$ and that there is equality for $G = \Z$.
Francesco Dolce (FIT - CTU in Prague)
Thursday 6 July, 12:00–12:20 • Main auditorium (Session K)
Dendric languages and the Finite Index Basis Property
A dendric language is a subset of the free monoid that is factorial - i.e., for any of its elements all its factors are in the language as well - and such that all graphs describing the possible extensions of one of its elements are trees.
In a way, they can be seen as a generalization of the well-known Sturmian languages, but the class is much wider and contains several different interesting families of languages.
In this talk we use dendric languages to draw a path from Combinatorics on Words to Algebra of free groups, passing through Theory of Codes.
We give several examples and results of such a class of languages.
In particular we focus on some properties connecting the free monoid with the free group, proving that in a recurrent dendric language a finite bifix code is maximal if and only if it is the basis of a subgroup of the free group.
Maria Elisa Fernandes (Universidade de Aveiro)
Thursday 6 July, 11:00–11:20 • Canteen (Session M)
The number of string C-groups of high rank
One of the most important facts about abstract regular polytopes is that such a polytope is entirely described by its group
of automorphisms, which is a string C-group (a certain smooth quotient of a Coxeter group).
I will present my most recent contribution for the theory of abstract regular polytopes (string C-groups).
With Peter Cameron and Dimitri Leemans we proved that the number of string C-groups with automorphism group
$S_n$ and rank $r$ depends only on $(n-r)$ when $r\geq \frac{n+3}{2}$.
A consequence of this result is the complete classification of all regular abstract polytopes for $S_n$ with rank $n-\kappa$ for $\kappa\in\{1,\ldots,6\}$,
when $n\geq 2\kappa+3$, which greatly extends previous classifications.
The number of regular polytopes of this classification gives the following sequence of integers indexed by $\kappa$,
$$\Sigma{\kappa}=(1,1,7,9,35,48).$$
This sequence of integers is new according to the On-Line Encyclopedia of Integer Sequences.
Gilda Ferreira (FCUL)
Wednesday 5 July, 11:00–11:20 • Canteen (Session J)
System F: the convergent journey of Logic and Computer Science
In the early 1970s, Jean-Yves Girard, a logician working in prof theory, and John Reynolds, a computer scientist working in programming languages, independently introduced the polymorphic lambda calculus, also known as System F.
This presentation explores various properties of System F and discusses the Russell Prawitz translation of Intuitionistic Propositional Calculus into System F. Within this context, we delve into atomic polymorphism and atomization conversions. The talk emphasizes the interplay between logic and computation through the lens of the Curry-Howard isomorphism.
Ambroise Grau (University of York)
Wednesday 5 July, 11:20–11:40 • Living room (Session I)
Restrictions and extensions in the endomorphism monoid of an independence algebra
Endomorphism monoids of independence algebras generalise the notion of full transformation monoids and of linear maps of a vector space. In this talk we will discuss the structure of the subsemigroup $T(A,B)$ of endomorphisms of an independence algebra $A$ whose image is restricted to a subalgebra $B$ and compare it to the known structure of $\mathrm{End}(A)$. We will also study extensions of ideals of $\mathrm{End}(A)$ by giving conditions under which the translational hull of an ideal $I$ is isomorphic to the whole endomorphism monoid.
Ricardo Guilherme (NOVA University of Lisbon & NOVA Math, Portugal)
Tuesday 4 July, 12:00–12:20 • Main auditorium (Session E)
Generalizing the hypoplactic monoid through quasi-crystals for arbitrary root systems
The plactic monoid, formally introduced by Lascoux and Schützenberger, can be obtained by identifying words in the same position of isomorphic connected components of a Kashiwara crystal of Cartan type A. This method enriched the structure of the plactic monoid and allowed its generalization, because the construction still results in a monoid for crystals of another type. In this talk, following joint work with Alan Cain and António Malheiro, we show that the hypoplactic monoid, introduced by Krob and Thibon, admits an analogous approach. For this purpose, we introduce the notion of quasi-crystal associated to a root system. We show that a quasi-crystal gives rise to a weight labelled graph, called quasi-crystal graph, which allows a purely combinatorial description of seminormal quasi-crystals. We define a tensor product of seminormal quasi-crystals that leads to the notion of quasi-crystal monoid. In this framework, we show that the hypoplactic monoid can be obtained by identifying words in the same position of isomorphic connected components of a quasi-crystal of type A, which leads to its generalization, because this construction still results in a monoid for quasi-crystals of another type. We finally present some results for the hypoplactic monoid obtained from a quasi-crystal of type C.
William Hautekiet (ULB - Université libre de Bruxelles)
Monday 3 July, 11:20–11:40 • Living room (Session B)
Partial comodules of groups
The notion of partial comodule of a group is dual to that of partial module, of which the main examples are linearizations of partial actions of groups. Since global comodules over a group are exactly vector spaces graded over that group, partial comodules of groups can be seen as a partial analogue of graded vector spaces. In this talk, we will construct simple partial comodules of finite groups and discuss their globalization. Joint work with Eliezer Batista, Paolo Saracco and Joost Vercruysse.
Samuel Herman (CUNY Graduate Center)
Monday 3 July, 17:10–17:30 • Living room (Session D)
Pointlike sets with respect to ER
I outline a proof showing that pointlike sets are decidable for the pseudovariety of finite semigroups whose idempotent-generated subsemigroup is R-trivial. Additionally, I will briefly discuss some related conjectures.
Trevor Jack (Illinois Wesleyan University)
Monday 3 July, 16:30–16:50 • Living room (Session D)
Deterministic Logspace Algorithms for Checking Conjugacy in Inverse Semigroups
Given two elements of a full inverse semigroup, we will describe deterministic algorithms that decide within logarithmic space whether the elements are conjugate with respect to various notions of semigroup conjugacy.
Piotr Kawałek (Marii-Curie-Slodowska University in Lublin)
Tuesday 4 July, 11:20–11:40 • Canteen (Session G)
A probabilistic approach to solving equations in finite algebraic structures
The realm of equations over finite algebraic structures hides a spectrum of problems that have remained unsolved for many years. Even if we concentrate solely on finite groups, we still lack a complete description of groups for which a polynomial-time algorithm exists for the equation satisfiability problem. Nevertheless, some of the recent results give hope that such a description can be discovered in the near future. Interestingly, there is a connection of the equation satisfiability problems in groups with the expressive power of deterministic finite automata over those groups (in a non-uniform setting). We examine this connection in order to show a scheme for providing randomized polynomial-time algorithms.
Michael Kompatscher (Charles University, Prague)
Tuesday 4 July, 11:40–12:00 • Canteen (Session G)
Algebras with short pp-definitions
A primitive positive (pp) formula is a first-order formula that only admits existential quantification and conjunctions. It is well-known that Inv(A), the set of relations invariant under an algebraic structure A, is closed under pp-definitions. Then, let us say that A has short pp-definition, if Inv(A) is the pp-definable closure of a finite set of relations, and we can furthermore bound the length of pp-definitions of n-ary relations in Inv(A) by a polynomial p(n). In this talk, I would like to motivate this notion by applications in theoretical computer science (subpower membership, constraint satisfaction), and present a recent result, stating that finite algebras from residually finite varieties with cube term have short pp-definitions.
This is joint work with Jakub Bulín.
Jörg Koppitz (Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, Sofia )
Monday 3 July, 16:30–16:50 • Main auditorium (Session C)
Ranks and presentations for order-preserving transformations with one fixed point
We consider the semigroup (no monoid) of all order-preserving full transformations $\alpha$ on an $n$-element chain $X_{n}=\{1<2\cdots
Ludwig Krippahl (NOVA LINCS)
Thursday 6 July, 11:20–11:40 • Living room (Session L)
A quick introduction to deep learning
Deep neural models are increasingly used to tackle complex problems. Especially problems we do not know how to solve explicitly, such as image recognition and generation, chat bots or automated monitoring of social media. This presentation will cover advantages and disadvantages of these large models, take a brief look at how they work and show the importance of improving inductive bias.
Dmitry Kudryavtsev (University of Manchester)
Wednesday 5 July, 11:00–11:20 • Living room (Session I)
Local embeddability into finite semigroups
The concept of studying infinite structures by approximating them with finite ones has been investigated through various methods, such as residual finiteness (an algebraic approach based on homomorphisms), pseudofiniteness (a model theory approach) and soficity (a more topological approach). The notion of a structure locally embedding into the class of finite structures (being LEF for short) combines all the aforementioned approaches. In this talk we will be covering various properties and examples of LEF semigroups, seen both as a self-contained class and in relation to LEF groups and the general notion of being LEF.
Ganna Kudryavtseva (University of Ljubljana)
Monday 3 July, 11:40–12:00 • Living room (Session B)
$\mathrm{Hom}$-set globalization of partial semigroup actions
We present a new construction of globalization of a partial action of a semigroup on a set, the $\mathrm{Hom}$-set globalization construction. For a semigroup $S$ acting partially on a set, $X$, we construct a globalization of this partial action as a certain set of partial homomorphisms of $S$-acts from $S^1$ to $X$ and show that it is the terminal object in the category of all $X$-generated globalizations of the given partial action.
It is interesting that if $S$ is a group, the ${\mathrm{Hom}}$-set globalization construction coincides with the tensor product construction, but in the semigroup case the
constructions can be far different, with an infinite chain of non-isomorphic objects between them. This is joint work with Valdis Laan.
Valdis Laan (University of Tartu)
Monday 3 July, 12:00–12:20 • Living room (Session B)
Tensor product globalization of partial semigroup actions
We consider partial actions of semigroups on sets.
These are generalizations of global actions of semigroups and they appear naturally in many places. For example, the additive semigroup of natural numbers acts partially on the set of natural numbers by subtraction.
One important problem is: when can a partial action of a semigroup on a set $A$ be extended to a global action of the same semigroup on a (possibly) bigger set $B$? In such a case we say that the partial action can be globalized.
It turns out that a partial action of a semigroup can be
globalized if and only if it is strong.
A semigroup is called firm if it is canonically isomorphic to its tensor square. Using tensor products, one can aslo define firm global and partial actions. Firmness is a condition that was first used for rings and modules and later adopted to the
semigroup case. It plays an important role in Morita theory (both for semigroups and non-unital rings).
Every firm and strong partial action of a semigroup can be globalized using a tensor product construction and the resulting global action will be an initial object in the category of all globalizations of the initial partial action.
We obtain a globalization functor which is a reflector
from the category of firm stong partial acts to the category of firm global acts.
This talk is based on joint research with Ganna Kudryavtseva.
Alexei Lisitsa (University of Liverpool )
Monday 3 July, 11:20–11:40 • Main auditorium (Session A)
New AC-simplifications found by automated reasoning
We present recent developments in the applications of automated theorem proving in the investigation of the well-known Andrews-Curtis conjecture [1]. We demonstrate previously unknown simplifications of trivial group presentations from a parametric family MS_n(w∗) [2]
for n = 3, 4, 5, 6, 7 (subset of well-known Miller-Schupp family [3]). We apply the method developed in [4,5] using both implicational (n=3...6) and equational encoding (n=7) of simplification problems in first-order logic. We discuss the problem of comprehension and generalizations of these proofs in order to obtain a proof for all n > 1.
References
[1] J. Andrews and M.L. Curtis. Free groups and handlebodies. Proc. Amer. Math. Soc., 16:192–195, 1965.
[2] Ximena Fern ́andez. Morse theory for group presentations. arxiv:1912.00115, 2019.
[3] C. F. Miller III and P. E. Schupp. Some presentations of the trivial group, volume 250 of Contemp. Math., pages 113–115. Amer. Math. Soc., Providence, RI, 1999.
[4] A. Lisitsa. The Andrews-Curtis Conjecture, Term Rewriting and First-Order Proofs. In Mathematical Software - ICMS 2018 - 6th International Conference, South Bend, IN, USA, July 24-27, 2018, Proceedings, pages 343–351, 2018.
[5] A. Lisitsa. Automated reasoning for the Andrews-Curtis conjecture. In AITP 2019, Fourth Conference on Artificial Intelligence and Theorem Proving, Abstracts of the Talks April 7–12, 2019, Obergurgl, Austria, pages 82–83, 2019.
Maria Loukaki (Department of Mathematics & Applied Mathematics, University of Crete )
Thursday 6 July, 12:00–12:20 • Canteen (Session M)
On the common transversal probability in finite groups.
Let $G$ be a finite group, and let $H$ be a subgroup of $G$. We compute the probability, denoted by $P_G(H)$, that a left transversal of $H$ in $G$ is also a right transversal, thus a two-sided one. Moreover, we define, and denote by $tp(G)$, the common transversal probability of $G$ to be the minimum, taken over all subgroups $H$ of $G$, of $P_G(H)$. We will see that $tp(G)$ satisfies various nice abstract properties like subgroup- and quotient-monotonicity and thus serves as an efficient ”detector” of
key properties of G. Roughly, this means that the larger tp(G) is, the more normal structure G exhibits and thus determines structural properties of $G$ like nilpotency, solvability and supersolvability . Finally, some related questions are discussed.
Inês Legatheaux Martins (Universidade de Lisboa)
Thursday 6 July, 11:20–11:40 • Canteen (Session M)
Schur-Weyl dualities for the rook monoid: an approach via Schur algebras
The classical Schur-Weyl duality between the symmetric group Sn and the general linear group GLd(C) on the n-th tensor power of a d-dimensional complex space is a fundamental result in representation theory. In essence, it shows that the study of the representations of Sn and the polynomial representations of GLd(C) are essentially two sides of the same coin.
Results of J. A. Green (among others) show that the classical Schur-Weyl duality remains true if one replaces the complex field C by an arbitrary infinite field F. This is largely due to the existence of an equivalence between polynomial representations of GLd(F) and representations of Schur algebras. Introduced in a seminal monograph by J. A. Green in 1980, these finite-dimensional algebras provide a natural setting for studying representations of GLd(F) and their interactions with those of Sn. For the past forty years, many authors have exploited this approach and enriched our knowledge of the representation theory of these structures, specially in the modular case.
In this talk, we turn our attention to Schur-Weyl dualities that involve the rook monoid Rn. Also known as the symmetric inverse monoid, Rn plays a similar rôle for finite inverse monoids as Sn plays for finite groups. In 2002, L. Solomon established a Schur-Weyl duality between Rn and the general linear group GLd(F) on the n-th tensor power of a d-dimensional F-space, where F is a field of characteristic zero.
The aim of this talk is to give a new Schur-Weyl duality between Rn and an analog of the classical Schur algebra, which we have named the extended Schur algebra. Our approach will allow us to recover Solomon’s result in the language of Schur algebras and to discuss its generalisation for infinite fields.
Peter Mayr (University of Colorado Boulder)
Wednesday 5 July, 11:00–11:20 • Main auditorium (Session H)
Commutator theory for semigroups
Commutators have been generalized from groups to arbitrary algebras in many different ways. I will give an overview of the known properties of the binary term condition commutator and higher commutators from universal algebra specialized to semigroups. In particular I will investigate what the derived notions of nilpotence, supernilpotence, and solvability mean and how they relate to classical concepts in semigroup theory.
Neil A. McKay (University of New Brunswick, Saint John, Canada)
Tuesday 4 July, 11:00–11:20 • Living room (Session F)
The scale of ups
The main tool used in analyzing all-small games since the 1970s has been the atomic weight theory, which tries to measure a game in terms of the game up. In the 1980s, Conway and Ryba proposed (but did not publish) the uptimal theory, which is finer and more precise than the atomic weight theory. Here, we provide a brief summary of this theory, including its practical application for analyzing specific rulesets and discuss the mathematical structure of the uptimals.
Craig Miller (University of York)
Monday 3 July, 16:50–17:10 • Living room (Session D)
The heights of Green's posets of semigroups
For each of the Green's relations K in {R, L, H, J}, the K-height of a semigroup is the height of its poset of K-classes, i.e. the supremum of the lengths of chains of K-classes. We discuss the relationships between these parameters. In particular, for a semigroup S with finite L- and R-heights, we establish a bound on the J-height of S. Moreover, for each K in {R, L, H}, given a semigroup S with finite K-height we establish bounds on the K-heights of arbitrary one-sided ideals (in particular, these substructures inherit the property of having finite K-height). By way of contrast, the property of having finite J-height is not closed under ideals, but it is within the class of stable semigroups.
Rebecca Milley (Grenfell Campus, Memorial University of Newfoundland, Canada)
Tuesday 4 July, 11:40–12:00 • Living room (Session F)
Progress on misère dicots: game comparison, canonical forms, and conjugate inverses
The universe of dicotic games, denoted as D, consists of games where either both players can move or neither player can move. In D, a comparison of games can be performed using an «options only» test, which is then used to define unique reduced games (canonical forms). Moreover, by using the defined canonical forms in D, it is possible to prove that D satisfies the conjugate property: regarding the invertible forms, the inverses can be obtained
by swapping the sides of the players.
Ana-Catarina C. Monteiro (FCUL and CEMAT, Universidade de Lisboa)
Wednesday 5 July, 12:00–12:20 • Living room (Session I)
Formations on Orthodox Semigroups
Formations of finite groups have been extensively explored (see [1], for example), however formations of semigroups have not been object of large study. The first results were obtained by Ballester-Bolinches et al [3] for finite monoids and associated formal languages, and were followed by the work presented in [2], that includes the study of related congruences, generalising results of Therien [8] for varieties of finite monoids, congruences and recognisable languages. In a different direction, there is the work of Branco et al [4]. In the world of many sorted formations these questions are discussed by Ll\'opez and Vidal in [7].
It is natural to consider formations of other classes of semigroups such as inverse. In [5], Gomes and Nobre introduced the concept of formation for inverse semigroups, deducing several properties and, in particular, relations between classes of inverse semigroups and of groups. By a formation of inverse semigroups we mean a class of such semigroups closed for quotients and finite subdirect products.
With G. Gomes, we have extended the concept of bivariety introduced in [6], to the concept of formation of orthodox semigroups. In this presentation, inspired by what was done in [5], and after introducing various concepts, we will compare classes of orthodox semigroups, of inverse semigroups and of groups, discussing the property of being formations, bivarieties or varieties. Also, we shall relate formations and f-formations of orthodox semigroups with formations of congruences and formations of idempotent separating congruences.
References
[1] Ballester-Bolinches, Ezquerro L.M., Classes of Finite Groups, volume 584 [Springer Science & Business Media], (2006).
[2] Ballester-Bolinches A., Llópez E.C., Esteban-Romero R., Rutten J. ``Formations of finite
monoids and formal languages: Eilenberg's variety theorem revisited'' Sci. Ann. Comput. Sci., 25, 171--209, 2015.
[3] Ballester-Bolinches A., Pin J., Soler-Escrivá X. ``Formations of monoids, congruences, and formal languages'' Forum Math., 26, 1737-1761, 2014.
[4] Branco M.J., Gomes G.M., Pin J., Soler-Escrivá X.. ``On formations of monoids'' J. Pure and Appl. Algebra, 224, 106401, 2020.
[5] Gomes G.M.S., Nobre I.J., ``Formations of inverse semigroups'' Semigroup Forum, 105, 217-243, 2022.
[6] Kadourek J., Szendrei M.B., ``A new approach in the theory of orthodox semigroups'' Semigroup Forum, 40, 257-296, 1990.
[7] Vidal J.C., Llópez. E.C. ``Eilenberg theorems for many-sorted formations'' Houston J. Math., 54, 1427-1444, 2019.
[8] Therién. D. ``Classification of finite monoids: the language approach'' Theor. Comput. Sci., 14, 195-208, 1981.
Financed by FCT Projects UIDB/04621/2020 and UIDP/04621/2020
Conceição Nogueira (IPLeiria, CMAT)
Thursday 6 July, 11:20–11:40 • Main auditorium (Session K)
The overlap gap between left-infinite and right-infinite words
In this talk I will present ultimate periodicity properties related to
overlaps between the suffixes of a left-infinite word λ and the prefixes
of a right-infinite word ρ. I will talk about a result that states that
the set of minimum lengths of words x and x′ such that xλ_n = ρ_nx′
or λ_nx = x′ρ_n is finite, where n runs over positive integers and λ_n
and ρ_n are respectively the suffix of λ and the prefix of ρ of length
n, if and only if λ and ρ are ultimately periodic words of the form
λ = u−∞v and ρ = wu∞ for some finite words u, v and w.
This is a joint work with José Carlos Costa (Universidade do Minho)
and M. Lurdes Teixeira (Universidade do Minho).
Richard Nowakowski (Dalhousie University, Canada)
Tuesday 4 July, 11:20–11:40 • Living room (Session F)
Absolute Combinatorial Game Theory
In this talk, we explore a recent unifying additive theory that applies to standard conventions in Combinatorial Game Theory, including normal-play, misère-play, and scoring-play. Games in an absolute universe satisfy the property of dicotic closure. This implies that if A and B are non-empty sets of forms in the universe, then the form {A|B} is also an element of the universe. When this property holds, the fundamental game comparison problem «Is G>=H?» can be solved constructively, meaning that it is possible to compare G with H using only their literal forms.
Isabel Oitavem (NOVA University of Lisbon & NOVA Math, Portugal)
Wednesday 5 July, 11:20–11:40 • Canteen (Session J)
On a shortest proof of \phi implies \phi
Related with investigations on simplicity of proofs, we focus on formulas of the form \phi implies \phi, adopting as framework the Pure Positive Implication Propositional Calculus based on Frege's axiomatization of implication. In this context, we search for a shortest proof of \phi implies \phi. There might be particular instances of this formula which admit proofs that are shorter than a shortest proof of \phi implies \phi in general. A first example is the case for \phi itself of the form \psi implies \psi. More examples are obtained by means of combinatory logic. This is joint work with Reinhard Kahle and Paulo Guilherme Santos.
Luís Oliveira (CMUP, Dep. Mat., Fac. Ciências, Univ. Porto, Portugal)
Monday 3 July, 11:40–12:00 • Main auditorium (Session A)
Weakly generated regular semigroups
A regular semigroup $S$ is weakly generated by a subset $A$ if $S$ has no proper regular subsemigroup containing $A$. A regular semigroup $S$ weakly generated by a $A$ is not generated by $A$ usually, as very often the subsemigroup generated by $A$ is a proper non-regular subsemigroup. In this talk we will consider two classes of regular semigroups, the class $WGI(X)$ of all regular semigroups weakly generated by a set $X$ of idempotents and the class $WG(X)$ of all regular semigroups weakly generated by a set $X$ of elements. Both classes have a free object in the sense that all semigroups in those classes are homomorphic images of the corresponding free object. In this talk we will look to the structure of these objects.
We will denote by $WFI(X)$ the free object in $WGI(X)$, that is, the \emph{weakly free idempotent generated} regular semigroup on $X$, and by $WF(X)$ the free object in $WG(X)$, that is, the \emph{weakly free} regular semigroup on $X$. Both semigroups are described by presentations with an infinite set of generators and an infinite set of relations. Nevertheless, we can describe a canonical form for the corresponding congruence classes, and then present a solution for the word problem for these presentations. We will see also how the generating sets of these presentations become a ``footprint'' for the structure of the $\mathcal{D}$-class relation on these semigroups.
Tânia Paulista (NOVA University of Lisbon & NOVA Math, Portugal)
Monday 3 July, 17:30–17:50 • Main auditorium (Session C)
Commutative nilpotent transformation semigroups
We characterize the commutative nilpotent subsemigroups of maximum order in the full transformation semigroup $T_n$, using a mixture of algebraic and combinatorial techniques. Although non-commutative nilpotent subsemigroups of $T_n$ can be much larger, the maximum-order commutative nilpotent subsemigroups turn out to be precisely the maximum-order null subsemigroups of $T_n$ previously characterized by Cameron et al. [1].
[1] Peter J. Cameron, James East, Des FitzGerald, James D. Mitchell, Luke Pebody and Thomas Quinn-Gregson. Minimum degrees of finite rectangular bands, null semigroups, and variants of full transformation semigroups. Preprint, 2021. arXiv: 2110.09701.
Hugo Penedones (Inductiva Research Labs)
Thursday 6 July, 12:00–12:20 • Living room (Session L)
AI for scientific computing
Fundamental sciences such as Mathematics, Physics, Chemistry and Biology have a long track record of using computers to help answer open research questions. Impressive results have been achieved using various domain-specific algorithms and systems, some of them exploiting parallelization in large computer clusters. Despite the exponential growth of compute power available in the last decades, progress in some problems has been limited -- as the time complexity of the underlying algorithm might also grow exponentially with the input size (e.g. some combinatorial problems, simulations of quantum systems, etc.). Can Artificial Intelligence, in particular Deep Learning, become the new "universal" computational tool to help crack more problems in Science? Recent trends show that it might.
Teresa M. Quinteiro (Instituto Superior de Engenharia de Lisboa & NOVA Math, Portugal)
Monday 3 July, 16:50–17:10 • Main auditorium (Session C)
Generators of semigroups of endomorphisms of a finite path
In this talk, we consider the widely studied endomorphisms and weak endomorphisms of a finite undirected path from semigroup generators perspective. We present formulas for the ranks of the semigroups $wEndP_n$ and $EndP_n$ of all weak endomorphisms and all endomorphisms of the undirected path $P_n$ with $n$ vertices.
Duarte Ribeiro (NOVA University of Lisbon & NOVA Math, Portugal)
Tuesday 4 July, 11:40–12:00 • Main auditorium (Session E)
Tropical representations and identities of the stylic monoid
The stylic monoid styln of finite rank n, introduced by Abram and Reutenauer, is a finite quotient of the plactic monoid of rank n, defined by the action of words on the left of columns of semistandard Young tableaux by Schensted left insertion. Its elements can be uniquely identified with so-called N-tableaux, and it is presented by the Knuth relations and the idempotency relation on its generators. As a finite J-trivial monoid, it is in some Jk, the pseudovariety in Simon’s hierarchy of J-trivial monoids which recognize piecewise testable languages of height k, which is defined by all identities u ≈ v such that u and v share the same subsequences of length ≤ k. Blanchet-Sadri has shown that Jk is finitely based if and only if k ≤ 3, while Johnson and Fenner have shown that the variety described by the same identities as Jk is generated by the monoid Uk+1(S) of (k+1) × (k+1) upper unitriangular matrices with entries in a non-trivial, idempotent commutative semiring S, of which the tropical max-plus semiring T is an example.
We exhibit a faithful representation of styln as a monoid of upper unitriangular matrices over T. Thus, we show that styln generates the pseudovariety Jn. From this, we obtain the equational theory of styln, show that it is finitely based if and only if n ≤ 3, and that its identity checking problem is decidable in linearithmic time. We also solve the finite basis problem for styln with involution.
Bernardo Rossi (Johannes Kepler Universität Linz)
Tuesday 4 July, 12:00–12:20 • Canteen (Session G)
Polynomial completeness properties of Mal’cev algebras with (SC1)
In the characterization of various types of polynomial completeness for algebras in congruence modular varieties we often encounter conditions that involve congruences, the binary term condition commutator and the centralizer. In this talk, we will discuss the properties of the finite algebras with a Mal’cev polynomial that satisfy a condition known in the literature as (SC1).
In particular, we will show how partial functions that preserve the congruences of a finite Mal’cev algebra with (SC1) can be interpolated by a polynomial function, and we will give a characterization of strictly 1-affine completeness for finite congruence regular Mal’cev algebras.
Part of the work presented in this talk is based on an unpublished manuscript by E. Aichinger and P. Idziak.
Carlos Pereira dos Santos (NOVA University of Lisbon & NOVA Math, Portugal)
Tuesday 4 July, 12:00–12:20 • Living room (Session F)
Invertible elements of the misère dicotic universe
The universe of dicotic games, denoted as D, consists of games where either both players can move or neither player can move. In D, a comparison of games can be performed using an "options only" test. Moreover, by using that test, it is possible to prove a characterization of the invertible elements of D.
José Santos (Microsoft)
Thursday 6 July, 11:00–11:20 • Living room (Session L)
Large Language Models as generic machine learning models
In this talk, we showcase the power of large language models (LLMs) as generic machine learning models. We'll explore how prompt engineering enables LLMs to solve complex machine learning problems that previously required extensive data collection, labeling, and training of specific models by data scientists. Through carefully crafted prompts, one can leverage LLMs vast pre-trained knowledge to tackle tasks that until very recently demanded substantial time and expertise. This breakthrough significantly streamlines the development process and enables non-experts to harness LLMs for non-trivial machine learning tasks thus democratizing access to advanced AI capabilities.
Paulo Guilherme Santos (NOVA University of Lisbon & NOVA Math, Portugal)
Wednesday 5 July, 12:00–12:20 • Canteen (Session J)
‘Provability Implies Provable Provability’ using FLINSPACE
We study the derivability condition 'provability implies provable provability' using the complexity class FLINSPACE.
Apatsara Sareeto (Institute of Mathematics, University of Potsdam, Germany )
Monday 3 July, 17:10–17:30 • Main auditorium (Session C)
The rank of the semigroup of order-, fence-, and parity-preserving partial injections on a finite set
The monoid of all partial injections on a finite set (the symmetric inverse semigroup) is of particular interest because of the well-known Wagner-Preston Theorem. In this presentation, we step forward the study of a submonoid of the symmetric inverse semigroup. We study the monoid of all order-preserving partial injections on an $n$-element chain such that $|I_i|$ and $|J_i|$ have the same parity for $i\in\{1,...,k\}$, where $I_1 Csaba Schneider (Universidade Federal de Minas Gerais) Standard filiform Lie algebras are nilpotent Lie algebras of maximal nilpotency class. The algebras of their polynomial invariants are finitely generated and show complicated structure already in small dimensions. I will present some theoretical and computational methods to calculate the Hilbert series of these invariant algebras. Manuel Silva (NOVA University of Lisbon & NOVA Math, Portugal) In 1928 Frank P. Ramsey proved a theorem in his paper “On a problem of formal logic”, which can be viewed as a powerful generalization of the pigeonhole principle and implies that every large combinatorial structure contains some regular substructure. We will discuss ramsey-type results in the context of infinite words. Tânia Z. Silva (FCUL CEAFEL) We consider the central Schur ring associated with the standard supercharacters of the adjoint group $G(\mathcal{A})$ of a finite radical ring $\mathcal{A}$, and define supercharacters of the subgroup $C_{G(\mathcal{A})}(\sigma)$ consisting of elements fixed by an involution of $G$ that can be defined when $\mathcal{A}$ is endowed with an (anti)involution and has odd characteristic. In particular, we extend known results for unipotent subgroups of the classical finite Chevalley groups. Eduardo Skapinakis (NOVA University of Lisbon & NOVA Math, Portugal) In this talk I will briefly introduce the implicit approach to complexity and how to use term rewriting systems to develop and analyse algorithms for classes of functions defined inductively. Nora Szakacs (University of Manchester) Equipping groups with a metric naturally connected to algebraic properties of the group is the idea which led to the development of the vibrant field of geometric group theory, and naturally it has prompted several attempts to be extended to larger classes of semigroups. The class that most naturally lends itself to generalizations is that of inverse semigroups, as their Schützenberger graphs carry a natural geometry which is tied to the structure of the semigroup by Stephen's solution to the word problem. In recent years, there has been a heightened interest in studying this metric both from an algorithmic point of view, as well as in relation to an associated C*-algebra called the uniform Roe algebra. In the talk, I will give an overview of the theory and present some of these results, which are joint with Pedro Silva, Robert Gray, Diego Martínez and YeongChyuan Chung. Armin Weiß (Universität Stuttgart) Over twenty years ago, Goldmann and Russell initiated the study of the complexity of the equation satisfiability problem (PolSat) and the NUDFA program satisfiability problem (ProgSat) in finite groups. They showed that these problems are decidable in polynomial time for nilpotent groups while they are NP-complete for non-solvable groups. However, for a long time the case of solvable but non-nilpotent groups remained wide open -- in a long sequence of papers, only the case of p-by-abelian groups could be shown to be decidable In 2020 Idziak, Kawałek, Krzaczkowski and myself succeeded to show that in groups of Fitting length at least three, PolSat cannot be solved in polynomial time under the condition that the exponential time hypothesis (ETH) holds. Later we extended this result to certain group of Fitting length 2 and considered the related problems of ProgSat and ListPolSat for which, under ETH and the so-called constant degree hypothesis, we can obtained a complete classification in which cases they are in P. In this talk I will explain the ideas for our lower bounds.
Wednesday 5 July, 11:20–11:40 • Main auditorium (Session H)
The Hilbert series of the invariant algebras of the standard filiform Lie algebras
Thursday 6 July, 11:00–11:20 • Main auditorium (Session K)
Ramsey-type results for infinite words
In one of the results, it is proved that the existence of powers or anti-powers is an unavoidable regularity. An abelian version, where we count the frequency of each letter, is conjectured to be true and reveals a surprising connection with the factor complexity function of an infinite word.
Thursday 6 July, 11:40–12:00 • Canteen (Session M)
A Schur ring approach to supercharacters of groups associated with finite radical rings
Wednesday 5 July, 11:40–12:00 • Canteen (Session J)
Implicit complexity and term rewriting systems
Wednesday 5 July, 11:40–12:00 • Main auditorium (Session H)
Geometric properties of inverse semigroups
Tuesday 4 July, 11:00–11:20 • Canteen (Session G)
Hardness of equation satisfiability for finite solvable groups
in polynomial time.