ABSTRACT: The geodesic words in a finitely generated group are known to form a regular set whenever the group is either word hyperbolic or free abelian. For selected generating sets, the same is true for virtually abelian groups, geometrically finite hyperbolic groups, all Coxeter groups, Artin groups of finite type and indeed all Garside groups; this list does not claim to be exhaustive.
I report on an investigation to look for connections between algebraic properties of such a group, combinatorial properties of its presentations, the structure of its regular set of geodesics, and the complexity of its word problem. That work is joint work with Gilman, Hermiller and Holt.
Terms such as regularity, star-freedom and local testability will be defined in the talk; each can be shown to have several different disguises (set-theoretic, geometric, or algebraic, in terms of an associated finite semigroup). We shall see in particular that certain small cancellation conditions on a presentation (which imply word hyperbolicity) force the set of geodesic words to be star-free, that a rather restrictive (but also natural) form of local testability of geodesics implies that the word problem for that group is context-free, and hence characterises virtually free groups, that 1-local testability characterises free abelian groups, and that in general a group with locally testable geodesics can have only finitely many conjugacy classes of torsion elements.