Star-free geodesic languages for groups
Susan Hermiller, Derek Holt and Sarah Rees
Keywords regular languages, starfree languages, geodesics
Status published in International Journal of Algebra and Computation 17 (2007) 329--345
In this article we show
that every group with a finite presentation
satisfying one or both of the small cancellation conditions
$C'(1/6)$ and $C'(1/4)-T(4)$ has the property that the
set of all geodesics (over the same generating set)
is a star-free regular language. Star-free regularity
of the geodesic set is shown to be dependent on
the generating set chosen, even for free groups.
We also show that the class of groups
whose geodesic sets are star-free with respect
to some generating set is closed under
taking graph (and hence free and direct) products,
and includes all virtually abelian groups.
The preprint is available as gzipped
dvi (36 kB) and
postscript (180 kB) files.
Alternatively, you can request a copy by