Job Announcement: Dean of the School of Computer Science at Reykjavík University

The School of Computer Science at Reykjavík University, my own stamping ground, is seeking a new dean. Our present dean, Ari K. Jónsson, will take over the rectorship of the university on January 23, 2010, and we are looking for excellent candidates to take over the deanship of the school. (The dean has direct responsibility for academic, administrative and fiscal operations of the School of Computer Science. The dean is part of the executive committee of the university and reports directly to the rector.)


The School of Computer Science hosts several active research groups and its main research areas are artificial intelligence, combinatorics, databases, human-computer interaction, natural language processing, software engineering, theoretical computer science and virtual environments.
 

The job announcement is here. Is any of you out there interested in applying for the job?

A Question on the Structure of Fields, Centres and Committees

Can anyone briefly explain to me, or point me to on-line information about, the raison d'être and operating characteristics of structures like the fields and centres at Cornell and MIT, or the interdisciplinary committees found at the University of Chicago?

I am asking wearing my hat of the chairman of the research council of my university, where we are mulling about the possibility of having similar structures. Thanks in advance for any information you might be able to provide!

Tony Hoare on Industrial vs. Pure Research

I have just read a very cogent retrospective piece that Tony Hoare has written for the October 2009 issue of CACM to mark the 40th anniversary of the publication of his seminal paper An axiomatic basis for computer programming. (This is the first article he wrote as an academic. Not a bad way to start, is it?) It is a read that I thoroughly recommend and that I'll make available to the students who are now taking my course on the semantics of programming languages. I am posting an excerpt from that viewpoint article on industrial vs. pure research in computer science since it may be of interest to readers of this blog. I pass the word to Tony.

"Pure academic research and applied industrial research are complementary, and should be pursued concurrently and in collaboration. The goal of industrial research is (and should always be) to pluck the 'low-hanging fruit'; that is, to solve the easiest parts of the most prevalent problems, in the particular circumstances of here and now. But the goal of the pure research scientist is exactly the opposite: it is to construct the most general theories, covering the widest possible range of phenomena, and to seek certainty of knowledge that will endure for future generations. It is to avoid the compromises so essential to engineering, and to seek ideals like accuracy of measurement, purity of materials, and correctness of programs, far beyond the current perceived needs of industry or popularity in the market-place. For this reason, it is only scientific research that can prepare mankind for the unknown unknowns of the forever uncertain future.

So I believe there is now a better scope than ever for pure research in computer science. The research must be motivated by curiosity about the fundamental principles of computer programming, and the desire to answer the basic questions common to all branches of science: what does this program do; how does it work; why does it work; and what is the evidence for believing the answers to all these questions? We know in principle how to answer them. It is the specifications that describe what a program does; it is assertions and other internal interface contracts between component modules that explain how it works; it is programming language semantics that explains why it works; and it is mathematical and logical proof, nowadays constructed and checked by computer, that ensures mutual consistency of specifications, interfaces, programs, and their implementations. There are grounds for hope that progress in basic research will be much faster than in the early days. I have already described the vastly broader theories that have been proposed to understand the concepts of modern programming. I have welcomed the enormous increase in the power of automated tools for proof. The remaining opportunity and obligation for the scientist is to conduct convincing experiments, to check whether the tools, and the theories on which they are based, are adequate to cover the vast range of programs, design patterns, languages, and applications of today's computers. Such experiments will often be the rational reengineering of existing realistic applications. Experience gained in the experiments is expected to lead to revisions and improvements in the tools, and in the theories on which the tools were based. Scientific rivalry between experimenters and between tool builders can thereby lead to an exponential growth in the capabilities of the tools and their fitness to purpose. The knowledge and understanding gained in worldwide long-term research will guide the evolution of sophisticated design automation tools for software, to match the design automation tools routinely available to engineers of other disciplines."

Amir Pnueli Dies

I just learned via a posting on the TYPES mailing list the sad news that Amir Pnueli, one of the inspirational and leading figures in several areas related to the formal specification and verification of computing systems, passed away yesterday at age 68. An email message circulated yesterday by his family states that "Amir has suffered a serious brain hemorrhage which he could not recover from. He passed away today [2 November] at noon."

In 1996, Pnueli received the Turing Award for seminal work introducing temporal logic into computing science and for outstanding contributions to program and systems verification.

His scientific legacy will be felt for many years to come.

Benchmarking Metrics: What and Why?

In his post entitled "Top 10 theory schools?", Jonathan Katz gives a list of what he considers to be the top 10 theory departments in the US. (Read the post and the comments for an update on the discussion.) One of the comments reads as follows:

I would agree about:


MIT (Silvio, Shafi, Ron, Michel, …)
Cornell (Rafael, Eva, Jon, Bobby,…)
Berkeley (Luca, Christos, Umesh,…)
CMU (Venkat, Manuel, Avrim, Ryan,…)
Princeton (Boaz, Sanjeev, Moses, Bernard,..)

The others are a bit flakier:

GA Tech (Santosh, Chris, Vijay, Sasha, …)
UT Austin (Adam, David, Brent)
UCSD (Mihir, 1/4 Russell, Daniele, maybe Hovav)
U Washington (Anna, Paul, Anup)

I would say at least he following schools are VERY comparable to above:

Stamford (Dan, Serge, Tim, Amin,…)
NYU (Subhash, Assaf, Yevgeniy, Richard, …)
Harvard (Salil, Michael(s), Leslie)
Columbia (Mihalis, Rocco, Tal)

I would say there are top 5, and then top 10 following them.

So this commentator measures the quality of a theory group using the perceived research quality of the very best researchers at a given institution. Another possible metric would be the size of the group of active researchers with high international visibility. Yet others could be the number of peer-reviewed publications in top-class journals and conferences, or the average such number per staff member.

What criteria are most useful and why (bearing in mind that, at the end of the day, we are always making subjective judgements)? I am interested in this topic since the School of Computer Science I am working at is presently undertaking a benchmarking exercise. The aim of the exercise is to find three to four departments in the Nordic countries with which we aim at comparing ourselves in the very short term, within five years and within 10-15 years. One of the interesting aspects of this exercise is that our school is substantially smaller than most of the departments elsewhere. So, what do you think would be good metrics for the benchmarking exercise? Standing of the top scientists within the school? Average number of peer-reviewed publications and citations? Or what?

EATCS Award 2010: Call for Nominations

The Call for Nominations for the EATCS Award 2010 has been published (see this pdf). Nominations and supporting data should be sent to the chairman of the EATCS Awards Committee, Emo Welzl. The next award is to be presented during ICALP'2010 in Bordeaux. The deadline for nominations is: December 15, 2009. So get your act together quickly and nominate one of the many "obvious suspects" for the award! 

Note that nominations are now kept alive for three years. Since I sent in an unsuccessful nomination last year, I don't need to do anything this time around and will just be a very interested observer :-)


I wish the award committee the best of luck with their work.

Five Years of Logical Methods in Computer Science

I have received this letter via email. I post it here since I strongly support journals like LMCS and I encourage my readers to submit good papers to it. Happy birthday LMCS! May your reputation grow with the years.



Dear Colleague:

We would like to bring the community up to date on the journal

   Logical Methods in Computer Science
   www.lmcs-online.org

We started this fully refereed, open access, free electronic journal in January 2005, intending to create a high-level platform for publications in all theoretical and practical areas in computer science involving logical methods, taken in a broad sense. We are now on Issue 3 of Volume 5 (there are four issues a year). So far, we have received more than 350 submissions of which we have published 162. In addition to individual submissions, our journal publishes special issues, e.g., of selected papers of high-level international conferences such as LICS, IJCAR, CAV, CSL, and RTA.

We are continuing actively to develop the journal. For example, we accept survey articles, and are developing `live' surveys, which can be continually updated as knowledge progresses. In another direction, we are considering allowing authors to provide additional material of an expository nature, such as slides and videos, to enable them to interest a wider spectrum of readers in their contribution.

The journal is an overlay of CoRR, the computer science repository of arXiv. There are no fees for authors nor for readers. Every paper is refereed by two or more referees, and high standards are applied. The editorial board consists of about sixty top specialists in all areas of logic in computer science.

The journal is covered by Mathematical Reviews, the ISI Web of Knowledge, and the DBLP Database.

We welcome your comments and suggestions, and we seek your contributions! For more information please consult our web pages:

     www.lmcs-online.org

Yours,

Editor-in-Chief:   Dana S. Scott <dana.scott@cs.cmu.edu>
Managing Editors:  Benjamin C. Pierce <bcpierce@cis.upenn.edu>
                  Gordon D. Plotkin <gdp@inf.ed.ac.uk>
                  Moshe Y. Vardi <vardi@cs.rice.edu>
Executive Editors: Jiri Adamek <adamek@iti.cs.tu-bs.de>
                  Stefan Milius  <s.milius@tu-bs.de>

IFIP 1.8 workshop on FORMAL METHODS FOR EMBEDDED SYSTEMS

I have received the following announcement from Bas Luttik. I am happy to post it here since the event will be of interest to concurrency theorists and people working on formal methods at large, many of whom will be in Eindhoven for FM week.  (Not to mention the fact that I am the outgoing chair of IFIP WG 1.8.)

==============================

========================================
                       CALL FOR PARTICIPATION
======================================================================
      IFIP 1.8 workshop on FORMAL METHODS FOR EMBEDDED SYSTEMS

               http://www.cse.unsw.edu.au/~rvg/FMES/

           Eindhoven, The Netherlands, November 5, 2009
======================================================================

This IFIP 1.8 workshop is organised as part of the Formal Methods Week,
which takes place in Eindhoven from November 2 until November 6, 2009.
The goal of the workshop is to summarise research from different areas
of formal methods targeted to embedded systems, and to promote the use
of formal methods in different applications and in the engineering
discipline for embedded systems.

PROGRAMME:
----------
 8:30  Registration and coffee
 8:50  Opening

 9:00  Bert van Beek -
         The Compositional Interchange Format: concepts, formal basis,
         and applications
 9:45  Holger Hermanns -
         Synchronous vs. Asynchronous Performance Models of Industrial
         Networks on Chip Designs

 10:30 Coffee break

 11:00 Catuscia Palamidessi -
         Synchronization in the pi-calculus
 11:45 Joost-Pieter Katoen -
         Analysis and Semantics of Extended AADL Models

 12:30 Lunch
 14:00 The End

For abstracts of the talks and further details about the workshop we
refer to http://www.cse.unsw.edu.au/~rvg/FMES/.

REGISTRATION
------------
The registration fee for the workshop is 45 euros and covers coffee/tea
and lunch. You also need to register for FMweek, which costs an
additional 35 euros (administration costs). Please register via the
FMweek website: http://www.win.tue.nl/fmweek

WORKSHOP ORGANISERS:
---------------------
Rob van Glabbeek (National ICT Australia)
Ursula Goltz (Technical University Braunschweig, Germany)
Bas Luttik (Technische Universiteit Eindhoven, The Netherlands)
Uwe Nestmann (Technical University Berlin, Germany)

Presburger Award

In an old post I announced that the EATCS was about to initiate a young researcher award. I am happy to see that the call for nominations for the first Presburger Award has now been advertised. See here for the details. The award is meant for scientists in TCS who are 35 or younger.

The award is named after Mojzesz Presburger who accomplished his ground-breaking work on decidability of the theory of addition (which today is called Presburger arithmetic) as a student in 1929.

The award includes an amount of 1000 € and an invitation to ICALP 2010 for a lecture.

I hope you will take the time to nominate young scientists for the award. Who would be your favourite candidates?

Treatment of Alan Turing was “appalling”

Arnar Birgisson, a former MSc student of mine who is now a PhD student at Chalmers, pointed out to me that last Thursday Gordon Brown issued a statement "recognising the “appalling” way he [Alan Turing] was treated for being gay." The piece of news may be found here.

It is understandable that Gordon Brown's statement focuses on Turing's work on breaking the German Enigma codes. However, I find it suprising that Turing's role in the development of computer science does not deserve any mention at all in the apology.

The statement ends as follows:

"So on behalf of the British government, and all those who live freely thanks to Alan’s work I am very proud to say: we’re sorry, you deserved so much better."

So long, and thanks for breaking the Enigma code, devising the Turing machine and the universal Turing machine, building some of the earliest programmable computers and all the rest.....

Nominations for the Gödel Prize 2010

The Call for Nominations for the 2010 Gödel Prize has been posted (see this pdf file). The 2010 Award Committee consists of Cynthia Dwork (Microsoft Research), Johan Håstad (KTH Stockholm), Jean-Pierre Jouannaud (INRIA and Tsinghua University; chair), Mogens Nielsen (University of Aarhus), Mike Paterson (University of Warwick) and Eli Upfal (Brown University). The deadline for nominations is 31 January, 2010.

I hope that the volume B community will nominate some excellent papers to give the very strong volume A papers a run for their money :-) What papers would you nominate? Post a comment with your favourite candidates. Perhaps you can garner some support for them, leading to an actual nomination for the prize.

I will try to post some suggestions myself when my list of things to do shrinks to an acceptable level. (Fat chance, alas.)

Tom Henzinger: The First President of IST Austria

Last Sunday night I came back to Iceland after a thoroughly enjoyable stay in Bologna for CONCUR 2009, SOS 2009 and the 16th EXPRESS workshop. This was a welcome opportunity to see many friends and colleagues, letting alone visiting my home country and a pretty city like Bologna.

I hope to find some time to report on the conference, not least to pay tribute to the great work done by the local organizers and their team (with special thanks to Christian, Cinzia, Ferdinanda, Jacopo and Jorge). With the start of the teaching period approaching fast and a pile of chores to catch up on, here I'll just limit myself to mentioning a piece of news that I learned at the conference while discussing with Krishnendu Chatterjee. From 1 September, Tom Henzinger is the first President of the Institute of Science and Technology (IST) Austria in Klosterbeuburg. You can read the official press release here.

The aim of the institute, which is richly funded by the Austrian government, is "to become a world-class research center offering, by 2016, an international, state-of-the-art environment for approx. 500 scientists and doctoral students." This commitment to excellence and to basic research is witnessed already by the first few hires IST has made and things can only improve under Tom's presidentship.

I wish Tom and IST the best of luck. It is great to see Austria invest on basic research with the creation of such an institute, which is already bringing to Europe top-class scientists like Herbert Edelsbrunner (the only computer scientist to have won the National Science Foundation's Alan T. Waterman Award) and researchers of exceptional promise like Krishnendu. Moreover, it is really awesome to see one of us be chosen as the leader of such an institute.

In Bologna I also guessed correctly that Tom is the scientist with the largest number of papers during the first 20 years of CONCUR (21 papers overall). I have every reason to believe that Tom Henzinger will continue to contribute to research in concurrency theory even as president of IST.

CAV Award 2009

Does any of my readers know who received the 2009 CAV Award? The conference ended on July 2, but the web page has not been updated with that information.

Post a comment if you know who the recipient of the award was.

A Look at my Crystal Ball

Let me make an attempt at predicting the winner(s) of the LICS Test-of-Time Award for 2009.

According to the rules of the award, the prize will go to a paper that was presented at LICS 1989 in lovely Asilomar. I was there as a second-year Ph.D. student and I presented a paper myself, but it was not award material.

The conference programme was really good and the award committee must have had a difficult choice. I do not know who will receive the award in mid-August, but let make a personal prediction: the award will be shared by the following two papers:

• Douglas J. Howe, Equality in lazy computation systems and
• Eugenio Moggi, Computational lambda-calculus and monads.

What papers do you think will receive the award? It will be interesting to look back at the predictions and see who was right.

Arthur Benjamin's Proposal for Changing Maths Education

ICE-TCS Theory Day 2009

Last Friday, ICE-TCS hosted its fifth annual theory day. This is an event we organize each year to advertise TCS to the local scientists and students, usually in connection with visits by guests of the centre from outside Iceland. (The list of previous guest speakers includes Thomas Erlebach, Wan Fokkink, Ryan Hayward, Jan Kratochvil, Kim G. Larsen, MohammadReza Mousavi, Mogens Nielsen and Moshe Vardi.)

The programme for this year's event is here. We had a keynote address delivered by Zoltan Esik, who presented work on regular words and linear orders, which may be found in, e.g., this paper of his. The session devoted to algorithms saw two excellent talks by the Halldórsson brothers on algorithms for detecting genomic copy variations and on scheduling wireless networks. (The latter talk was based on a paper that will be presented at ICALP 2009.) The scientific programme was brought to a close by two talks by PhD students, who are the future of TCS. Paul van Tilburg (Eindhoven University of Technology, NL) described some of the results he has achieved in his research work so far, which aims at connecting the time-honoured theory of automata with the theory of processes. Matteo Cimini (a PhD student I am supervising with Anna Ingolfsdottir) explained the Curry-Howard isomorphism, which is one of the pearls of TCS, to all of us in a clear way.

The event was followed by wine, pizza and a social gathering. The only happening that marred our celebration of TCS is a 6% salary cut that was announced by our rector during the session in the programme devoted to algorithms.

"May you live in interesting times" says an old Chinese curse. These are definitely interesting times here in Iceland, alas. However, despite the lack of resources, ICE-TCS will try to keep waving the flag of TCS on the island as far as it can. If you happen to be in Iceland and you wish to drop by and give a talk in our seminar series, drop us a line.

Concurrency column for the June 2009 issue of the BEATCS

Last month I submitted the concurrency column for the June 2009 issue of the BEATCS to the editor in chief. The piece is entitled Deriving labelled transition systems --- a structural approach and has been contributed by Julian Rathke and Pawel Sobocinski.

The paper reports on recent results obtained by the authors in their ongoing research effort whose aim is to contribute to the development of a general theory for the systematic derivation of a labelled transition semantics for a process calculus from a simpler, non-structural, description of the reduction semantics.

I think that we can expect to hear further developments on this line of work soon, but the authors already have a good story to tell and the paper they contributed to the BEATCS witnesses this fact.

Thanks to Julian and Pawel for their efforts in putting this good paper together!

Announcing LIPIcs, a new series of electronic conference proceedings in computer science

I just saw the appended message on the concurrency mailing list. I think that it will be of interest to readers of this blog. Much is afoot in the area of open-access conference and workshop proceedings and I guess that several events will consider publishing their proceedings in this series.

----

Dear colleagues,

Following an initiative of the conferences STACS (http://stacs-conf.org) and FSTTCS (http://www.fsttcs.org/), to opt for non-commercial, electronic proceedings, the German conference center Schloss Dagstuhl Leibniz Center for Informatics (LCI) has decided to establish a new series of conference proceedings called Leibniz International Proceedings in Informatics (LIPIcs,http://www.dagstuhl.de/en/publications/lipics/). The objective of this series is to publish the proceedings of high-quality conferences in all fields of computer science. An Editorial Board is being instituted to oversee the selection of the conferences to be included in this series.

Details about joining this serie and about the editorial process can be found on-line, http://www.dagstuhl.de/fileadmin/redaktion/DROPS/LIPIcs/lipics_announce.pdf. The main features are as follows:
The proceedings in the LIPIcs series will be published electronically and will be accessible freely and universally on the internet, keeping the copyrights with the authors, and under an open access license guaranteeing free dissemination. To face the cost of electronic publication, a one-time fee will be required from the conference organizers. This fee will be kept to a minimum, intended to cover the costs of LCI, thanks in particular to a sharing of the workload between LCI and the conference organizers.

The LCI and the LIPIcs Editorial Board wish to attract the best conferences in computer science, and they hope you can encourage steering and program committees to join it!

Pascal Weil
LaBRI - CNRS
351 cours de la Libération
33405 Talence Cedex - France

pascal.weil@labri.fr
http://www.labri.fr/~weil

EPTCS, a new open access proceedings series

I have received the following message from Rob van Glabbeek, which I am very happy to post on this blog. I encourage readers of this blog to spread the announcement at their own institutions and to post it on their blogs, if they have any. I like to think that this new series of open access proceedings will offer the TCS community a good service. Of course, only time will tell whether this will happen, but I feel that the time is ripe for such initiatives in the TCS community. Spread the news!

With this posting, we are launching

   Electronic Proceedings in Theoretic Computer Science (EPTCS)

a new international refereed open access venue for the rapid
electronic publication of the proceedings of workshops and
conferences, and of festschrifts, etc, in the general area of
theoretical computer science, broadly construed.

We do not charge authors or event organisers for electronic
publication in EPTCS in any way. If hard-copies of proceedings are
desired, event organisers have the choice of organising the printing
themselves or taking advantage of a standard contract we will make
with a printing house. Copyright on all papers is retained by the
author, and full-text electronic access to all papers is freely
available, without any need for registration or subscription.

Permanent archival of EPTCS publications is ensured by organising
EPTCS as an overlay of the Computing Research Repository (CoRR): see
arXiv.org. The content of EPTCS will be indexed by DBLP.

Only original papers will be considered for publication in EPTCS:
manuscripts are accepted for review by an EPTCS conference or workshop
with the understanding that the same work has not been published, nor
is presently submitted, elsewhere. However, full versions of extended
abstracts published in EPTCS, or substantial revisions, may later be
published elsewhere.

The submission and refereeing process is handled entirely by the
organisation of the conference, workshop or festschrift to which the
paper is submitted. Our editorial board carefully selects which
workshops and conferences can be trusted to select scientific papers
of quality only, and only those events will be granted a contract to
fill a volume of EPTCS.

Our editorial board consists of:

Luca Aceto  Rob van Glabbeek Gordon Plotkin  
Rajeev Alur  Lane A. Hemaspaandra Vladimiro Sassone 
Krzysztof R. Apt Matthew Hennessy Robert H. Sloan  
Lars Arge  Bartek Klin  Wolfgang Thomas  
Ran Canetti   Evangelos Kranakis Irek Ulidowski  
Luca Cardelli  Shay Kutten  Dorothea Wagner  
Rocco De Nicola  Nancy Lynch  Martin Wirsing  
Jose' Luiz Fiadeiro Aart Middeldorp  Moti Yung  
Wan Fokkink  Benjamin Pierce     

Further information can be found on our website:

     http://eptcs.org/.

In the hope this initiative will benefit the theoretical computer
science community,

Rob van Glabbeek
(Editor in Chief)

Accepted Papers for LICS 2009

The list of papers selected for presentation at LICS 2009 is out. At first sight, it wasn't a great year for concurrency theory, but the programme looks very interesting as usual. Some of the papers I intend to check out when I can get my hands on them, and the dust settles, are, e.g.:

• Taolue Chen, Tingting Han, Joost-Pieter Katoen and Alexandru Mereacre. Quantitative Model Checking of Continuous-Time Markov Chains Against Timed Automata Specifications
• Joachim Parrow, Magnus Johansson, Björn Victor and Jesper Bengtson. Psi-calculi: Mobile processes, nominal data, and logic
• Frank Pfenning and Robert Simmons. Substructural Operational Semantics as Ordered Logic Programming
• Sumit Nain and Moshe Vardi. Trace Semantics Is Fully Abstract
• Udi Boker and Orna Kupferman. Co-ing Büchi: Less Open, Much More Practical

Plenty to read! Congrats to Sumit and Taolue, with whom I have had the pleasure to co-author papers at some point in the past.