Where academic tradition
meets the exciting future

Guest lecture by Charles Grellois

On Thursday 13.11. Charles Grellois will give a guest lecture in Publicum, room 150, starting at 15:00.

Title: On the Coinductive Nature of Centralizers

The centralizer of a language L is defined as the largest solution C(L) to the language equation XL = LX. In other terms, any word u.v obtained as a concatenation of a word u of L and of a word v of C(L) should admit a factorization starting by a word of C(L) and ending with a word of L. We can understand this as a rewriting process on the words of C(L).

Kunc designed in 2006 a regular language L in which this rewriting process is such that it simulates the transitions of a Minsky machine. However, he could deduce from this that C(L) is not recursively enumerable...

We will sketch a variant of his proof using Turing machines, and introduce the key concept of coinduction, which solves the mystery of Kunc's result: centralizers' behaviour is dual to the one of machines.


Host: Aleksi Saarela