Frank Stephan: The complexity of verbal and pattern languages over groups

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 13 August 2014, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Frank Stephan

Title: The complexity of verbal and pattern languages over groups


Note: This meeting includes a short organisatorial session for organising
the logic seminar in this semester; in the case that you want to speak but
cannot come, please drop an email to Frank Stephan at

The talk presents 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, that verbal languages cannot
be context-free (unless they are either the empty word or the full group)
and that pattern languages cannot be regular (unless they are either a
singleton or the full group). Verbal languages and pattern languages 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.

Joint Work: This is joint work with Sanjay Jain and Alexei Miasnikov; the
talk builds on and extends work presented at LICS 2012.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.