TY - JOUR
T1 - The complexity of verbal languages over groups
AU - Jain, Sanjay
AU - Miasnikov, Alexei
AU - Stephan, Frank
N1 - Publisher Copyright:
© 2018 Elsevier Inc.
PY - 2019/5
Y1 - 2019/5
N2 - 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.
AB - 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.
KW - Automatic groups
KW - Chomsky hierarchy
KW - Free groups
KW - Pattern languages
KW - Verbal languages
UR - http://www.scopus.com/inward/record.url?scp=85057072722&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85057072722&partnerID=8YFLogxK
U2 - 10.1016/j.jcss.2018.10.005
DO - 10.1016/j.jcss.2018.10.005
M3 - Article
AN - SCOPUS:85057072722
SN - 0022-0000
VL - 101
SP - 68
EP - 85
JO - Journal of Computer and System Sciences
JF - Journal of Computer and System Sciences
ER -