Saturday, May 27, 2017

Best paper awards at ICALP 2017

The following papers will receive the best paper awards at ICALP 2017 (source:

  • Best Track A Paper: A. Björklund, P. Kaski and I. Koutis.  Directed Hamiltonicity and Out-Branchings via Generalized Laplacians. 
  • Best Track A Student Paper: E. Lee. Improved Hardness for Cut, Interdiction, and Firefighter Problems. 
  • Best Track B Paper: M. Benedikt, P. Bourhis and M. Vanden Boom. Characterizing Definability in Decidable Fixpoint Logics. 
  • Best Track B Student Paper: F. Reiter. Asynchronous Distributed Automata: A Characterization of the Modal Mu-Fragment.
  • Best Track C Paper: E. I. Ásgeirsson, M. M. Halldorsson and T. Tonoyan. Universal Framework for Wireless Scheduling Problems.
Congratulations to all the award recipients!

It's been another good year for Nordic TCS (best papers at tracks A and C). Of course, we at ICE-TCS are particularly pleased for the Track C best paper award to our ICE-TCS colleagues Eyjólfur Ingi Ásgeirsson, Magnús Már Halldórsson and Tigran Tonoyan. Way to go!

Friday, May 05, 2017

2017 Alonzo Church Award announcement

Gordon Plotkin has kindly shared the 2017 Alonzo Church Award announcement with me. I am happy to post it here and hope that readers of this blog will be enticed to learn about this truly fundamental contribution to theoretical computer science.

The 2017 Alonzo Church Award for Outstanding Contributions to Logic and Computation is given jointly to Samson Abramsky, Radha Jagadeesan, Pasquale Malacaria, Martin Hyland, Luke Ong, and Hanno Nickau for providing a fully-abstract semantics for higher-order computation through the introduction of game models, thereby fundamentally revolutionising the field of programming language semantics, and for the applied impact of these models. Their contributions appeared in three papers:
  • S. Abramsky, R. Jagadeesan, and P. Malacaria. Full Abstraction for PCF. Information and Computation, Vol. 163, No. 2, pp. 409-470, 2000. 
  • J.M.E. Hyland and C.-H.L. Ong. On Full Abstraction for PCF: I, II, and III. Information and Computation, Vol. 163, No. 2, pp. 285-408, 2000. 
  • H. Nickau. Hereditarily sequential functionals. Proc. Symp. Logical Foundations of Computer Science: Logic at St. Petersburg (eds. A. Nerode and Yu.V. Matiyasevich), Lecture Notes in Computer Science, Vol. 813, pp. 253-264. Springer-Verlag, 1994. 
Description of the Contribution 

These papers made two fundamental contributions to our understanding of programming languages and logic. First, they provided signi ficant insight into the longstanding and fundamental "full abstraction problem" for the paradigmatic higher-order language PCF by giving a compositional semantic account of sequentiality, via an elegant cartesian-closed category of games and strategies. In the mid-1970s Milner posed the full-abstraction problem for PCF and Plotkin showed the difficulty of the problem, which essentially lies in the fact that the standard Scott-Strachey model permits non-sequential functions, although PCF itself is sequential.

The papers constructed models for PCF from games, leading to the first fully abstract models of PCF whose construction made no reference to the syntax of PCF. The elements of the models are strategies for certain kinds of interactive dialogues between two players (or between system and environment). These dialogue games are required to follow certain conventions concerning when questions are posed or answered; these conventions reflect constraints on the information available to the players of the game. The papers give new insight into the fundamental work in higher-type recursion theory of such logicians as Kleene, Gandy, Normann, and Hyland.

Second, and perhaps more importantly, game semantics has provided a new framework for the semantics of programming languages. Games can be used as a flexible and modular modelling tool, as a wide variety of programming language features can be understood as corresponding to different restrictions placed on allowed strategies. Thus there are fully abstract games models for call-by-value and call-by name languages; for languages with state, with control, with references, with exceptions, with nondeterminism, and with probability; and for concurrent and mobile process languages. In this way, game semantics has changed the landscape of programming language semantics by giving a unified view of the denotational universes of many different languages. This is a remarkable achievement that was not previously thought to be within reach.

Techniques developed in game semantics have found their way into a wide variety of applications. For example, they have provided tools for the verification of a range of computational systems, such as reactive systems of timed and hybrid automata, higher-order and mobile processes, and model-checking higher-order programs. There has also been significant influence on other areas, for example, static program analysis, type systems, resource-sensitive compilation, and compiler certification. All of these developments can be traced from the initial work of Abramsky, Jagadeesan and Malacaria, of Hyland and Ong, and of Nickau.

The 2017 award will be presented at the 26th Computer Science Logic (CSL) Conference, the annual meeting of the European Association for Computer Science Logic. This will be held August 20th{24th, 2017, at Stockholm University, Sweden.

The Alonzo Church Award for Outstanding Contributions to Logic and Computation was established in 2015 by the ACM Special Interest Group for Logic and Computation (SIGLOG), the European Association for Theoretical Computer Science (EATCS), the European Association for Computer Science Logic (EACSL), and the Kurt Godel Society (KGS). The award is for an outstanding contribution represented by a paper, or small group of papers, within the past 25 years; this is the second such award. The 2017 Award Committee consisted of Catuscia Palamidessi, Gordon Plotkin (chair), Natarajan Shankar, and Moshe Vardi.

Thursday, May 04, 2017

Call for participation: LearnAut at LICS 2017

The organizers of the Learning and Automata (LearnAut)  workshop, which is co-located with LICS 2017, have asked me to distribute the appended call for participation. 

The full list of workshops is available at
The early registration deadline is tomorrow
Please distribute this call to your students and research collaborators, as you see fit.



Learning and Automata (LearnAut) — LICS 2017 Workshop
June 19, Reykjavik (Iceland)
Early registration: May 5th

Grammatical Inference studies machine learning algorithms for classical recursive models of computations like automata and grammars. The expressive power of these models and the complexity of associated computational problems are a major research topic within theoretical computer science. This workshop aims at offering a favorable place for dialogue and at generating discussions between researchers from these two communities.

The following papers have been accepted for oral presentation:

  • Enes Avcu, Chihiro Shibata and Jeffrey Heinz: Subregular Complexity and Deep Learning
  • Alexander Clark: Strong learning of Probabilistic Context-Free Grammars from Strings
  • Nathanaël Fijalkow: Bisimulation on Distributions for Markov Decision Processes
  • Oded Maler and Irini-Eleftheria Mens: On Learning Symbolic Automata over Boolean Alphabets
  • Ariadna Quattoni, Xavier Carreras and Matthias Gallé. Scalable Spectral Learning of Automata through Maximum Matching
  • Rick Smetsers: Grammatical Inference as a Satisfiability Modulo Theories Problem

In addition, the papers accepted for poster presentation are:

  • Giovanni Bacci, Giorgio Bacci, Kim Guldstrand Larsen and Radu Mardare: On the Metric-based Approximate Minimization of Markov Chains
  • Simone Barlocco and Clemens Kupke: Automata Learning: A Modal Logic Perspective
  • Michael Bukatin and Jon Anthony: Dataflow Matrix Machines as a Model of Computations with Linear Streams
  • Kaizaburo Chubachi, Diptarama, Ryo Yoshinaka and Ayumi Shinohara: Query Learning of Regular Languages over Large Ordered Alphabets
  • Joshua Moerman: Learning Product Automata
  • Tianyu Li, Guillaume Rabusseau and Doina Precup: Neural Network Based Nonlinear Weighted Finite Automata
  • Alexis Linard, Rick Smetsers, Frits Vaandrager, Umar Waqas, Joost van Pinxten and Sicco Verwer: Learning Pairwise Disjoint Simple Languages from Positive Examples
  • Xiaoran Liu, Qin Lin, Sicco Verwer and Dmitri Jarnikov: Anomaly Detection in a Digital Video Broadcasting System Using Timed Automata
  • Guillaume Rabusseau and Joelle Pineau: Multitask Spectral Learning of Weighted Automata
  • Michal Soucha and Kirill Bogdanov: Efficient Active Learning with Extra States

The following top researchers will be invited speakers at LearnAut:
  • Kim G. Larsen (Aalborg University)
  • Mehryar Mohri (New York University & Google Research)
  • Alexandra Silva (University College London)

If you have not registered yet to the workshop, and if you are interested by its program, we strongly recommend you to do it as soon as possible ( The early registration deadline is on May 5th.

Pressures on accommodation possibilities are high, the sooner you book one the better it is (a lot of hotels are unfortunately already full).

Looking forward to seeing you at Reykjavik!

Friday, April 14, 2017

Public service announcement for LICS (workshop) participants

This is a public service announcement. If you plan to attend a LICS 2017 workshop and/or the main conference, and you have not booked your flight and accommodation yet, I strongly suggest that you do so ASAP. Iceland is a very hot holiday destination these days and it becomes fully booked soon, especially during the summer months. We already have about 160 registered participants for the conference and accommodation is disappearing at a rate of knots.

Friday, April 07, 2017

Ten PhD positions in CS at the Gran Sasso Science Institute

The Gran Sasso Science Institute (GSSI -, a recently established international PhD school and a Centre for advanced studies in L'Aquila (ITALY), offers 10 PhD positions in Computer Science (CS).

The PhD program in CS is mainly concerned with heterogeneous distributed systems and their interactions. Different perspectives are offered to provide students with the necessary tools for the design, the implementation, the management and the use of distributed systems. The main research areas of interest are:
- Efficient algorithms for communication networks and social networks;
- Formal methods for systems correctness and analysis;
- Software engineering for efficient and resilient applications.

Apart from pursuing their own research studies, the successful candidates will have the opportunity to cooperate with members of the research group and of the Scientific Board, as well as with the frequent guests of the Institute. Detailed information about the CS research group and about the activities for the PhD program in CS can be found at

The fellowships are awarded for three years and their yearly amount is € 16.159,91 gross. Moreover all PhD students:
- will have free accommodation at the GSSI facilities and luncheon vouchers;
- will have tuition fees waived;
- will be covered by insurance against accident and/or injury.

The application must be submitted through the online form available at and must be accompanied by the curriculum vitae of the applicant, and by a letter of motivation describing expertise and general research interests together with future plans and reasons for having chosen GSSI for PhD studies.

The deadline for application is: 31st May 2017 at 18.00 (Italian time).

Tuesday, April 04, 2017

18 postdoctoral positions at the Gran Sasso Science Institute

The Gran Sasso Science Institute offers 18 postdoctoral positions for research activity in Physics, Mathematics, Computer Science and Social Sciences.
Applicants must hold a PhD degree or an equivalent qualification. 

The research grants are awarded for two years and their yearly amount is € 36.000,00 gross. 

The application must be submitted through the online form available at by May 15, 2017 at 6 p.m. (Italian time zone).

For more information, please consult the Call for Applications at or write an email to

A description of research in computer science at GSSI is available here

Feel free to share this announcement as you see fit.

Saturday, April 01, 2017

The faculty is the university: The case of IMT Lucca

The physicist Isidor Isaac Rabi famously told President Eisenhower that "the faculty is the university." This is a quote I like to use when discussing with university administrators and I was reminded of it these days while reading opinions aired by several Italian academics on IMT Lucca, an Italian centre of advanced study and an international PhD school.

IMHO, a recent case of possible plagiarism involving an IMT graduate hasn't been handled well at all by the top management of that institution. However, to my mind, this event should not be used to debase the excellent work that our colleagues have done and are doing at that institute, which attracts to Italy and trains a good number of high-quality PhD students from abroad, and conducts cutting-edge research in its areas of interest. In fact, I do believe that schools of advanced study such as IMT can play an important role in the academic environment in Italy by attracting talent from abroad and nurturing Italian young researchers within an international research environment. IMHO, the variety those schools add to higher education in my native country is beneficial.

I would definitely encourage my (former) students to take up a PhD or a postdoctoral position within the SysMA group, to work with Rocco De Nicola, Mirco Tribastone and the young researchers in that group, five of whom are from outside Italy. I would also point people interested in control and dynamical systems to the DYSCO group, led by Alberto Bemporad.

These are just two examples from areas that are close to my own research interests. However, the quality of the faculty and of the postdocs and students at IMT is consistently high. I have had the pleasure of giving lectures on basic research skills to IMT students of a varied background, including students in cultural heritage, and thoroughly enjoyed interacting with them.

Summing up, my message to the colleagues who are currently forming an opinion on IMT Lucca based on the actions of its management is simple: "The faculty is the university." Look carefully at the (IMHO, excellent) work done by our colleagues working at that institute and form an opinion based on it, not on mediatic noise.