The Schedule
Day 1
June 15, Thursday
12:30 - 14:00
Lunch
14:00 - 15:00
Igor Potapov
Title: Matrix Semigroups, Equations and Linear Maps
Abstract: A large number of naturally defined matrix problems are still unanswered, despite the long history of matrix theory. Some of these questions have recently drawn renewed interest in the context of the analysis of digital processes, verification problems, and links with several fundamental questions in mathematics. In this presentation, I will discuss a number of challenging computational problems for matrix semigroups and their connections to matrix equations, non-deterministic maps and linear recurrence sequences. Apart from answering whether the decision problems for matrix semigroups are decidable, it is also important to understand the level of their complexity. So, we are also interested in proving their harnesses in the computational complexity hierarchy, reductions to other models/problems and building efficient algorithms for numerical and symbolic reachability questions.
15:00 - 16:00
Lorna Gregory
Title: Representation type and decidability of theories of modules of finite-dimensional algebras.
Abstract: The representation type of a finite-dimensional k-algebra is an algebraic measure of how hard it is to classify its finite-dimensional indecomposable modules. Roughly, a finite-dimensional k-algebra is of wild representation type if classifying its finite-dimensional indecomposable modules is as hard as classifying those of the polynomial ring in two non-commuting variables. On the other hand, a finite-dimensional algebra is tame if for every dimension d, all but finitely many of the finite-dimensional indecomposable modules of dimension d are in finitely many 1-parameter families. According to Drozd, when k is algebraically closed, a finite-dimensional k-algebra is either tame or wild.
A long standing conjecture of Mike Prest claims that a finite-dimensional algebra has decidable theory of modules if and only if it is of tame representation type. I will give an introduction to this conjecture.
Coffee Break 16:00 - 16:30
16:30 - 17:00
Martin Hampenberg Christensen
Title: Submonoids of the Symmetric Inverse Monoid
Abstract: Let X be a countably infinite set and Sym(X) the group of permutations of X. Given two subgroups G,H ≤ Sym(X) let us write G ≈ H if there exists a finite subset U of Sym(X) such that the groups generated by G ∪ U and H ∪ U are equal. In their 2006 paper, Bergman and Shelah showed that the subgroups which are closed in the pointwise topology on Sym(X) fall into exactly four equivalence classes with respect to this equivalence relation ≈. Similar studies have since been done for subsemigroups of the full transformation monoid, but the results are not nearly as conclusive here.
In this talk I will present my work on extending this analysis to the symmetric inverse monoid I_X, the inverse semigroup of bijections between subsets of X. We will see that many results from Sym(X) carry over directly, but we will also see how the tools developed for describing groups can fail in this more general setting.
17:00 - 18:00
Alan Logan
Title: Post's Correspondence Problem in Group Theory
Abstract: Post's Correspondence Problem (the PCP) is a classical decision problem that asks whether for pairs of free monoid morphisms g,h:Σ*→Δ* there exists any non-trivial x∈Σ* such that g(x)=h(x); see Wikipedia for more details. Post's Correspondence Problem for a group Γ takes pairs of group homomorphisms g,h:F(Σ)→Γ instead, and similarly asks whether there exists an x such that g(x)=h(x) holds for non-elementary reasons.
In this talk I will contrast this problem with the classical free monoid setting and its surrounding theory, and then sketch a proof that this problem is decidable for Γ virtually nilpotent. Joint work with Laura Ciobanu and Alex Levine.
Dinner 19:30 - 22:00
Day 2
June 16, Friday
9:00 - 10:00
Carl-Fredrik Nyberg Brodda
Title: One relator, many problems
Abstract: The word problem for one-relator groups was the first serious decision problem studied for groups. After dealing with free groups (zero-relator groups), one-relator groups provide the obvious next candidate for theory building, and in 1932 Magnus proved that the word problem is decidable in every one-relator group, setting the stage for all combinatorial group theory. One-relator groups are a natural class, but this type of step from zero relators to one relator may also be performed for any algebraic structure admitting free objects. For the purposes of this talk, I will consider three: groups, monoids, and inverse monoids. The second of these classes -- one-relation monoids -- is old, and was studied already by Thue in 1914. Here, there is a semblance of a general theory, but in spite of a century of efforts the word problem remains elusively open for this class. The third class -- one-relation inverse monoids -- is by contrast rather new, and has only seen serious study since the work by among others Margolis, Meakin, and Stephen in the 1990s and early 2000s. In recent years, a batch of unexpected results have appeared in this area -- most centrally the undecidability of the word problem!, which demonstrates a pressing need for a general theory to be developed here. In this talk, I will try and give an overview of how these three remarkable classes interact, and the many intricate manners in which (un)decidability results from any one of the three classes can be pushed through into the others. I will also mention how recent joint work with I. Foniqi & R. D. Gray has found new undecidability results for these three classes, including the discovery of the first known undecidable "real" problem for one-relation monoids.
10:00 - 11:00
Laure Daviaud
Title: Some applications of semigroup theory in formal verification.
Abstract: This will be an introductory talk to formal verification, where I will try to highlight some examples of the use of semigroups for deciding properties on computer systems.
I will refer to two specific pieces of work done in collaboration with Marianne Johnson (Manchester) and David Purser (Liverpool).
Coffee Break 11:00 - 11:30
Our main result is the following characterization of subgroups of a surface group:
11:30 - 12:00
Daniel Turaev
Title: Deciding the first order theory of the Plactic Monoid
Abstract: The plactic monoid is a monoid first studied in depth by Lascoux and Schutzenberger. It endows the set of Semistandard Young tableaux with a natural monoid structure, and became an algebraic structure of interest when Lascoux and Schutzenberger used it to prove the Littlewood-Richardson rule for Schur functions. It is naturally applicable to studying algebraic combinatorics and representation theory due to its link to Young tableaux, but has also been applied to algebraic geometry and Lie theory via crystal basis theory. When a monoid is finitely presented, a natural decision problem is whether this monoid has decidable first order theory. In this talk I will present the definition of a finitely presented plactic monoid and present a proof that all such monoids have decidable first order theory.
12:00 - 13:00
María Cumplido Cabello
Title: Solving the word problem in Artin groups without braid relations
Abstract: Artin groups are the groups defined by a finite set of generators and relations of the form sts...=tst... where s and t are generators and both words of the equality have the same length. Despite these groups are easily defined, they are quite mysterious: basic problems of classic group theory remain open, as it is the case for the word problem. There have been many (geometric and algebraic) approaches to solve the word problem for particular families of Artin groups (being the braid group the flagship example). In this talk we will explain a method of rewriting words that allows us to obtain geodesic representatives for elements in Artin groups that do not have a relation of length 3 (also known as braid relations) and, as a direct consequence, we will solve the word problem in this (big) family of Artin groups. This is a joint work with Rubén Blasco-García and Rose Morris-Wright.