Title: Applications of L systems to group theory,
Abstract: L systems generalise context-free grammars by incorporating parallel
rewriting, and generate languages such as EDT0L and ET0L that are strictly
contained in the class of indexed languages. In this paper we show that many of
the languages naturally appearing in group theory, and that were known to be
indexed or context-sensitive, are in fact ET0L and in many cases EDT0L. For
instance, the language of primitives in the free group on two generators, the
Bridson-Gilman normal forms for the fundamental groups of 3-manifolds or
orbifolds, and the co-word problem of Grigorchuk's group can be generated by L
systems. To complement the result on primitives in free groups, we show that
the language of primitives, and primitive sets, in free groups of rank higher
than two is context-sensitive. We also show the existence of EDT0L and ET0L
languages of intermediate growth.