# Random walks on semaphore codes and delay de Bruijn semigroups.

## Speaker:

Pedro V. Silva (FCUP / CMUP)

## Date:

Friday, 6 November, 2015 - 14:30

## Venue:

Room FC1.004, DMat-FCUP

In joint work with John Rhodes (University of California at Berkeley) and Anne Schilling (University of California at Davis), a new approach to random walks on de Bruijn graphs over the alphabet $A$ is developped through right congruences on $A_k$, defined using the natural right action of $A^+$. Right congruences may be approximated by special right congruences, which correspond to semaphore codes and allow an easier computation of the hitting time.

# Prefix and Right-Partial Derivative Automata.

## Speaker:

Eva Maia (FCUP/CMUP)

## Date:

Tuesday, 16 June, 2015 - 14:30

## Venue:

Room FC1.029, DMat-FCUP

Recently, Yamamoto presented a new method for the conversion from regular expressions (REs) to non-deterministic finite automata (NFA) based on the Thompson $\varepsilon$-NFA ($\at$). The $\at$ automaton has two quotients  discussed: the suffix automaton $\asuf$ and the prefix automaton, $\apre$.  Eliminating $\varepsilon$-transitions in $\at$, the Glushkov automaton ($\mathcal{A}_{pos}$) is obtained. Thus, it is easy to see  that $\asuf$ and the partial derivative automaton ($\apd)$ are the same.

# On Syntactic Structures.

## Speaker:

Libor Polák (University Brno, Czech Republic)

## Date:

Tuesday, 16 June, 2015 - 13:30

## Venue:

Room FC1.029, DMat-FCUP

The algebraic language theory contributes to the classification of regular languages and to the decision of memberships of a given language to various important classes of languages (star-free, piecewise testable, ...). The crucial notion is here the variety of languages (for each finite alphabet A one has a Boolean algebra $\mathcal{V}(A)$ of regular languages over $A$ which is closed with respect to quotients, and for each morphism $f:B^*\to A^*$ and $L\in \mathcal{V}(A)$ one has also $f^{-1}(L)\in\mathcal{V}(B)$.

# Distinguishability Operations and Closures on Regular Languages.

## Speaker:

Rogério Reis (FCUP/CMUP)

## Date:

Friday, 24 April, 2015 - 13:30

## Venue:

Room FC1.007, DMat-FCUP

Given a regular language $L$, we study the language of words $dis{L}$, that  distinguish between pairs of different left-quotients of $L$. We characterize this distinguishability operation, show that its iteration has always a fixed point, and we generalize this result to operations derived from closure operators and Boolean operators.

# Drift and Entropy of Random Walks on Regular Languages.

## Speaker:

Lorenz Gilch (University of Graz, Austria)

## Date:

Thursday, 16 April, 2015 - 11:00

## Venue:

Room FC1.006, DMat-FCUP

In this talk, I will collect some results about random walks on regular languages over a finite alphabet. For this purpose, I will give a brief introduction to random walks on regular languages. Afterwards I will present some results about the rate of escape and the asymptotic entropy of these random walks: I will sketch the proofs for existence of the rate of escape and the entropy (including formulas). The main idea is to cut the random walk into pieces such that this sequence of pieces form a Markov chain. Finally, I will summarize some important properties.

# The Word Problem for Omega Terms over Two Variable Logic.

## Speaker:

Jan Philipp Wächter (University of Stuttgart, Germany)

## Date:

Friday, 20 March, 2015 - 17:00

## Venue:

Room FC1.029, DMat-FCUP

The word problem for omega terms over a variety (of finite monoids) V is the following decision problem: given two omega terms alpha and beta, does the equation alpha = beta hold for all monoids in V? For the variety DA - which is connected to two variable first order logic FO2[<] - this question can be solved using "rankers". Rankers were introduced by Weis and Immerman based on the turtle programs of Schwentick, Therien and Vollmer and are connected to Lodaya, Pandya and Shah's interval temporal logic.

# The Karoubi envelope and the Schützenberger category of a semigroup.

## Speaker:

Alfredo Costa (FCTUC/CMUC)

## Date:

Friday, 13 March, 2015 - 14:30

## Venue:

Room FC1.006, DMat-FCUP

The Karoubi envelope plays a fundamental role in Tilson's Delay theorem. It is also known that two semigroups with local units are Morita equivalent if and only if they have equivalent Karoubi envelops.

We introduce a new category, the Schützenberger category of a semigroup, which stands in relation to the Karoubi envelop of the semigroup as the Schützenberger groups stand to maximal subgroups. We analyze some aspects of this relationship, with an emphasis on the case of semigroups with local units.

This is joint work with Benjamin Steinberg.

# The congruence $\eta^\ast$ on semigroups.

## Speaker:

M. Hossein Shahzamanian (CMUP)

## Date:

Friday, 20 February, 2015 - 14:30

## Venue:

Room FC1.029, DMat-FCUP

In this work, we define a congruence $\eta^{\ast}$ on semigroups. For the finite semigroups $S$,  $\eta^{\ast}$ is the smallest congruence relation such that $S/ \eta^{\ast}$ is a nilpotent semigroup (in the sense of Malcev).  In order to study the congruence relation $\eta^{\ast}$ on finite semigroups, we define a $\textbf{CS}$-diagonal finite regular Rees matrix semigroup. We prove that, if $S$ is a $\textbf{CS}$-diagonal finite regular Rees matrix semigroup then $S/ \eta^{\ast}$ is inverse.

# On the Freeness of Automata Groups.

## Speaker:

Emanuele Rodaro (CMUP)

## Date:

Friday, 6 February, 2015 - 14:30

## Venue:

Room FC1.004, DMat-FCUP

We present a geometric approach to groups defined by transducers via the notion of enriched dual. We prove that the boundary dynamics $Q^{\omega}$ of the (semi)group generated by the enriched dual transducer characterizes the algebraic property of being free for an automaton group.

# Depth parameters of finite semigroups.

## Speaker:

Nasim Karimi (FCUP / CMUP)

## Date:

Friday, 23 January, 2015 - 14:30

## Venue:

Room FC1.004, DMat-FCUP

In the first part of this talk we investigate the minimum length of elements in the minimum ideal  of a finite semigroup. We denote this parameter by N(S,A), where A is a generating set of the finite semigroup S, and we call it A-depth of S.  Then we introduce depth parameters for a finite semigroup. We estimate the depth parameters for some families of finite semigroups and give an upper bound for N(S) where S is a wreath product or a direct product of two finite (transformation) monoids.