More or less than Dehn

Sarah Rees (Newcastle)

Wednesday 16th April, 2008 16:00-17:00 214

Abstract

I shall discuss the word problem for groups, introduced a century ago by Dehn, annd solved by him for surface groups. In the late 1980's Muller and Schupp proved that the word problem could be solved on a pushdown automaton pecisely when the group is virtually free. In that case Dehn's algorithm can be run on a pushdown automaton. The proof is based on the realisation that the underlying context-free grammar puts a restriction on the geometry of the group. I shall report on joint work with Holt and Shapiro, which examines the grammar associated with word problems solvable using a generalisation of the word problem developed by Goodman and Shapiro. We extend work of Goodman and Shapiro to find a host of examples with context-sensitive but not growing context-sensitive word problem, answering questions of Kambites and Otto, who found the first example in that category.

Add to your calendar

Download event information as iCalendar file (only this event)