The complexity of verbal languages over groups

Sanjay Jain, Alexei Miasnikov, Frank Stephan

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Scopus citations

Abstract

This paper investigates the complexity of verbal languages and pattern languages of Thurston automatic groups in terms of the Chomsky hierarchy. Here the language generated by a pattern is taken as the set of representatives of all strings obtained when chosing values for the various variables. For noncommutative free groups, it is shown that the complexity of the verbal and pattern languages (in terms of level on the Chomsky hierarchy) does not depend on the Thurston automatic representation and that verbal languages cannot be context-free (unless they are either the empty word or the full group). They can however be indexed languages. Furthermore, it is shown that in the general case, it might depend on the exactly chosen Thurston automatic representation which level a verbal language takes in the Chomsky hierarchy. There are examples of groups where, in an appropriate representation, all pattern languages are regular or context-free, respectively.

Original languageEnglish
Title of host publicationProceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2012
Pages405-414
Number of pages10
DOIs
StatePublished - 2012
Event2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2012 - Dubrovnik, Croatia
Duration: 25 Jun 201228 Jun 2012

Publication series

NameProceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2012

Conference

Conference2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2012
Country/TerritoryCroatia
CityDubrovnik
Period25/06/1228/06/12

Keywords

  • Chomsky Hierarchy
  • Free Groups
  • Thurston Automatic Groups
  • Verbal Languages

Fingerprint

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

Cite this