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.