CARMA Seminar

4:00 pm

Thursday, 16th May 2013

V129, Mathematics Building

Assoc Prof Murray Elder

(CARMA, The University of Newcastle)

C-graph automatic groups

Graph automatic groups are an extension of the notion of an automatic group, introduced by Kharlampovich, Khoussainov and Miasnikov in 2011, with the intention to capture a wider class of groups while preserving computational properties such as having quadratic time word problem. We extend the notion further by replacing regular with more general language classes. We prove that nonsolvable Baumslag-Solitar groups are (context free)-graph automatic, (context sensitive)-graph automatic implies a context-sensitive word problem and conversely groups with context sensitive word problem are (context sensitive)-automatic. Finally an obstruction to (context sensitive)-graph automatic implying polynomial time word problem is given.

This is joint work with Jennifer Taback, Bowdoin College.