In the early 1980’s, in the early days of the theory of automatic groups (which associates with some groups normal forms which are regular languages, that is, sets of strings recognised by finite state automata, essentially as an expression of certain finiteness properties of these groups) questions started to be asked about what the structure of a regular language associated with a group might reveal about the group itself.
In particular semigroup theorists Rhodes and Margolis conjectured that the regular set of all geodesics of a word hyperbolic group in any presentation must always be a star-free set, that is, expressible in terms of finite sets using only the operations of union, intersection, concatenation and complementation (but without the Kleene closure operation which is needed in addition to find expressions for the full range of regular sets). Since the star-free languages form a natural, low complexity subclass of the regular languages, such a result would be in line with the low complexity of the solution of the word problem for these groups. Recently, Holt (Warwick), Hermiller (Nebraska) and I started to examine Margolis and Rhodes’s conjecture.
We found it to be false, indeed we found a presentation of a free group for which the set of geodesics is not star-free. But nontheless we can prove that certain small cancellation conditions on a presentation (which imply word hyperbolicity) do make a group star-free, so Margolis and Rhodes were not far off.
I shall discuss these results and others which relate the structure of sets of geodesics in a group to the properties of the group itself.