The complexity of verbal languages over groups

This paper investigates the complexity of verbal languages and pattern languages of automatic groups in terms of the Chomsky hierarchy (regular languages, context-free languages, context-sensitive languages, recursively enumerable languages). For non-Abelian free groups with finitely many generators, the following is shown: the level of a language in the Chomsky hierarchy is independent of the automatic representation; the context-free verbal languages are only the full group and the language of the empty word; the regular pattern languages are either a singleton or the full group; verbal languages are, however, indexed languages by a result of Ciobanu, Diekert and Elder. For some groups, it depends on the exactly chosen automatic representation whether a pattern language is regular, context-free or context-sensitive.