The study of finite semigroups has its roots in Theoretical Computer Science. In particular, in the mid nineteen seventies, Eilenberg [2] 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 "pseudo varieties". 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 "k-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 [1] on the pseudovariety consisting of all "R-trivial semigroups".
References: [1] J. Almeida and M. Zeitoun, An automata-theoretic approach to the word problem for ω-terms over R, Theoret. Comput. Sci. 370 (2007), no. 1-3, 131-169. [2] S. Eilenberg, Automata, languages, and machines. Vol. B, Academic Press, New York - London, 1976.
(*) Célia Borlido is a student for the Joint PhD Program in Mathematics UC|UP working at the University of Porto in the area of “Semigroups, Automata and Languages” under the supervision of Prof. Jorge Almeida.
|