Please use this identifier to cite or link to this item: https://doi.org/10.1109/LICS.2012.50
Title: The complexity of verbal languages over groups
Authors: Jain, S. 
Miasnikov, A.
Stephan, F.
Keywords: Chomsky Hierarchy
Free Groups
Thurston Automatic Groups
Verbal Languages
Issue Date: 2012
Source: Jain, S., Miasnikov, A., Stephan, F. (2012). The complexity of verbal languages over groups. Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2012 : 405-414. ScholarBank@NUS Repository. https://doi.org/10.1109/LICS.2012.50
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. © 2012 IEEE.
Source Title: Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2012
URI: http://scholarbank.nus.edu.sg/handle/10635/41115
ISBN: 9780769547695
DOI: 10.1109/LICS.2012.50
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

4
checked on Dec 6, 2017

WEB OF SCIENCETM
Citations

3
checked on Nov 19, 2017

Page view(s)

47
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.