CARMA Colloquium

4:00 pm

Tuesday, 4th Apr 2017

V205, Mathematics Building


Dr Michal Ferov

(CARMA, The University of Newcastle)

Groups, machines, algae and trees

In a way, mathematics can be seen as a language game, where we use symbols, together with some rewriting rules, to represent objects we are interested in and then ask what can be said about the sequences of symbols (languages) that capture certain phenomena. For example, given a group G with generators a and b, can we recognise (using a computer) the sequences of generators that correspond to non-trivial elements of G? If yes, how strong computer do we need, i.e. how complicated is the language we are studying?

There is a natural duality between various types of computational models and classes of languages that can be recognised by them. Until recently most problems/languages in group theory were classified within the Chomsky hierarchy, but there are more computational models to consider. In the talk I will briefly introduce L-systems, a family of classes of languages originally developed to model growth of algae, and show that the co-word problem in Grigorchuk's group, a group of particularly nice transformations of infinite binary tree, can be seen as a language corresponding to a fairly simple L-system.