The study of finite semigroups has its roots in Theoretical Computer Science. In particular, in the
The study of finite semigroups has its roots in Theoretical Computer Science. In particular, in the mid nineteen seventies, Eilenberg~\cite{MR0530383} established the link between ``varieties of rational languages'', which is an important object of study in Computer Science, and certain classes of finite semigroups, known as ``pseudovarieties''.   At the level of pseudovarieties, some problems arise naturally, one of them being the so-called ``word problem''. Roughly speaking, it consists in deciding whether two expressions define the same element in every semigroup of a given pseudovariety.   In this talk, we start by introducing some basic background on finite semigroups. Our first goal is to explain what the ``$\kappa$-word problem over $DRG$'' is about. After that, based on some illustrative examples, we intend to give intuition on how to show that the referred problem is decidable. Our solution extends work of Almeida and Zeitoun~\cite{MR2289710} on the pseudovariety consisting of all ``$\mathcal{R}$-trivial semigroups''. \begin{thebibliography}{1} \bibitem{MR2289710} J.~Almeida and M.~Zeitoun, \emph{An automata-theoretic approach to the word problem for {$\omega$}-terms over~{$\sf{R}$}}, Theoret. Comput. Sci. \textbf{370} (2007), no.~1-3, 131--169. \bibitem{MR0530383} S.~Eilenberg, \emph{Automata, languages, and machines. {V}ol. {B}}, Academic Press, New York-London, 1976.

Date and Venue

Start Date
Venue
Room 5.5, Department of Mathematics, University of Coimbra

Speaker

Célia Borlido

Speaker's Institution

University of Porto

Area

Research Seminar Program (UC|UP MATH PhD program)