After almost forty years, a well-known theorem in algebra about 'Eilenberg-type correspondences' is finally fully understood. Although it has been broadly studied in the literature since Eilenberg showed his variety theorem in 1976, the defining properties and origin were not yet known until now. Julian Salamanca, PhD student at CWI in Amsterdam, made a unified theory that explained their real nature. He defends his thesis 'Coequations and Eilenberg-type correspondences' on 24 April 2018 at Radboud University in Nijmegen. The results are of interest to theoretical computer scientists, and in the future also for software engineers.
Salamanca says: "Formal languages are, in general, a way of describing software design in a mathematical way. They are often used to make software better and safer. In my PhD thesis, I studied these formal languages, and especially the theory of Eilenberg-type correspondences, which relate algebra and special formal languages that are called 'varieties of languages'. Although these varieties of languages are equations that satisfy the algebras, I discovered that they are - surprisingly - disguised as sets of expressions instead of equations. To obtain a general and simpler proof of the theorem, I used mathematical techniques from category theory and the recently developed theory of systems called coalgebra. In order to show the generality of the theorem, I derived 64 correspondences, of which 44 are new in the literature”.
The project was carried out in the Formal Methods research group at CWI under the supervision of Jan Rutten (CWI and RU) and Marcello Bonsangue (UL and CWI), with funding from NWO. Julian Salamanca was born in Bogota (Colombia) and got his MSc in mathematics at Universidad de los Andes. He started a PhD in mathematics at the University of Manitoba in Canada. When his supervisor Jiri Sichler sadly passed away, he moved to Amsterdam to start and finish his PhD project at CWI. Since 2017, he has been a scientific assistant at the University of Warsaw (Poland).
Julian Salamanca (in the middle) right after his PhD defence, with his supervisors. On the left Jan Rutten, on the right Marcello Bonsangue. (Own picture.)
More information
The thesis of Julian Salamanca: https://ir.cwi.nl/pub/27604/
CWI's Formal Methods group: https://www.cwi.nl/research/groups/formal-methods
Contact: salamanc (at) cwi.nl or juliansalamancat (at) yahoo.com
Information at the IPA website: http://www.win.tue.nl/ipa/?event=coequations-and-eilenberg-type-correspondences
