# Aggregation-based automata minimisation.

## Speaker:

Johanna Björklund

## Date:

Friday, 26 May, 2017 (All day)

## Venue:

Room FC1.004, DMat-FCUP at 14:30

This is a joint work w. Loek Cleophas, Eindhoven University.

# Revisiting concatenation hierarchies of regular languages

Marc Zeitoun

## Date:

Friday, 19 May, 2017 (All day)

## Venue:

Room FC1.004, DMat-FCUP at 15:30

This talk addresses the following question: which languages can we define over a finite alphabet, starting from the class consisting of the empty set only, and alternating two operations a prescribed number of times: (1) Boolean closure and (2) polynomial closure? This basic problem, strongly related to logical definability in first-order logic, is wide open since the early 70s. I will introduce a strengthening of this question, and argue that this harder problem is actually easier to deal with than the original one.

# Green's relations in transformation semigroups.

## Speaker:

Manfred Kufleitner

## Date:

Friday, 19 May, 2017 (All day)

## Venue:

Room FC1 004, DMat-FCUP at 14:30

This is joint work with Lukas Fleischer.

We consider the complexity of Green's relations when the semigroup is given by transformations on a finite set.

# Stone Duality and the Substitution Principle.

Célia Borlido

## Date:

Friday, 5 May, 2017 (All day)

## Venue:

Room FC1 004, DMat-FCUP at 14:30

Finite and profinite monoids have proved to be a powerful tool in the study of regular languages. In particular, understanding the interplay between the topological and algebraic structures of these objects has been crucial. However, many of the classes of languages that are of interest to study are not regular, and so, those theories no longer apply. Boolean spaces with biactions of monoids were recently proposed as suitable objects to handle classes of (not necessarily regular) languages.

# Computing topological closures through algebraic recognition.

Jorge Almeida

## Date:

Friday, 3 March, 2017 (All day)

## Venue:

Room FC1.006, DMat-FCUP

One of the key problems that has been considered on a pseudovariety V of finite monoids consists in deciding whether a given finite system of equations with rational constraints has a solution in every monoid from V. An instance of this problem is the separation problem, which has received considerable attention lately due to its role in investigations on the Straubing-Thérien hierarchy of star-free languages.

# Duality theory in the study of formal languages.

Célia Borlido

## Date:

Monday, 20 February, 2017 - 14:30

## Venue:

Room FC1.004, DMat-FCUP

In 2008, Gehrke, Grigorieff, and Pin proposed Stone duality as a means for studying Boolean algebras of (non-necessarily regular) languages. They showed how that tool could be understood as a generalization of some key concepts found in the study of varieties of regular languages, such as the syntactic monoid of a language. In this talk, I will present the main points of this approach.

# Word problems of free inverse monoids as languages.

Tara Brough

## Date:

Friday, 10 February, 2017 - 14:30

## Venue:

Room FC1.004, DMat-FCUP

Let FIM(X) be the free inverse monoid on a finite set X. The word problem of FIM(X) is easily seen to be recognisable in linear space (e.g. using Munn trees), and this has been improved to log space (Lohrey and Ondrusch 2007).

# On finite simple quotients of triangle groups.

Claude Marion

## Date:

Monday, 5 December, 2016 - 17:00

## Venue:

Room FC1.031, DMat-FCUP

In the 1980s, following the classification of   finite simple groups, it was established that every finite simple group can be generated by two elements. A natural question arises: can we impose restrictions on these generators? Given a triple (a,b,c) of positive integers, we say that a finite group is an (a,b,c)-group if it can be generated by two elements of respective orders dividing a and b,  and having product of order dividing c. In other words, an (a,b,c)-group is a finite quotient of the triangle group

# The reflexible to chiral ratio of regular oriented maps.

## Speaker:

António Breda D’azevedo

## Date:

Thursday, 17 November, 2016 - 14:30

## Venue:

Room FC1.006, DMat-FCUP

Regular maps consist of triples $(G,a,b)$ where $G$ is a finite group and $(a,b)$ is a pair of generators of $G$ such that the product $ab$ is an involution. A regular map ${\cal M}=(G,a,b)$ is reflexible, or chiral, according as $\cal M$ is isomorphic, or not, to its mirror image $\overline{{\cal M}}=(G,a^{-1},b^{-1})$.

# Locally testable languages and group languages with partial commutations.

Giovanna Guaiana

## Date:

Thursday, 20 October, 2016 - 13:30

## Venue:

Room FC1.006, DMat-FCUP

The study of the trace monoid was initiated by A. Mazurkiewicz in 1977, and it was later developed, motivated by its interpretation as a model to describe the behaviour of concurrent systems. When a partial commutation (often called independence relation) is fixed over the letters of an alphabet, stating what letters can commute, a trace can be identified with an equivalence class of words that can be obtained from one another by switching successively some consecutive independent letters.