Tata Institute of Fundamental Research
Effective Eilenberg Machines
Colloquium
Speaker:
Benoit Razet
Tata Institute of Fundamental Research
School of Technology and Computer Science
Homi Bhabha Road
Date:
Wednesday, 17 Mar 2010 (all day)
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Benoit Razet Tata Institute of Fundamental Research School of Technology and Computer Science Homi Bhabha Road |
| Date: | Wednesday, 17 Mar 2010 (all day) |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.