Groups whose geodesics are locally testable
Sarah Rees
Keywords
group geodesics, regular languages, locally testable, starfree
Status
published in Int. J. Alg. Comput. 18 (2008) 911-923.
Abstract
A regular set of words is ($k$-)locally testable if membership of a word
in the set is determined by the nature of its subwords of some bounded
length $k$. In this article we study groups for which the set of all geodesic
words with respect to some generating set is ($k$-)locally testable,
and we call such groups ($k$-)locally testable.
We show that a group is \klt{1} if and only if it is free abelian.
We show that the class of ($k$-)locally testable groups
is closed under taking finite direct products.
We show also that a locally testable group
has finitely many conjugacy classes of torsion elements.
Our work involved computer investigations of specific groups, for which
purpose we implemented an algorithm in \GAP\ to compute a finite state automaton
with language equal to the set of all geodesics of a group (assuming that this
language is regular), starting from a shortlex automatic structure.
We provide a brief description of that algorithm.
\
The preprint is available as gzipped
dvi (28 kB),
postscript (164 kB) and
pdf files.
Alternatively, you can request a copy by
e-mailing me.