Titles and abstracts of the talks

Jorge Almeida (Porto)

Title: A geometric interpretation of the Schtzenberger group of a minimal subshift

Abstract: To each irreducible subshift over a finite alphabet, one may naturally associate a regular J-class of the free profinite semigroup on the same alphabet, and thus a well-defined abstract profinite group, which is called the Schtzenberger group of the subshift. In this talk, we provide a geometric interpretation of this group in the case of minimal subshifts. Indeed, it can be obtained as a natural inverse limit of profinite completions of homotopy groups of graphs combinatorially associated with the minimal subshift, namely a suitable variant of its Rauzy graphs. (Joint work with Alfredo Costa)

Jean-Camille Birget (Rutgers University, Camden)

Title: Semigroups and one-way functions

Abstract: A one-way function is a function f on bit-strings such that f is computable in deterministic polynomial time, and f is polynomially balanced (i.e., the input length is polynomially bounded from above in terms of the output length), but no inverse of f is computable in deterministic polynomial time. (These are "worst-case one-way functions", not cryptographic one-way functions. It is know that P is different from NP iff worst-case one-way functions exist.)

The Thompson-Higman groups can be generalized to monoids. These have interesting algebraic and computational properties. The Thompson-Higman monoids can be further generalized by taking prefix codes and functions that are accepted, respectively computed, in deterministic polynomial time. In the resulting monoid, fP, the non-regular elements are the worst-case one-way functions; fP has many interesting properties.

Volker Diekert (Stuttgart)

Title: Local Divisors and Church-Rosser Languages

Abstract: Local divisors have been introduced in semigroup theory as a tool for proving results by a refined induction method. The scheme splits a ``big'' induction step into many tiny ``baby'' steps. Over the past few years it turned out to be useful in various and quite different areas. For example it led to a simplified proof for the Krohn-Rhodes decomposition theorem by Manfred Kufleitner, Benjamin Steinberg and myself.

Using local divisors we were also able to prove in 2012 that regular languages are Church-Rosser congruential. This solved a problem, which was open for more 25 years. The solution received the best paper award at ICALP 2012, Track B. In my talk I will focus on aperiodic monoids, where an even stronger result is true. This part was obtained in a joint work with Manfred Kufleitner and Pascal Weil.

Robert Gray (University of East Anglia)

Title: Finite Grbner-Shirshov bases for Plactic algebras and biautomatic structures for Plactic monoids

Abstract: The Plactic monoid has its origins in work of Schensted (1961) and Knuth (1970) concerned with certain combinatorial problems and operations on Young tableaux. It was later studied in depth by Lascoux and Schtzenberger (1981) and has since become an important tool in several aspects of representation theory and algebraic combinatorics. Various aspects of the corresponding semigroup algebras, the Plactic algebras, have been investigated, for instance in Cedo & Okniski (2004), and Lascoux & Schtzenberger (1990). In this talk I will discuss a result in which we show that every Plactic algebra of finite rank admits a finite Grbner-Shirshov basis. The result is proved by using the combinatorial properties of Young tableaux to construct a finite complete rewriting system for the corresponding Plactic monoid. Also, answering a question of Efim Zelmanov, I will explain how this rewriting system and other techniques may be applied to show that Plactic monoids of finite rank are biautomatic. These results are joint work with A. J. Cain and A. Malheiro.

Mark Kambites (Manchester)

Title: The Geometry of Tropical Matrix Semigroups

Abstract: The tropical semiring is (roughly speaking) the algebraic structure formed by the real numbers under the operations of addition and maximum. It arises naturally (and indeed has often been independently rediscovered) in diverse areas of mathematics, including formal language theory, process control and modelling, combinatorial optimization and scheduling, phylogenetics and algebraic geometry to name but a few. I will report on recent progress in understanding the semigroup of tropical matrices, and its relationship to the geometry of tropical polytopes.

Olga Kharlampovich (Hunter College CUNY)

Title: Algorithmic problems for hyperbolic and toral relatively hyperbolic groups.

Abstract: One can associate to any subgroup of a free group a so-called Stallings automaton, i.e. a finite oriented labeled graph, that accepts only elements of H. Given generators of a finitely generated subgroups H and K of a free group F we can compute their bases, solve the membership problem, find intersections of their conjugates etc. using Stallings automata. We will describe how to construct similar automata for finitely generated relatively quasi-convex subgroups of toral relatively hyperbolic groups and how to solve different algorithmic problems for them. We will apply these (and other) results to give algorithms for different model-theoretic constructions in hyperbolic groups. These are joint results with A. Myasnikov and P. Weil.

Markus Lohrey (Leipzig)

Title: Rational subsets of wreath products

A subset of a group G is called rational if it is a homomorphic image of a regular set of words. The rational subset membership problem for a finitely generated group G asks whether a given group element belongs to a given rational subset of G. This problem generalizes the classical subgroup membership problem (generalized word problem). Only very few classes of groups with decidable rational subset membership problems are known. Examples are free groups, f.g. abelian groups and certain graph groups. In this talk, we will consider the rational subset membership problem for wreath products. We will sketch proofs for the following two results: i) The rational subset membership problem is decidable for every wreath product H wr V, where H is a finite group and V is virtually free (this includes e.g. the famous lamplighter group). ii) The rational subset membership problem is undecidable for the wreath product Z wr Z (where Z is the group of integers). Actually, undecidability already holds for a fixed finitely generated submonoid of Z wr Z.

This is joint work with Benjamin Steinberg (CCNY) and Georg Zetzsche (Univ. Kaiserslautern).

Alex Lubotzky (Hebrew University of Jerusalem)

Sieve method in group theory

Abstract: The sieve methods are classical methods in number theory. Inspired by the 'affine sieve method' developed by Sarnak, Bourgain, Gamburd and others, as well as by works of Rivin and Kowalsky, we develop in a systematic way a 'sieve method' for group theory. This method is especially useful for groups with 'property tau'. Hence the recent results of Breuillard-Green-Tao, Pyber-Szabo, Varju and Salehi-Golsefidy are very useful and enables one to apply them for linear groups. We will present the method and some of its applications to linear groups, mapping class groups and Aut(F_n).

Alexander Olshanskii (Vanderbilt)

Title: On group embeddings and their asymptotic invariants

Abstract.

Jean-Eric Pin (LIAFA, CNRS, Paris-7)

Title: Automata, semigroups and groups: 60 years of synergy.

Abstract. This will be a survey lecture on the interactions between automata, semigroups and groups over the past sixty years.

John Rhodes (Berkeley)

Title: Boolean representations of matroids and simplicial complexes with applications to semigroups.

Abstract: The definition of a boolean representation of a matroid and a simplicial complex will be given. A general theory will be outlined including that all matroids have boolean representations and calculating the minimum boolean representations of some classical matroids. Relations with the shellability of a simplicial complexes will be considered. Finally applications to semigroups will be given.

This is current research with Pedro Silva, based on some previous research by Zur Izhakian and the author.

Luis Ribes (Carleton University)

Title: Profinite methods in abstract groups (On the sixtieth birthday of Stuart Margolis)

Abstract: I shall review some results in groups that are obtained using profinite graphs and groups. As a sample I mention the following proposition. Let R be an abstract group that contains a free group of finite index (R is free-by-finite). Let H be a subgroup of R which is either finite or finitely generated torsion-free. Then H is conjugacy distinguished; i.e., if a ∈ R, then H contains a conjugate of a in R if and only if the analogous property holds for the images of a and H in every finite quotient of R.

Eliyahu Rips (Hebrew University, Jerusalem)

Title: Free n-Engel groups

Abstract: This is a joint work with Arye Juhasz. We study n-Engel groups for n sufficiently big, say n>=40. We use the generalized small cancellation theory in the version appearing in the paper in Israel J. Math. (1982). For this, we need to determine the structure of contiguity diagrams. We introduce canonical representatives using a certain 3 step procedure, and then we explicitly describe the combinatorics of the contiguity diagrams.

Anne Schilling (UC Davis)

Title: The power of R-trivial monoids

Abstract: R-trivial monoids have proven to be an interesting class of monoids leading to Markov chains where eigenvalues and multiplicities can be explicitly computed. We introduce new examples of ergodic Markov chains (such as a Markov chain on reduced words for the longest element of finite Coxeter groups, nonabelian sandpile models and Toom models), prove that their transition monoid is R-trivial, and use monoid theory to analyze them explicitly. This is joint work with Arvind Ayyer, Benjamin Steinberg and Nicolas Thiery.

Lev Shneerson (Hunter College, CUNY)

Title: On the growth and Gelfand- Kirillov dimension of finitely presented inverse semigroups

Abstract: We will speak on the asymptotic behavior of finitely presented inverse semigroups. It is shown that for any positive integer n there exists an inverse semigroup of rank n given by a presentation with n generators, n-1 relations and having polynomial growth.

It is proved that if a finitely presented Rees quotient S of a free inverse semigroup has polynomial growth then S is monogenic (with zero) or at least three relators must be used. The three relator case is fully characterized yielding a sequence of two-generator three-relator semigroups whose Gelfand-Kirillov dimensions form an infinite set. This part of the talk is based on joint work with David Easdown (University of Sydney, Australia).

Pedro V. Silva (Porto)

Title: Fixed points for groups and monoids

Abstract: In 2012, the study of fixed points constituted the main theme of my research. On my own or through joint work, I obtained results for several important classes of groups and semigroups, using very different techniques. The purpose of this talk is to report on this work. Using automata-theoretic techniques, I could generalize to virtually free groupsand (virtually injective) endomorphisms results proved by Gersten or Cooper for free group automorphisms. For the finite fixed points, I obtained a finiteness theorem for free group mappings defined through inverse transducers, leading to an alternative proof of Sykiotis' theorem on virtually free groups. For the infinite fixed points, a finiteness theorem on the regular orbits was also proved, as well as a classification theorem generalizing the theorem proved for free groups by Gaboriau, Jaeger, Levitt and Lustig. In joint work with Rodaro and Sykiotis, we could settle some of the questions outlined above in the context of graph groups (also known as right angled Artin groups), for both automorphisms and arbitrary endomorphisms. The finiteness properties turn out to depend on the nature of the commutation graph. As far as finite fixed points are concerned, the situation is simplified when we replace graph groups by trace monoids, their monoid-theoretic equivalent, but in this context, in joint work with Rodaro, we could extend the discussion to the infinite fixed points of the continuous extension to real traces. Also with Rodaro, but using very different techniques, we could prove that the periodic point submonoid of a free inverse monoid endomorphism is always finitely generated, and we could establish the nature of the fixed point submonoid with respect to Chomsky's hierarchy.

Ben Steinberg (CUNY, New York)

Title: Combinatorial topology and the global dimension of left regular bands

Abstract: In recent years work of Bidigare, Hanlon and Rockmore, Diaconis and Brown, Chung and Graham -- and others -- has shown that the representation theory of left regular bands (LRBs) is a powerful tool for analyzing Markov chains. They are also closely related to classical topics in representation theory like Solomon's descent algebra for a finite Coxeter group and the representation theory of quivers (which can be viewed as a special case of the representation theory of LRBs). In this talk we compute the cohomological dimension of an LRB over any base ring and the global dimension over a field using techniques from algebraic topology. The key result is that the augmented chain complex of the order complex of the R-order provides a projective resolution of the trivial module. As a consequence we obtain a new interpretation of the Leray number of a flag complex, which arises for instance in the theory of Stanley-Reisner rings, as the global dimension (in fact cohomological dimension) of the corresponding right-angled Artin LRB. This is joint work with Stuart Margolis and Franco Saliola

Mikhail Volkov (Ekaterinburg)

Title: Primitive digraphs, Markov chains and synchronizing automata

Abstract: It is well known that the underlying digraph of a strongly connected synchronizing automaton is primitive. Trahtman's proof of the Road Coloring Conjecture shows that, conversely, every strongly primitive primitive digraph can be endowed with the structure of a synchronizing automaton. On the qualitative level, experiments with synchronizing automata have revealed a remarkable similarity between the distribution of their reset thresholds and the distribution of exponents of primitive digraphs. Analyzing connections between these two parameters, we have been able to deduce in a uniform way several series of slowly synchronizing automata, both new and already known ones, from some classic series of primitive digraphs with large exponents. We have also suggested a sequence of notions intermediate between primitivity and synchronizability. The sequence in a sense converges to synchronizability and so we hope that studying it may shed new light on the Černý conjecture. We also assign to each strongly connected synchronizing automaton a family of Markov chains and discuss connections between the stationary distributions of these Markov chains and the reset threshold of the automaton.