## Monday, June 25, 2007

### Accepted Papers for CONCUR 2007

The list of accepted papers for CONCUR 2007 is finally out. You can browse through the list here. The programme looks exciting, and I am looking forward to attending the conference.

The list of invited talks and tutorials is here. It will be a great honour to deliver an invited talk at that conference. (An honour that I cannot help but feel should have been bestowed on many other colleagues of mine.) I will eventually post the slides for my talk on this blog. Check this space if, for some reason, you are interested in the talk I plan to give.

## Friday, June 22, 2007

### What is a Free Name in a Process Algebra?

This is the question addressed by a short paper by Flemming Nielson, Hanne Riis Nielson and Henrik Pilegaard that appears in Information Processing Letters 103 (2007), pp. 188-194. In the paper, the authors show that the standard definition of free name is not preserved under the structural congruence, which is one of the sanity properties one would expect to have.

The traditional definition of the set of free names of a process term stipulates that the set of free names of a parameterized constant A(x1,...,xn) is {x1,...,xn}. Moreover, a term of the form A(y1,...,yn) is structurally congruent to P[y1,...yn/x1,...,xn] if the body of A(x1,...,xn) is the term P.

Consider now, for instance, the constant A(x) with body 0. The A(x) has x as its only free name. But this term is structurally congruent to 0, whose set of free names is empty! This is an example showing that the traditional definition of free names is not preserved by structural congruence, and we certainly want a process constant to be congruent to its body.

Why didn't anybody notice this before? As the authors write in their paper "Unfortunately the notion of free names is usually considered so simple that a formal definition is dispensed with and this occasionally shows up as problems in proofs."

In that paper, the authors develop a fixed point approach to the set of free names, argue that the set of free names can be computed efficiently and show that it is invariant under structural congruence.

I strongly recommend reading the paper.

## Thursday, June 21, 2007

### Book Promotion

I apologize for the self-promotion and marketing :-)

In case any of you are looking for some summer reading, I recommend, not surprisingly, the book advertised in this flyer. If you purchase the book using the flyer, you'll have a 20% discount. Get your university library to order a few copies!

Here is what the endorsers of the book have to say about it. (Edited excerpts from the endorsements appear on the back cover for the book.)

## Wednesday, June 20, 2007

### ICALP 2008: Call for Workshops and Web Site

The call for workshops for ICALP 2008 has been posted on a large collection of mailing lists today. Consider proposing a workshop and making a trip to Iceland for the event! The deadline for workshop proposals is October 31, 2007. You'll be notified of acceptance/rejection of your proposals by 21 November 2007 at the latest.

The web site for the conference is located here. It is still preliminary, but all of the pieces of information that are relevant at this stage are already in place. For a sneak preview of the call for papers, look here.

Watch this space for further information on the development of the conference organization.

## Tuesday, June 19, 2007

### Avi Wigderson's Louis Clark Vanuxem Lectures

I recently stumbled across the slides for "A world view through the computational lens", three talks given at Princeton University by Avi Wigderson. These talks, which were delivered in the Louis Clark Vanuxem series, form an excellent companion to the talk that Papadimitriou recently gave at FCRC. See this post.

The plan for Wigderson's series of lectures is as follows.

There is a lot of inspiration to be drawn from those slides. Is TCS really the "new math"? Only time will tell, but this really a good refrain to listen to anyway :-)

## Friday, June 15, 2007

### Computing Community Consortium Workshop at FCRC

The Computing Community Consortium (CCC) was recently created by the Computing Research Association (CRA) and is funded under a cooperative agreement from the National Science Foundation (NSF). The purpose of the CCC is to catalyze the computing research community to debate longer range, more audacious research challenges; to build consensus around research visions; to articulate those research visions; to evolve the most promising visions toward clearly defined initiatives; and to work with funding organizations to move the challenges and visions toward funding initiatives.

This week the CCC is organizing a workshop at the 2007 Federated Computing Research Conference. The slides for the contributed talks given so far are available here. (Lazowska's slides are still missing at the time of writing since his talk will be delivered today. I am looking forward to seeing them!) They are all interesting at first sight. In particular, I want to encourage readers of this blog to look at the wonderful slides for Christos Papadimitriou's talk on the Algorithmic Lens. The slides give Christos Papadimitriou's view of the impact that computer science is having on other sciences, and can offer all of us plenty of food for thought as well as material for enticing students to CS.

In case you do not have time to look at the slides, the executive summary of the talk, presented on the last slide reads:
• The algorithmic world view is changing the sciences: mathematical, natural, life, social
• CS is placing itself at the center of the scientific discourse and exchange of ideas
• And this is only the beginning…
Thanks Christos!

Addendum: Ed Lazowska's slides are now on line.

## Monday, June 11, 2007

### Rejecting Excellent Papers

Is it good for a journal, no matter how prestigious, to reject excellent scientific contributions on the grounds that it gets substantially more first-rate submissions than it is able to accept? In TCS, I am aware that JACM has such a policy, and I wonder whether it is backfiring badly. (My, possibly wrong, impression is that several authors decide not to submit top-notch papers to that journal because of that policy. I myself have always some trouble in deciding whether a paper is among the best papers of the year in its area since this seems to involve some crystal-ball gazing.)

A recent, remarkable instance of this kind of rejection is mentioned in a letter in the latest issue of the Notices of the AMS. (See here, on page 2 of the file. The letter is co-signed by Vaughan Pratt, one of my favourite theoretical computer scientists.) Apparently, the editorial board of the Journal of the AMS, which is the flagship journal of the American Math Society, has declined to publish a 14-page paper reporting on Friedrich Wehrung's solution to Dilworth's Congruence Lattice Problem for its lack of “interaction with other areas of mathematics”. The problem had been open for about fifty years, and drove the development of lattice theory during that time. See this web page for more information.

I am sure that the author will rapidly publish the paper in a top-notch journal, given that it had glowing referee reports. What I am not sure of is how many, apparently superb papers, a journal can decline to publish before authors stop submitting to it.

I guess that, as usual, the great judge will be Time.

Addendum 12 June 2007: A look at Friedrich Wehrung's publications page indicates that the aforementioned paper of his is going to appear in

## Friday, June 08, 2007

### June/July Notices of the AMS

The latest installment of the Notices of the AMS is out with a new look and some interesting-looking articles. I am certainly going to look at the article on The Mathematical Work of Jon Kleinberg by Gert-Martin Greuel, John Hopcroft, Margaret H. Wright, and at the contribution on the highly-successful math department at UCLA. The contribution by Graetzer on Two Problems That Shaped a Century of Lattice Theory looks worth a browse, even though the math is surely way beyond my knowledge of lattice theory.

Enjoy.

## Thursday, June 07, 2007

### Invited Speakers at ICALP 2008

This is my second news item on the organization of ICALP 2008 (7-11 July 2008, Reykjavik, Iceland). On behalf of the organizing committee, I am pleased to give you the preliminary list of confirmed invited speakers. These are:
In addition, the recipients of the EATCS award and of the GÃ¶del prize 2008 will deliver talks.

Anna, Magnus and I are very glad to be able to offer participants at ICALP 2008 this outstanding set of invited talks.

Preliminary call for workshops and call for papers will be posted on this blog and on mailing lists very soon. Watch this space if you want to be the first to know!

## Tuesday, June 05, 2007

### AITO Dahl-Nygaard Prize Winners for 2007

I just saw that the Dahl-Nygaard Prizes for 2007 will be given to Luca Cardelli, Microsoft Research Cambridge (Senior prize) for his overall contribution to both theory and practice for object-oriented languages, and to Jonathan Aldrich, Carnegie Mellon University Pittsburgh (Junior prize) for his recent contribution to expressing and verifying software architecture in object-oriented languages.

I am very pleased to see Luca Cardelli honoured in this way, and I trust that this won't be the last award he will receive for his outstanding research achievements. Luca is a one-man research team, and he is equally at ease in theoretical as well as in implementation work. The text accompanying the notification singles out his famous book "A Theory of Objects", published with Martin Abadi in 1996, the Ambient Calculus (developed with Andy Gordon) and his work in Computational Systems Biology.

Congratulations to Luca!

### Ranking

My gmail RSS monitor has alerted me that the June issue of CACM includes the article Automatic and versatile publications ranking for research institutions and scholars by Jie Ren and Richard N. Taylor. In that article, the authors briefly discuss the role of rankings of institutions and individuals in modern academic life, present the main criteria used in existing rankings, and introduce their own fully automatic ranking system, which is available here.

I have not played with the authors' system yet, but the tables they present to substantiate its quality make for some interesting reading. The top five computer science departments in the US, according to their ranking, are as follows.

1. MIT
2. University of Maryland, College Park
3. CMU
4. Georgia Institute of Technology
5. Stanford
UC Berkeley is "only" 10th (something that I find surprising), Princeton is 22nd and Harvard is 41st (which I find less surprising).

In Software Engineering, as an Italian abroad I am glad to see the Politecnico di Milano in 8th place and the University of Bologna in 41st. Amongst individual researchers in SE, Paola Inverardi is ranked 17th. Perhaps interestingly, the SE rankings given in the article differ significantly from those obtained by others in a previous ranking exercise.

This is what the authors have to say.

Our ranking is significantly different from the JSS ranking. The second column in Table 2 shows that only two of the top 15 institutions from the JSS ranking are among the top 15 of our ranking. The second column in Table 3 shows that only two of the top 15 scholars from the JSS ranking are among the top 15 of our ranking.

Two policy disparities probably contribute to the difference. First, we included two conferences in our ranking that the JSS ranking did not consider. Secondly, our ranking and the JSS ranking selected different journals and these journals contributed scores differently. The JSS ranking heavily relies on papers published in itself and the journal Information and Software Technology. It also includes a magazine, IEEE Software. The JSS ranking receives almost no influence from ACM Transactions on Software Engineering and Methodology. This study illustrates that the framework can produce dramatically different results when used with different policies, even for the same field.

What does this indicate? Automatic rankings will be very useful in the future, but it will be all the more important to specify clearly how such rankings are obtained. In particular, when evaluating the results of such ranking exercises, I'd really like to know what publication outlets were considered, what weight they were given, and what weight was given to multi-authored papers. I do not see why the author of a multi-authored paper should necessarily receive a fraction of the points awarded to the paper. Is writing a paper with a co-author less work than doing it alone?

## Monday, June 04, 2007

### Invited Paper for CONCUR 2007

I have posted my contribution to the Proceedings of CONCUR 2007. The paper, coauthored with Anna and entitled The Saga of the Axiomatization of Parallel Composition, is a survey of recent work Anna and I have done in collaboration with Wan Fokkink, Bas Luttik and MohammadReza Mousavi. We published some of this work directly in journals, and so it felt appropriate to present it in a conference proceedings. I'll be basing my invited talk at CONCUR on the paper.

Thanks a lot to Anna, Bas, Mohammad and Wan for our pleasant collaborations so far. I hope to do some justice to our joint work in Lisbon. It'll be a bit of a challenge to make the audience interested in the story I have to tell, but it is one I hope to meet decently well. It'll be up to the participants at CONCUR 2007 to tell whether I'll succeed.

Surprisingly, the list of accepted papers for the conference is not yet available from the CONCUR 2007 web site. I am looking forward to viewing the programme for this event.