Friday, May 28, 2010

Extended Deadlines for SOS 2010

I am co-chairing SOS 2010, an affiliated workshop of CONCUR 2010, which will be held in Paris. You are still on time to submit a paper to that event! The new submission deadlines are as follows:
  • Submission of abstract: Friday 28th May 2010 Tuesday 1st June 2010 (strict)
  • Submission: Wednesday 2nd June 2010 Monday 7th June 2010 (strict)
Can you resist the lure of Paris in late August-early September?

Thursday, May 27, 2010

My Workplace

Here are some views of my workplace and its environment. The two photos above picture the entrance to my "professorial work area" :-) The one on the right depicts the entrance to my work area and its immediate environment, with the work places of Anna Ingólfsdóttir (left) and Magnús Halldórsson (right, behind the stand where we place some of our recent papers and books). This is the heart of our ICE-TCS enclave.

Can one work in such an environment? So far, the answer seems to be yes, but this is mainly because I am starting to believe one can work anywhere provided everyone in one's neighbourhood adheres to some basic ground rules.

Is the open-space environment conducive to academic work? This I am much less convinced about.

To conclude, here is what the open-space work environment looks like when I arrive at work in the morning. (The photo is taken from outside my cubicle.)

First Presburger Award to Mikolaj Bojanczyk

The Presburger Award Committee, consisting of S. Leonardi, A. Tarlecki, and W. Thomas (chair) has chosen Mikolaj Bojanczyk as the first recipient of the EATCS Presburger Award for young scientists.

The motivation from the award committee reads as follows:
Mikolaj Bojanczyk, 32 years old, has contributed numerous deep results to automata theory and to logic and algebra in computer science. Among them is the theorem stating that tree walking automata are strictly weaker than general tree automata, the definition of new decidable logics based on quantifiers for boundedness, and the development of a novel algebraic framework for the study of properties of unranked trees. His work thus led to the solution of long-standing open problems and introduced methods that open new directions in theoretical computer science (also relevant to neighbour disciplines such as data base theory). The committee recommends Mikolaj Bojanczyk as an exceptional young scientist who not only fully deserves the Presburger Award but is also an ideal first recipient. The committee also would like to mention that more than one excellent nomination was made, a fact which lets us hope that the Presburger Award will receive several nominations of truly exceptional level from all areas of theoretical computer science in the coming years.
Let me add that, in 2005, Mikolaj's doctoral thesis, entitled ”Decidable Properties of Tree Languages”, received the Ackermann award of the European Association of Computer Science Logic. In 2006, he was awarded the ”Witold Lipski prize for young Polish researchers in computer science”. In 2007, he received the Kuratowski award for young Polish mathematicians, awarded by the Polish Mathematical Society. In 2009, Mikolaj became one of the very few young computer scientists to obtain a European Research Council Starting Grant.

Congrats to Mikolaj for yet another well-deserved award. May his work go from strength to strength.

Saturday, May 15, 2010

Fifth International Summer School on Rewriting

The 5th International School on Rewriting will be held in the period  July 3-8, 2010, in Utrecht, The Netherlands. The programme includes both basic and advanced lectures. Perhaps some of your graduate students will be interested in attending the event.

Term rewriting is a core area in Theoretical Computer Science. It is powerful model of computation underlying much of declarative programming, which is heavily used in symbolic computation in logic and computer science. Applications can be found in theorem proving and protocol verification, but also in fields as diverse as mathematics, philosophy and biology.


Monday, May 10, 2010

School of Computer Science at RU on Twitter

The School of Computer Science at Reykjavik University, where I work, has made the step to advertise its events and news on Twitter. See here. Our aim is to make potential students and the community at large aware of what the school can offer.

Does your institution have a Twitter page too? Do you think that Twitter is a good channel for spreading news to potential CS students?

Thursday, May 06, 2010


After five years of operation, ICE-TCS (our little research centre in TCS) finally has a logo, which you see displayed above in its full glory. The logo design is courtesy of Emilka Bojańczyk. Do have a look at her graphic design work, which I like a lot. If you need logos, posters or any other kind of TCS- or Maths-related  design work, I strongly recommend Emilka.

Apart from being a professional graphic designer, Emilka has a mathematical background (she graduated with honours from the Mathematics Department of Warsaw University in 2002) as well as strong family connections with TCS :-) She has also designed the logo for the STACS conference series, amongst other things.

Thanks Emilka!

LICS 2010 Test-of-time Award Winners

I just read an email announcing the papers selected for the 2010 LICS Test-of-Time Award. For the 2010 LICS Test-of-Time Award, all papers from LICS 1990 were considered by an Awards Committee consisting of Glynn Winskel (chair), Jean-Pierre Jouannaud and John Mitchell.

In view of the weight of highly-influential papers, across a range of areas, the committee has taken the exceptional step of selecting four papers! They are:
  • Model-checking for real-time systems by R. Alur, C. Courcoubetis and D. Dill. This paper was a pioneer in the model checking of real-time systems. It provided a polynomial-space algorithm for the model checking of a real-time logic (an extension of CTL with timing constraints) with respect to a continuous-time model. Its techniques are still used extensively and results of this paper form part of almost any course or tutorial on real-time verification.
  • Symbolic model checking: 10^20 states and beyond by JR Burch, EM Clarke, KL McMillan, DL Dill and LJ Hwang. This paper revolutionized model checking. Through its symbolic representation of the state space using Randy Bryant's Binary Decision Diagrams (BDDs) and its careful analysis of several forms of model checking problems, backed up by empirical results, it provided a first convincing attack on the verification of large-state systems. The paper was a major agent in establishing BDDs as a tool in mainstream computer science.
  • The theory of ground rewrite systems is decidable by M Dauchet and S Tison. This paper asked what has proved to be a very important question, whether the first-order theory of one-step rewriting is decidable. The paper settled the question positively for the theory of ground rewrite systems using innovative techniques on tree automata. Its techniques rekindled an interest in automata theory on finite trees, now a major topic, with many current applications from rewriting through to security, program analysis and concurrency.
  • Recursive types reduced to inductive types by P Freyd. This paper showed what was really going on with the classic method of solving domain equations.  By separating positive and negative occurrences of the unknown in a domain equation, it gave an elegant category-theoretic treatment of recursively defined domains that extends the well-understood and widely-used methods of initial-algebra semantics. Its methods are now standard. They led to new techniques for relating operational and denotational semantics, and new mixed induction/coinduction principles.
Congratulations to all the recipients of the awards!