Papers I find interesting---mostly, but not solely, in Process Algebra---, and some fun stuff in Mathematics and Computer Science at large and on general issues related to research, teaching and academic life.

## Monday, June 25, 2007

### Accepted Papers for CONCUR 2007

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?

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(x

_{1},...,x

_{n}) is {x

_{1},...,x

_{n}}. Moreover, a term of the form A(y

_{1},...,y

_{n}) is structurally congruent to P[y

_{1},...y

_{n}/x

_{1},...,x

_{n}] if the body of A(x

_{1},...,x

_{n}) 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

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 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

**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

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…

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

## Monday, June 11, 2007

### Rejecting Excellent Papers

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

*Advances in Mathematics*.

## Friday, June 08, 2007

### June/July Notices of the AMS

Enjoy.

## Thursday, June 07, 2007

### Invited Speakers at ICALP 2008

- Ran Canetti (IBM T.J. Watson Research Center and MIT, USA),
- Bruno Courcelle (Labri, UniversitÃ¨ Bordeaux, France),
- Javier Esparza (Technische UniversitÃ¤t MÃ¼nchen, Germany),
- Muthu Muthukrishnan (Google, USA) and
- Peter Winkler (Dartmouth, USA).

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 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

**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.

- MIT
- University of Maryland, College Park
- CMU
- Georgia Institute of Technology
- Stanford

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 fromACM 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.