05/05/2017, 15:00 — 16:00 — Sala 6.2.38, Faculdade de Ciências da Universidade de Lisboa
Tara Brough, Centro de Matemática e Aplicações, UNL
Word problems of free inverse monoids
In semigroups, $y$ is an inverse of $x$ if $xyx = x$ and $yxy = y$. An inverse monoid is a monoid (semigroup with identity) in which every element has a unique inverse. I will describe the free objects in the category of inverse monoids: for any set $X$, the free inverse monoid on $X$ is denoted $\operatorname{FIM}(X)$. The word problem of a monoid is, informally, the problem of deciding whether two words over a given generating set represent the same element of the monoid. I will explain how this can be considered as a formal language, and discuss the language type (e.g. context-free, context-sensitive) of the word problem of $\operatorname{FIM}(X)$ for a finite set $X$.
The talk will focus primarily on the rank 1 case, in which words over the standard generating set can be viewed as walks in one dimension.
