The complexity of verbal languages over groups

Sanjay Jain, Alexei Miasnikov, Frank Stephan

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)68-85
Number of pages18
JournalJournal of Computer and System Sciences
Volume101
DOIs
StatePublished - May 2019

Keywords

  • Automatic groups
  • Chomsky hierarchy
  • Free groups
  • Pattern languages
  • Verbal languages

Fingerprint

Dive into the research topics of 'The complexity of verbal languages over groups'. Together they form a unique fingerprint.

Cite this