Appears in collection : Frontiers of reconnaissability / Frontières de la reconnaissabilité

The talk is based on a joint work with Kufleitner, Reinhardt, and Walter. The result was presented first at ICALP 2012 in Warwick. It shows that for each recognizable language L there exist some finite confluent and length-reducing semi-Thue system S such that L is a finite union of congruence classes with respect to S. This settled a long standing conjecture in formal language theory which dates back to a JACM publication by McNaughton, Narendran and Otto in 1988. Substantial steps towards the solution were done by Reinhardt and Therien concerning group languages and in 2011 in a joint work of the speaker with Kufleitner and Weil for aperiodic languages. The solution for the aperiodic languages and the general case became possible by proving in each of these cases a much stronger result, thereby "loading the induction".