Groups whose geodesics are locally testable

Sarah Rees


group geodesics, regular languages, locally testable, starfree


published in Int. J. Alg. Comput.


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.