Friday, April 30, 2021

PolyConc: Online collaboration to improve on a result on the equational theory of CCS modulo bisimilarity

The aim of this post is to try and start an online collaboration to improve the solution to a problem in the equational logic of processes that I posed in a survey paper in 2003, namely

Can one obtain a finite axiomatisation of the parallel composition operator in bisimulation semantics by adding only one binary operator to the signature of (recursion, restriction, and relabelling free) CCS?

Valentina Castiglioni, Wan Fokkink, Anna Ingólfsdóttir, Bas Luttik and I published a partial, negative answer to the above question in a paper at CSL 2021. (See the arXiv version for details and for the historical context for the above question.) Our solution is based on three simplifying assumptions that are described in detail in Section 3 of the above-mentioned paper. We'd be very interested in hearing whether any member of the research community in process algebra, universal algebra and equational logic can relax or remove any of our simplifying assumptions. In particular, one can start with assumptions 3 and 2. 

We would also welcome any comments and suggestions on whether some version of that problem can be solved using existing results from equational logic and universal algebra. In particular, are there any general results guaranteeing that, under certain conditions, the reduct of a finitely based algebra is also finitely based? Or, conversely, that if some algebra is not finitely based, then so its expansion with a new operator?

To start with, add any contributions you might have as comments to this post. If ever we make substantial enough progress on the above question, anyone who has played a positive role in extending our results will be a co-author of the resulting paper. 

Let PolyConc begin!

Sunday, February 21, 2021

Article by Sergey Kitaev and Anthony Mendes in Jeff Remmel's memory

Sergey Kitaev just shared with me an article he wrote with Anthony Mendes in Jeff Remmel's memory. Jeff Remmel was a distinguished mathematician with a very successful career in both logic and combinatorics. 

The short biography at the start of the article paints a vivid picture of Jeff Remmel's  personality, and will be of interest and inspiration to many readers. His hiring as "an Assistant Professor in the Department of Mathematics at UC San Diego at age 25, without officially finishing his Ph.D. and without having published a single paper" was, in Jeff Remmel's own words, a "fluke that will never happen again."

I had the pleasure of making Jeff Remmel's acquaintance when he visited Sergey in Reykjavik and thoroughly enjoyed talking to him about a variety of subjects. He was truly a larger-than-life academic.

Monday, February 08, 2021

Whence do research collaborations (in TCS) arise?

About ten days ago, I gave a talk to my colleagues at the Department of Computer Science at Reykjavik University, introducing my personal (and admittedly very biased) view of the past, present and future of ICE-TCS

After my presenta­tion, a colleague asked me how she could engage mathematicians and theoretical computer scientists in joint research. I gave her an answer off the top of my head, but it was clear that she was unconvinc­ed and felt that I was avoid­ing answering her question. (For the record, I basically told her that she should knock on our door, discuss with us the problems she was interested in solving and hope that they are of interest to us. I feel that many research collaborations arise from serendipity and that there is no recipe that is guaranteed to work.) 

The thought that she felt that I might have dodged her question prompted me to look back at my own research collabo­rations and how they came about. The rest of this post is the result of that quick-and-dirty reflection. Let me state right away that my list isn't meant to be exhausti­ve and that I won't mention many of the collaborations in which I have been lucky to be involved and that I have played a crucial role in shaping my academic development. 

Reading papers. One of my long-term research collaborations arose from reading a paper written by a colleague. His paper prompted my companion and me to ask ourselves whether we could prove a similar result to the one our colleague had shown in a different setting. We succeeded and sent him our paper. Subsequently, we invited him to visit us in Aalborg. That visit marked the start of a collaboration and friendship that has lasted for over 20 years.

Approaching a colleague via email for help in solving a problem. At some point, my companion and I were thinking about a research problem that had frustrated us for a while. I remembered reading a number of papers by a colleague on related topics, so I wrote to him, describing the problem, our attempts at solving it and where we had hit a brick wall. I asked him whether he would be interested in working with us on solving it. He did and that was one of the lucky breaks I have had in my research career. Once more, that collaboration offer via email led to mutual visits, other joint papers and, IMHO even more importantly, a long-term friendship that extended beyond work.

Available funding and building on one's mistakes. One day in 2009, an email in my mailbox alerted me to the availability of substantial funding for research collabo­ration between universities in country X and those locat­ed in Norway, Iceland and Lichtenstein. This opportunity was enticing, as I had never visited country X, so I asked myself: "Is there anyone there we might conceivably work with?'' Mulling over that question, I recalled that a colleague from country X had spotted an imprecision in a paper I had coauthored. 

I wrote to him, we applied for that funding jointly and got it. That successful grant application provided the funds for many research visits involving several people in our research groups. Those visits resulted in joint papers, another successful grant application and a number of friendships.

Coffee breaks at conferences. I have at least two exhibits under this heading. The first belongs to a previous geologic­al era (1991). I was attend­ing a conference at CMU and asked a colleague what he was working on. He told me
about a problem he was tackling, which I knew was also on the radar of a fellow researcher and on which I had started working independently. Eventually, after some email exchanges, that chat over coffee turned into a three-way collaboration that, thanks to my coauthors, produced one of my best papers.

Fast forward to 2017 and I'm in Rome to deliver an invited talk at a small conference. During the coffee break follow­ing my presentation, I was approached by a young research­er, with whom I had a number of pleasant conversations during the conference. Some time later, she sent me a draft paper dealing with a topic related to the content of my invited talk. I invited her to visit our research group in Reykjavik and to join the team working on a research project for which we had funding at the time. Those coffee-break conversations led to a collaboration and friendship that I hope will last for a long time. Meeting that colleague has been another of my lucky breaks.

Reading groups. Last, but by no means least, let me mention that my first research collaboration that did not involve my thesis supervisors arose when I read Gordon Plotkin's famous "Pisa Notes (On Domain Theory)" with a fellow PhD student. Reading that work led to our first joint paper in 1991 and a companionship that has lasted to this day. I heard Orna Kupferman give the following, tongue-in-cheek advice to young researchers: "Write papers with your twin-sister!" Mine might be: "Write papers with your companion in life!" 

Let me conclude by saying that serendipity and an actual friendship that extends beyond the confines of scientific work were the key aspects in my most pleasant and enduring collaborations. I apologise to the colleagues from whom I have learnt much over the years (former students and postdocs, as well as others) who were the prime movers in research collaborations I did not mention in this post. 

 I guess that this note provides much more information than my colleague was intending to receive, but I thought I should put it out for the benefit of the young researchers at Reykjavik University and at the Gran Sasso Science Institute, and of any reader I might have. 

How did your research collaborations arise? If you have anything to add to what I wrote above, and I am sure you do, add your contributions as comments to this post.

Friday, February 05, 2021

Support research in the Foundations of Computing at the University of Leicester!

In an ideal world, university administrators would support the work of the top-class academics employed by their institution, especially if they attract students, have a high research standing within their communities and bring in substantial funding from competitive research funds. After all, to quote Isidor Isaac Rabi, "the faculty are the university" and the most valuable currency for an academic institution is reputation. 

Unfortunately, university administrations the world over repeatedly surprise me by making structural changes that affect some of their very best academics and actually reduce the reputation of their institutions in the eyes of the community at large.

The latest example comes from the University of Leicester, where, as stated here,

[the] University VC proposes to merge Informatics and Mathematics into a combined school focussed exclusively on AI, data science, computational modelling and "digitalisation". This includes the proposal to cease research in Foundations of Computer Science (FoCo) where research is "highly theoretical and not directly linked with applications", retaining staff only if the research they have published in the past (!) aligns well with the new desired focus on foundations of AI, computational modelling, data science and digitalisation. Staff have been given no opportunity to alter their research to fit with the proposed new direction. The plan is to make redundant (in the middle of a pandemic) all (up to 10) staff in foundations of computer science whose past research is deemed not to be a good enough fit with the new strategic priorities.

See also this statement by the University and College Union of the University of Leicester. 

I might be biased, but I find it inconceivable that one can think of building a world-class research programme in AI, data science and computational modelling without building on existing strengths in the Foundations of Computer Science and Mathematics. What my crystal ball tells me is that the strong Leicester academics who might be affected by the planned restructuring will find positions elsewhere and that the University of Leicester is shooting itself in the foot. Which high-profile academic would be enticed to join a university that has shown so little consideration for its existing areas of strength and where one's job might be in danger when the buzzwords du jour change, as they undoubtedly will? 

I encourage you to sign the petition in support of our Leicester colleagues. Kudos to Isobel Armstrong, FBA, for returning her honorary doctorate to the University of Leicester upon hearing of their plans!

Monday, February 01, 2021

Two PhD positions at the Department of Computer Science, Reykjavik University: Model-driven SE for blockchain and smart contracts

The Software and Emerging Technology Lab at the Department of Computer Science, Reykjavik University, is looking for two PhD candidates to work on an ongoing research project on the application of Model Driven Software Engineering principles, methodologies, technologies and abstractions to Blockchain and Smart Contracts. While both positions require strong software development skills and familiarity with the model-driven software engineering approach, the first position will focus on domain analysis and code generation, while the second position is concerned with contract safety and validity and requires knowledge in model verification and validation. The project is based in Iceland. It will be directed by Mohammad Hamdaqa in collaboration with Luca Aceto and Gísli Hjálmtýsson and in close collaboration with Polytechnique Montréal in Canada. The positions are fully funded and include full tuition waiver and a salary in accordance with the Icelandic Research Fund guidelines. Particularly the funding is covering full tuition as well as a stipend of 383,000 ISK per month before taxes for a minimum of three years. 
If you are interested to apply, please send the documents below to the following email addresses:
  • A copy of your CV and research interests
  • A copy of all your transcripts
  • A sample publication
  • A maximum of one page research statement of your plans for research in your PhD.
  • Your intended starting date / and if you need a visa
  • For more information about the position and the research topics, do not hesitate to send your enquiries to any of the project collaborators.
Luca Aceto (

Gísli Hjálmtýsson (

Informal inquiries about the project and the conditions of work are very welcome. We will start reviewing applications as soon as they arrive and will continue to accept applications until each position is filled. We strongly encourage interested applicants to send their applications as soon as possible and no later than 28 February 2021.

Friday, January 29, 2021

One PhD and one postdoc position at Reykjavik University

Mode(l)s of Verification and Monitorability

Department of Computer Science, Reykjavik University

One PhD and one postdoc position

We invite applications for a total of two positions: one PhD position and one postdoc position, at the Department of Computer Science of Reykjavik University.

The position is part of a research project funded by the Icelandic Research Fund, under the direction of Antonis Achilleos (Reykjavik University), Luca Aceto (Reykjavik University), and Anna Ingolfsdottir (Reykjavik University) in cooperation with Adrian Francalanza (University of Malta) and Karoliina Lehtinen (LIS, Aix-Marseille).

The project continues previous work in the theoretical foundations of runtime verification and its overarching goal is to better understand the properties and push the limits of monitorability in different settings. For more information on the project, please visit 

or contact Antonis Achilleos (email:

The successful candidates will benefit from, and contribute to, the
research environment at the Icelandic Centre of Excellence in
Theoretical Computer Science (ICE-TCS), with research groups on
concurrency, logic and semantics, algorithms, combinatorics. For
information about ICE-TCS and its activities, see .

Moreover, they will cooperate with Adrian Francalanza and Karoliina 
Lehtinen during the project work and will benefit from the interaction 
with their research groups at the University of Malta and LIS, Aix-Marseille.

*Qualification requirements*

Applicants for the postdoctoral position should have, or be about to
defend, a PhD degree in computer science or a closely related
field. Moreover, previous knowledge in logic, concurrency theory, or any 
of the project's related areas, and mathematical competence are desirable.

Applicants for the PhD fellowship should have, or be about to obtain, an 
MSc degree in Computer Science, or closely related fields. Some 
background in logic, concurrency theory, or some other of the project's 
related areas, and mathematical competence are desirable.


The PhD position provides a stipend of 383,000 ISK per month before 
taxes, and the salary for the postdoc position is 460,000 ISK per month 
before taxes.

*Start date and duration*

The PhD position is for three years, to start as soon as possible.

The postdoc position is for one year, to start in July or August 2021 (the start date is negotiable), and can be renewed for one more year, based on mutual agreement.

*Application details*

Interested applicants should send their CV, including a list of publications, in PDF to all the addresses below, together with a statement outlining their suitability for the project and the names of at least two referees.

Antonis Achilleos

Luca Aceto

Anna Ingolfsdottir

Adrian Francalanza

Karoliina Lehtinen

Informal inquiries about the project and the conditions of work are very welcome.

We will start reviewing applications as soon as they arrive and will continue to accept applications until each position is filled. We strongly encourage interested applicants to send their applications as soon as possible and no later than 20 February 2021.

Tuesday, November 17, 2020

Faculty positions at the Department of Computer Science, Reykjavik University

The Department of Computer Science at Reykjavik University is hiring and invites applications for faculty positions at any rank. 

We are looking for energetic, highly qualified academics with a proven international research record.  We particularly welcome applications from researchers who have a strong network of research collaborators, can strengthen internal collaborations within the department, and generally have potential to flourish in our setting. 

We have just posted three separate calls for applications.

  • If you are interested in applying for one of the faculty positions in the fields of Data Science, Machine Learning, Software Engineering, and Computer Security, please follow this link for more information on the positions and on how to apply. 
  • If you are interested in applying for the faculty position in Game Design and Development, see here for more information on the position and on how to apply.
  • We also have a call for faculty positions in any area of Computer Science. You can find further information on those positions here

Addendum dated 19 November 2020: Scientists coming to Iceland from abroad for work can apply for a tax relief for the first three years of their employment. If the application is successful, 25% of their salary is tax free.

Department of Computer Science at Reykjavik University

The Department of Computer Science at Reykjavik University has about 650 full-time-equivalent students and 22 faculty members. It provides an excellent working environment that encourages and supports independence in academic endeavors, and in which a motivated academic can have impact at all levels. The department offers undergraduate and graduate programs in computer science and software engineering, as well as a combined undergraduate program in discrete mathematics and computer science. The department is home to several research centers producing high-quality collaborative research in areas such as artificial intelligence, financial technology, language technology, software systems, and theoretical computer science, among others; for more information on those research centers, see

Reykjavík University 

On the Times Higher Education rankings for 2021, Reykjavík University is ranked in first place along with eight other universities for the average number of citations per faculty. Overall, RU is ranked among the 350 best universities world-wide, 59th of all universities established fewer than 50 years ago, and first among Icelandic universities. Reykjavík University has around 3.700 students and 250 faculty and employees in addition to numerous adjunct faculty in two schools: Technology and Social Sciences. We offer a welcoming and stimulating environment in which to work and live. The University is centrally located in Reykjavík, the capital city of Iceland. The role of Reykjavik University is to create and disseminate knowledge to enhance the competitiveness and quality of life for individuals and society, guided by good ethics, sustainability and responsibility. Education and research at RU are based on strong ties with industry and society. We emphasize interdisciplinary collaboration, international relations and entrepreneurship. 


Iceland is well known for breathtaking natural beauty, with volcanoes, hot springs, lava fields and glaciers offering a dramatic landscape. It consistently ranks as one of the best places in the world to live. It offers a high quality of life, is one of the safest places in the world, has high gender equality, and strong health-care and social-support systems. It is in fourth position in the 2020 UN World Happiness Report, which correlates with various life factors.