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!