Effective Eilenberg Machines

In this talk I revisit the idea of Eilenberg (from the book Automata, Languages and machines Vol.A 1974) to use automata labelled with relations as a general computational model. The model is now called Eilenberg machines. Originally it was presented in an abstract mathematical way. We make the model more precise to make it effective and give design choices for simulation using modern programming languages. In contrast with Turing machines, it is interesting to mention that Eilenberg machines may help to solve realistic problems, like the Sanskrit sandhi inversion problem for sentence segmentation as shown by Gérard Huet. We will also discuss how the simulation can be implemented in a clean way and proved correct using a software of modern formal mathematics. We will also review the state of the art of compilation of non-deterministic automata from regular expressions since the latter shall be used as a language for describing the control component of Eilenberg machines.