CWI-onderzoeker Joost Winter promoveerde op 1 juli 2014 met een proefschrift waarin connecties tussen de coalgebra en de automatenthorie centraal staan. Coalgebra is een abstract raamwerk voor beschrijvingen en formele redenaties van systemen die zich in verschillende toestanden kunnen bevinden. Het kan onder andere gebruikt worden om te bewijzen dat systemen aan bepaalde eisen voldoen, zoals de correctheid van een complex softwaresysteem.
In zijn proefschrift past Winter principes uit de coalgebra toe in de automatentheorie, een theoretisch raamwerk om de werking van automaten te beschrijven. Winter beschrijft bekende klassen uit de automatentheorie, zoals de reguliere en de contextvrije talen (en generalisaties hiervan) beschreven in de vorm van (discrete) differentiaalvergelijkingen. Hierbij wordt de connectie tussen de klassieke automatentheorie, ontwikkeld vanaf de jaren '50 en '60, en de moderne coalgebraïsche benadering, verder opgehelderd.
Het Centrum Wiskunde & Informatica (CWI) geldt als de bakermat van de universele coalgebra. In een gezaghebbende paper uit 2000, die inmiddels meer dan 1000 keer is geciteerd, introduceert prof. dr. Jan Rutten dit onderwerp, waar inmiddels verschillende groepen wereldwijd aan werken.
Afbeelding: Een Turingmachine is een voorbeeld van een automaat dat te beschrijven is met automatentheorie. Een Turingmachine is een model voor berekeningen ontwikkeld door Alan Turing in 1937 en stond aan de basis van de moderne computer. De afbeelding toont een Turingmachine van LEGO, gebouwd door CWI-onderzoekers in 2012. www.legoturingmachine.org
