Word problems of free inverse monoids as languages.

Room FC1.004, DMat-FCUP
Friday, 10 February, 2017 - 14:30

Let FIM(X) be the free inverse monoid on a finite set X. The word problem of FIM(X) is easily seen to be recognisable in linear space (e.g. using Munn trees), and this has been improved to log space (Lohrey and Ondrusch 2007).

In this talk I will consider the complexity of the word problem of FIM(X) from a language theory perspective.  It is context-sensitive (equivalent to linear-space), but not context-free.  There is a rich world of interesting language classes in between the context-free and context-sensitive, and I will discuss where the word problem of FIM(X) fits within that world.  This is work in progress.

 

Speaker: 

Tara Brough

Institution: 

Universidade de Lisboa
Error | CMUP

Error

The website encountered an unexpected error. Please try again later.