27th Nordic Workshop on Programming Theory

The 27th Nordic Workshop on Programming Theory (NWPT 2015) was held at Reykjavik University in the period 21-23 October and was organized by AnnaIngolfsdottir and me in cooperation with our postdocs  Dario Della Monica, Ignacio Fabregas and Alvaro Garcia Perez. It finished on Friday, 23 October,  at around 17:30 after three packed days of scientific presentations.

The workshop had 57 registered participants (50 of which came from abroad, giving yet another indication of the powerful lure of Iceland as a destination for scientific events), and several talks were also attended by some local faculty members and students who were not officially registered for the workshop. All sessions had a good audience, including the very last one.

The workshop was graced by three excellent invited talks and the quality of the contributed presentations was consistently high. It was very pleasing to see many young researchers deliver clear, well prepared and well paced presentations. You can find all the abstracts for the contributed presentations and the slides for nearly all the talks here.

The invited talks were delivered by Rocco De Nicola (IMT Lucca, IT), Marta Kwiatkowska (University of Oxford, UK) and Jiri Srba; (Aalborg University, DK).

Rocco kicked off the workshop with a talk entitled Languages and Models for Collective Adaptive Systems (slides). Collective Adaptive Systems are heterogeneous collections of autonomous task-oriented systems that cooperate on common goals forming a collective system. Such systems consist of massive numbers of components that interact in complex ways amongst themselves and with other systems; they operate in open and non-deterministic environments, dynamically adapting to new requirements, technologies and environmental conditions. Developing such systems poses challenges to the developers such as the sheer number of components, the need to adapt to changing environments and requirements, the emergent behaviour resulting from complex interactions and the uncertainty both at design-time and at run-time. In his talk, Rocco presented the SCEL language developed by his research group for programming collective adaptive systems and its underlying theory.

Jiri delivered the Thursday invited talk on  Techniques and Tools for thefl Analysis of Timed Workflows (slides). According to Wikipedia, a work flow consists of an orchestrated and repeatable pattern of business activity enabled by the systematic organization of resources into processes that transform materials, provide services, or process information. Many such workflows have strong real-time requirements, and their modelling and analysis is a significant challenge.

In his talk, Jiri suggested a workflow model based on timed-arc Petri nets and introduced the foundational problems of soundness and strong (time-bounded) soundness. He addressed the decidability of these problems and showed, among other results, that soundness is decidable for monotonic workflow nets while reachability is undecidable. For general timed-arc workflow nets, soundness and strong soundness become undecidable, though one can design efficient verification algorithms for the practically interesting subclass of bounded nets. Finally, he demonstrated the usability of the theory by presenting case studies dealing with a Brake System Control Unit used in aircraft certification, the MPEG2 encoding algorithm, a blood transfusion workflow and a home automation system for a family house.

The implementation of the algorithms is freely available as a part of the model checker TAPAAL, which I encourage you to try. 

Last, but not least, Marta delivered  an invited  talk on Computing Reliably with Molecular Walkers (slides). DNA computing is emerging as a versatile technology that promises a vast range of applications, including biosensing, drug delivery and synthetic biology. DNA logic circuits can be achieved in solution using strand displacement reactions, or by decision-making molecular robots, so called 'walkers', that traverse tracks placed on DNA 'origami' tiles. (See, for instance, Luca Cardelli's work.) Similarly to conventional silicon technologies, ensuring fault-free DNA circuit designs is challenging, with the difficulty compounded by the inherent unreliability of the DNA technology and lack of scientific understanding. In her talk, Marta gave an accessible  overview of computational models that capture DNA walker computation and demonstrated the role of quantitative verification and synthesis in ensuring the reliability of such systems. Since stochasticity is an essential component of DNA computing, not surprisingly Marta and her collaborators use the tool PRISM, whose development has been led by Marta herself, in modelling and analysis of molecular programs.

Marta and her co-workers applied quantitative modelling, verification and synthesis to three DNA case studies:

1. DNA tranducer gate design (with Luca Cardelli),
2. DNA walker design (with AndrewTurberfield's lab) and
3. DNA origami dimer (also with AndrewTurberfield's lab).

All were continuous-time Markov chain models, and the first two were modelled analyzed successfully in PRISM. The third proved to be beyond the current capabilities of the tool. If you are interested, you will find papers on those case studies on Marta's publication page.

The workshop also had some local impact. In particular, several members of our association of female students in computer science met with Marta Kwiatkowska, Hanne Riis Nielson and other female participants to discuss about CS in an informal setting and learn from successful female role models, apart from those at their own institution. We thank these female colleagues for their mentoring role.

All in all, it seems to me that NWPT is excellent health and that many workshops, even with published proceedings, can only dream of having the type of support and environment that NWPT boasts.(The NWPT is an informal workshop without published proceedings, but there will be a special issue of a journal to which we will invite some selected contributions.)

The next edition of the workshop will be held in Aalborg. So the workshop will come back to Denmark, where it has not been held since 2009.