Texas A&M University, Department of
Mathematics, 216 Milner Hall, 12th of April 2006, 4:00-4:50
Groups and Dynamics Seminar
Rational
subsets of groups
Benjamin Steinberg of Carleton
University
A rational subset of a group G is a subset that can be recognized by a
finite state G-automaton. Such sets include finitely generated
subgroups and subsemigroups as
well as double cosets of finitely generated subgroups. A theorem
of Anissimov and Seifert shows
that a subgroup of a finitely generated group is rational if and only
if it is finitely generated, One
can study decidability of the membership problem for rational subsets.
Decidability of this problem implies
decidability of the generalized word problem as well as decidability of
the order of an element of the group.
Results prior to this talk are: free groups have decidable
rational subset membership (Benois); abelian groups have decidable
rational subset membership
(Eilenberg/Schutzenberger); decidability of the rational subset problem
is a virtual property (Grunschlag).
We prove a combination theorem showing that the class of groups with
decidable rational subset problem is closed under taking finite graphs
of groups with finite edge groups.
Also we use classical results from formal language theory
(Chomsky-Schutzenberger/Parikh theorems) to show that the rational
subset problem is decidable for the direct product of a free group and
a free abelian group. This is joint work with
Silva and Kambites.