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?

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.

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.

     

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?

ICE-TCS Logo

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!

Typos, typos....

I always tell my students at all levels that there is no excuse for not spell checking one's writings. There are rather good spell-checking programs out there, and one should use them to spot obvious typos.

Spell-checking programs, however, are no substitute for careful proof reading of one's papers. I was reminded of this fact of professional life some time ago when, while reading the revision of a journal submission of mine, I spotted the mention of a "format for impotence of operators" (in lieu of "format for idempotence of operators"). It would have been embarrassing, but admittedly amusing, to send the paper off with that typo left unspotted, just as it was entertaining for my students to attend a lecture mentioning a "poof technique" (rather than "proof technique") on a slide :-)

No spell-checker can find those typos. I'll use them to motivate my students to proof read their texts with care.

ICALP 2010: Accepted papers

The list of accepted papers for ICALP 2010 is out. Based on what I saw as a PC member for track B, the overall quality of the submissions was, in general, very high and many good papers could not be selected for presentation at the conference.

Journal Editors or Black Holes?

Sometimes journal editors (or referees) are observationally very similar to black holes. A paper is submitted, but no review escapes the force of gravity generated by the scientist in question. If the academic who is submitting the paper is well established, (s)he might not be overly bothered by this "black-hole-like effect" and live to see the day. However, in case the paper is submitted by a young scientist who might be applying for jobs, the negligence of an editor or a reviewer might have negative consequences on the career of the author of the paper.

Suppose, by way of example, that a young scientist submits a substantial paper to a high-impact journal reporting on the major findings in her doctoral dissertation. The first review round takes a whole year, despite repeated enquiries to the handling editor, and the editor asks for major revisions based on the detailed referee reports. The author works hard at handling the suggestions from her reviewers, and submits a revised paper. One more year passes and the email enquiries by the author receive no answer from the cognizant editor.

What would be the best line of action for the young scientist in question? Should she wait for a second bunch of reports, which might never come, or would she be best served by withdrawing the paper and submitting it elsewhere? What advice would you give in a situation like this one?

What Are The Hot Research Areas in Concurrency Theory?

Yesterday Andrei Sabelfeld (Chalmers University of Technology, Sweden) visited ICE-TCS with Arnar Birgisson, a former master student of mine who is now doing doctoral studies under his supervision. Andrei delivered the seminar Information flow in web applications in the ICE-TCS seminar series (the abstract for the talk is here), we talked about liveness and safety properties and about academic matters in general. We at ICE-TCS enjoyed his visit a lot.

Over dinner,  Andrei asked me:

• What are the big unsolved problems in concurrency theory?
• And what are the hot research areas in the field?

I gave my quarter-baked personal answers, but I'd like to hear yours.

I have the feeling that research in concurrency theory is driven more by "hot research areas" than by collections of big open problems, but that's just my personal impression, even though at some point I started collecting a list of open problems and stated some in this essay. 

Also, how much does the "hotness of a research area" inform the research you do and that you suggest to your students? For what it is worth, for good or for worse, I mostly tend to follow my own personal interests and inclinations rather than the directions of the field at large. However, one  has to "sell" one's work and have it published. It is undoubtedly easier to do so if the work is considered to be hot and timely by a substantial fraction of the research community. Doing work in areas that are considered "important" by many will probably also give a student better opportunities to find further employment.

Overall, I feel that it is important to give one's students a good problem to work on for her/his dissertation. There are certain characteristics that a good problem should have for sure, but is "hotness" one of those?

Addendum: There is a lot of good career advice for everyone here.

LICS 2010 Accepted Papers and Martin Grohe's Latest Opus

The list of accepted papers for LICS 2010 is out. As usual, the programme looks very interesting and exceedingly strong.

For an interested, but not very knowledgeable, observer like me, one of the most interesting looking papers that have been selected for the conference seems to be yet another seminal contribution by Martin Grohe. The paper is Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors.

From the abstract of that ten-page paper, I learn that Grohe proves that fixed-point logic with counting captures polynomial time over all classes of graphs with excluded minors. To my untrained eye, this looks like an amazing result. The proof of this theorem will take up the whole of this monograph, which is currently being written and will be well over 200 pages long. The current draft spans 238 pages.

Would such a result meet the current requirements for the Gödel prize, say? It seems to me that it would not, unless Grohe also publishes a journal paper based on a fragment of his monograph. Taking the view that proofs of certain results are likely to be very long and that very few journals in computer science would publish papers that are 250 pages long, say, would it not be reasonable to let a research monograph qualify a piece of research for the Gödel prize? After all, if the result is important, it will be studied in depth by many researchers, ensuring a more thorough level of peer review than the one obtained via a standard refereeing process for a journal.

The loss of a giant: Robin Milner has passed away

I just read the following message from Gordon Plotkin. This is really sad news. I plan to post a more elaborate message soon, but we have lost another intellectual giant, a gentleman and a true inspiration for us all.

-----------------------------

Dear Colleagues,

I am deeply saddened to pass on the following message from Barney and Chloë Milner:

"We are sorry to announce that Robin Milner died on Saturday 20th March, in Cambridge, just three days after the funeral of his wife, Lucy.

He will be greatly missed by his family and friends, as well as the academic community."


Gordon Plotkin

SOS 2010

I am co-chairing SOS 2010 (Structural Operational Semantics 2010) with Pawel Sobocinski (Southampton). The call for papers has been posted on several mailing lists and all the information on this workshop, which is affiliated with CONCUR 2010, is available from the workshop's web site.

Consider submitting a paper and join us in Paris on August 30 to discuss the latest research on Structural Operational Semantics! I have a series of long-overdue posts describing some of the recent work by my co-authors and me on this topic. I hope to find some time to write those posts after the teaching is over and I have cleared my desk a little.

First Clay Mathematics Institute Millennium Prize Announced Today

It looks like the Clay Mathematics Institute (CMI) is parting with its first one million USD. Indeed, today the CMI  announced that Grigoriy Perelman is the recipient of the Millennium Prize for the resolution of the Poincaré conjecture. Full details are here and a full-length press release is also available. 

What do you think will be the next Millennium Prize Problem to fall? It seems very unlikely that it will be our own P vs. NP problem, but, as Bohr taught us,  “Prediction is very difficult, especially about the future".  

Magnús Halldórsson receives the first Reykjavík University Research Award

This is a belated post on a piece of news that is mostly of local (read, Icelandic) relevance. However, I think that TCS researchers everywhere will be pleased to know that the first research award from Reykjavík University, where I have worked since November 2005, has been given to Magnús M. Halldórsson, for his work on approximation algorithms for computationally hard problems, amongst others. (The announcement in English is here.)  It is good to see the first research award go to a TCS researcher, also because this sets high standards for future such awards.

It will be interesting to see whether future award committees will be influenced by considerations related to "academic politics" in selecting awardees for the university research award. If not, I expect to see a few awards in the coming years go to people working in (T)CS and combinatorics.

Belated congratulations to Magnús.

Two PhD Studentships Available

Yesterday night, I posted the appended announcement of two PhD studentships, which became available thanks to a successful grant application to the Icelandic Fund for Research (Rannis), on a couple of mailing lists.

I am posting it here too, just in case any of the readers of this blog is interested in applying or has any student who would be a suitable candidate for the studentships.

---------------------------------------------------------

            Meta-Theory of Algebraic Process Theories

         School of Computer Science, Reykjavik University

          Two PhD studentships

Applications are invited for two PhD studentships at the School of Computer Science, Reykjavik University.  The positions are part of a three-year research project funded by Rannis (the Icelandic Fund for Research), under the direction of Luca Aceto and Anna Ingolfsdottir.

Aim of the project

Algebraic process theories, also known as “process algebras”, are prototype specification languages for reactive systems—that is, for devices that compute by reacting to stimuli from their environment. The main strength of such theories lies in the equational (calculational) style of reasoning they support. For each process theory, several natural questions immediately arise pertaining to the (non-)existence of (finite or recursive) sets of laws that allow one to prove by “substituting equals for equals” all of the valid equalities between process descriptions (closed or open terms) over fragments of the process theory at hand. Currently, answering such questions is only possible via delicate, error-prone and lengthy proofs.

The aim of the project is to contribute further advances to the study of the meta-theory of algebraic theories of processes.  The main goals of the project are

• to establish a generic framework for answering questions pertaining to the existence of equational axiomatizations of behavioural semantics over process algebras affording certain desirable properties, such as being finite or recursive, and
  
• to apply the proposed general theory to solve some of the main open problems in the study of the equational logic of processes.
  

Research environment

The research  within the project will be carried out in close collaboration with our long-term co-workers Wan Fokkink (VU Amsterdam), Bas Luttik (TU Eindhoven), MohammadReza Mousavi (TU Eindhoven) and Michel Reniers (TU Eindhoven).

The successful candidates will benefit from, and contribute to, the research environment at the Icelandic Centre of Excellence in Theoretical Computer Science (ICE-TCS). ICE-TCS has currently 14 permanent members, seven postdoctoral researchers and one Ph.D. student.  For more information about ICE-TCS, its members and its activities, see http://www.icetcs.ru.is/.

Qualification requirements

Applicants for the PhD studentships should have a good MSc degree in Computer Science, Mathematics or closely related fields, and have a strong background in discrete mathematics and formal systems. Some previous knowledge of topics from at least one of concurrency theory, process calculi and structural operational semantics is not a prerequisite, but would be desirable.

Remuneration

PhD position: 265,000 ISK (roughly 1,550 euros) per month before taxes, for three years, starting as early as possible and no later than October 2010.

Application details

By Friday, 26 February 2010, interested applicants should send their CV, including a list of publications where applicable, in PDF to the addresses below, together with a transcript of their academic record, a statement outlining their suitability for the project and the names of two referees.

Luca Aceto
email: luca@ru.is

Anna Ingolfsdottir
email: annai@ru.is

We will start reviewing applications as soon as they arrive, and will continue to accept applications until the positions are filled. However, we strongly encourage interested applicants to send in their applications as soon as possible.

About the School of Computer Science at Reykjavik University

The School of Computer Science at RU (http://www.reykjavikuniversity.is/computer-science/) has approximately 440 students at the undergraduate, masters and doctorate levels. The School is home to several strong research groups and the main research areas are algorithmics, artificial intelligence, combinatorics, concurrency theory, databases, human-computer interaction, natural language processing, software engineering, theoretical computer science and virtual environments.

The School of Computer Science at Reykjavik University  has ties with several leading foreign universities, facilitating collaboration, as well as faculty and student exchanges. In particular, the School has a joint M.Sc. degree in Computer Science with the University of Camerino, Italy, and a joint Ph.D. degree programme with KTH, Stockholm, Sweden.

Information about Ph.D. studies at the School of Computer Science is available at

http://www.reykjavikuniversity.is/departments/school-of-computer-science/ph.d-studies/

Concurrency Column for the February 2010 Issue of the BEATCS

I have just posted the paper for the concurrency column that will appear in the February 2010 Issue of the BEATCS. This installment of the concurrency column is devoted to a very informative survey, contributed by François Laroussinie, of recent work on the modelling and specification of open systems using games and alternating-time temporal logics. In particular, the paper focuses on fundamental semantic questions for those specification formalisms, such as the kind of properties that can be stated in various types of logics for games, and on the computational complexity of their model-checking problems. Enjoy it!

My New Workplace

The School of Computer Science has moved into its premises in the new building of Reykjavik University. The building is still a construction site, and will remain so for a few more months at least. You can see some photos here. There is no doubt that the building looks good. However, I am not so sure that it will offer the best working conditions for academic work. For instance, as a consequence of the downsizing of the building because of the economic crisis in Iceland, we have no offices and we are all sitting in an open space. (I'll try to post a photo of the TCS area when I get a chance to take one.)

I am not passing judgement yet on the effect that this will have on my work. The next few weeks will allow me to form an opinion on this issue. I will try to keep an open mind and to make the most of what I have available. However, it is hard to escape the nagging thought that I had a quieter working environment when I was a Ph.D. student.

Stay tuned for more information.

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?