TY - GEN
T1 - The complexity of verbal languages over groups
AU - Jain, Sanjay
AU - Miasnikov, Alexei
AU - Stephan, Frank
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
KW - Chomsky Hierarchy
KW - Free Groups
KW - Thurston Automatic Groups
KW - Verbal Languages
UR - http://www.scopus.com/inward/record.url?scp=84867189034&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84867189034&partnerID=8YFLogxK
U2 - 10.1109/LICS.2012.50
DO - 10.1109/LICS.2012.50
M3 - Conference contribution
AN - SCOPUS:84867189034
SN - 9780769547695
T3 - Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2012
SP - 405
EP - 414
BT - Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2012
T2 - 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2012
Y2 - 25 June 2012 through 28 June 2012
ER -