En stor ære

Mens jeg er i Malta, har jeg fået at vide, at jeg er blandt modtagerne af den såkaldte Test of Time Award, som uddeles ved konferencen CONCUR2020 i Wien til august. Prisen gives til artikler fra CONCUR-konferenceserien (en vigtig konference inden for teoretisk datalogi), der har rummet vigtige videnskabelige bidrag og har vist sig at “holde længe” (eller hvordan man bedst oversætter det engelske begreb “stand the test of time”).

Det er en virkelig stor ære for mig. Artiklen, Bisimulation Equivalence is Decidable for all Context-Free Processes, blev publiceret i 1992. Den er resultatet af et samarbejde med Søren Christensen og Colin Stirling, der var vejleder for både Søren og mig, da vi begge var PhD-studerende i Edinburgh.

Komiteens officielle begrundelse, som kan læses på CONCUR2020s hjemmeside, er denne:

The paper “Bisimulation Equivalence is Decidable for all Context-Free Processes”, published by Søren Christensen, Hans Hüttel and Colin Stirling at CONCUR 1992, receives one award for extending and simplifying the seminal result by Baeten, Bergstra and Klop, who proved the decidability of bisimilarity over normed context-free processes. The CONCUR’92 paper has paved the way to further decidability and complexity results for a variety of classes of infinite-state processes. This includes the 2-EXPTIME algorithm for bisimilarity over BPA presented by Burkart, Caucal and Steffen in a paper published at MFCS 1995, and the work by Senizergues in papers at FOCS 1998 and in the SIAM Journal on Computing in 2005, presenting decidability results for all “equational graphs” with finite out-degree.

Artiklens store resultat er et bevis for et åbent problem om afgørbarhed, jeg jagtede et svar på i mit PhD-arbejde, men ikke nåede at finde, inden min afhandling skulle afleveres. Men året efter, og ikke mindst takket være en vigtig indsigt fra Søren i form af et lemma om endelig karakterisation af vidner for ækvivalens, lykkedes det. Resultatene i vores artikel kom med i Sørens gode og velskrevne afhandling.

Han og jeg delte i et års tid lejlighed, men efter tiden i Edinburgh mistede vi desværre kontakten. Søren fik arbejde i en virksomhed, og jeg blev som bekendt universitetslærer. Nu har vi fået kontakt igen som resultat af denne hædersbevisning.

Da vi skrev artiklen, var Søren og jeg 28 år gamle. Nu er vi 56; der er gået et halvt liv. Lige før jul fik jeg at vide af Julian Bradfield, der også var en af Colins gamle PhD-studerende og siden blev i Edinburgh, at Colin nu går på pension. Forhåbentlig ser jeg dem begge igen i Wien ved prisoverrækkelsen – det ville glæde mig rigtig meget.