The main problem considered in this talk is the problem of
determining,
given a rational subset of a certain group, whether or not this subset
is recognizable.
In a 1996 paper, Géraud Sénizergues answered this question for
free groups in the process of proving a
conjecture proposed by Jacques Sakarovitch in 1979: every rational
subset of the free group must be either recognizable or disjunctive
(the corresponding syntactical congruence is the identity).
We developed two alternative approaches
to Sénizergues's that allow us to obtain various algorithmic
characterizations of recognizability as well as alternative proofs of
Sénizergues's results, including the conjecture of Sakarovitch.
The first approach uses techniques inspired by the study of inverse monoids and inverse automata and provides a wide variety of characterizations, sheding further light on recognizability in this setting.
The second approach is more universal and allows generalizations to other classes of groups, namely to free Abelian groups and also to the general case of finite extensions. As a consequence, we are able to provide a simple and elegant proof for Sakarovitch's conjecture.
Other decidability problems related to rational subsets of groups will be also discussed.
Sponsored in part by the FCT approved projects POCTI 32817/99 and POCTI/MAT/37670/2001 in participation with the European Community Fund FEDER and by FCT through Centro de Matemática da Universidade do Porto. Also sponsored in part by FCT, the Faculdade de Ciências da Universidade do Porto, Programa Operacional Ciência, Tecnologia, Inovação do Quadro Comunitário de Apoio III, and by Caixa Geral de Depósitos.