CONCUR 2008: Accepted Papers

The list of accepted papers for CONCUR 2008 is now available here. There will be plenty of reading to do once the ICALP organization and the course I am delivering now are over.

On a separate, but ICALP-related, note, the winner of the 2008 Gödel Prize is the paper Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time by Daniel A. Spielman and Shang-Hua Teng, Journal of the ACM (JACM), 51(3), May 2004, 385-463. The results in the paper were first presented at the Annual ACM Symposium on the Theory of Computing (STOC 01), 2001, pp. 296-305.

The prize will be awarded at the conference during the award ceremony held on Thursday, 10 July. Both Daniel A. Spielman and Shang-Hua Teng will attend the ceremony.

Change of Editor for the BEATCS

The June issue of the BEATCS will be the last issue with Vladimiro Sassone as editor of the Bulletin. Maria Jose Serna will take over from Vladimiro, who will assist her for the next couple of issues.

Vladimiro has been in charge of the Bulletin for the last five years. He has streamlined the production process and made it web-friendly. (The whole Bulletin is now produced using pdflatex.) He has inaugurated two new columns, designed and implemented a new editorial style, and was a prime mover on the issue of open access for the BEATCS.

I like to think that the quality of the BEATCS has continued improving during Vladimiro's editorship, and the whole TCS community owes him a lot of gratitude for the enormous amount of energy he has put in the editorship of the BEATCS.

I wish Maria the best of luck for her new and important role. The BEATCS needs a strong editor, and it won't be easy to follow Vladimiro's footsteps and to improve on his work. Let's help Maria by contributing pieces to the BEATCS and by thinking about ways to make that publication even better. If you have any ideas, please post a comment. I will do my best to mention your suggestions during the EATCS council meeting at ICALP 2008.

The Swan Song of SEN2 at CWI

This is a guest post from MohammadReza Mousavi on an event held yesterday at CWI to "celebrate" the demise of the project SEN2 at CWI. This marks the end of an era at CWI, and for the concurrency community all over the world. My own research career and interests over the years have benefited from, and have been strongly influenced by, the work being carried out within SEN2 and collaborations with several researchers who have been affiliated with it. Thanks to Mahammad for this post reminding all the concurrency-theory community how important SEN2 has been for the field.

Yesterday at CWI, there was a celebration of (the funeral service for) 25 years of concurrency theory, practiced at SEN2.

The meeting was attended by some 100 participants. All SEN2 leaders and all its graduated Ph.D. students were present. Four distinguished speakers gave four very interesting talks. What comes next is a brief summary of what I can recall from these interesting presentations. An abstract of the talks can be found here.

• Jos Baeten gave a brief history of 25 years of concurrency theory and practice at CWI. It all started with Jan Bergstra who cooperated with John Tucker (then at Leiden) and went on with the leadership of Jan Willem Klop, Jos Baeten, Frits Vaandrager, Jan Friso Groote, Wan Fokkink and Jaco van de Pol, all of whom after a short while became full professor at universities around the Netherlands. SEN2 has produced: about 1000 PAM talks (the last to begin given on June 18, 2008 by Jan Willem Klop), about 10 research projects, 25 Ph.D. thesis (2 in progress), hundreds of articles and CONCUR conferences (of which till now, 18 conference are held), which is a truly impressive track record.
• Then, Gerard Holzmann gave a wonderful talk on the history and state of the art on Model Checking (with an emphasis on Spin). He divided the history of model checking into 4 development phases: formalisms (from 1978-1988), algorithms (from 1988-1998), veracity (from 1998-2008) and multi-core model-checking (I am not sure if I recall this one well, from 2008-2018).
• The third speaker was Jan Bergstra, who is the father of concurrency theory in the Netherlands. (Mathematics Genealogy project counts about 50 pupils of his, see here.) He gave a very intriguing talk about many foundational issues for algebraic specification and process algebras. He said that he always believed in a number of dogmas including: superiority of total functions over partial functions, and also superiority of projective limit models to those induced by structural operational semantics. He made his point by defining a theory of meadows, which defines division as a total function (with 1/0 = 0). He showed that a very sensible algebraic theory can then be developed for meadows. Jan Bergstra stated (and to some extent showed) that this can simplify the foundations of mathematics even at the level taught in primary and high schools. His talk touched upon many other fundamental issues such as suitability of Turing Machines as the (only) foundational model for computability.
• Finally, Moshe Vardi presented a nice overview of the development of temporal logics for industrial applications. He gave an overview on expressiveness and verification complexity for linear and branching temporal logics and the developments led to practical versions of such logics such as PSL and SVA (SystemVerilog Assertion). He concluded that SEN2 has not only produced a lot of fish, but trained many skilled fishermen for the Dutch TCS community and the latter is the main contribution of SEN2, which will last forever.

Let me conclude, on a personal note, by saying that, as usual, Moshe has expressed in a nutshell one of the main forms of impact, if not the main one, that any academic institution worth its salt should have: the development of highly skilled academics who will continue sowing the seeds for the future development of their science both nationally and abroad. I won't mention names, but it will be clear to any observer that SEN2 has played this role very well over its life span.

More on Reverse Age Discrimination in Italian Universities

A while back, I wrote a post spurred by a reading of the commentary Reverse Age Discrimination, written for Nature Physics by Francesco Sylos Labini and Stefano Zapperi, two physicists based in Rome. I was reminded of that piece over the week-end, when I glanced at this on-line article from La Repubblica, a widely read Italian newspaper. The article is in Italian, and so won't be accessible to most readers. However, the figures mentioned in that article will be clear to everyone.

Here is the executive summary. Italian academic staff has never been older. The average age of associate and full professors is over 51. Over 50% of Italy's full professors is older than 60, about 8% is over 70, only 1,7% is under 40 and less than 19% is under 50. About 25% of the associate professors is over 60, and only 10% is under 40. Looking at researchers, a paltry 2% is younger than 30.

How does my home country compare with other European countries? Not well, alas, judging from the figures mentioned in that article. The average age of university professors is 45 in France, 44 in Spain and 42 in Germany. There is more. In Italy only 4% of university professors is below 34. Compare this figure to the ones in France (21%), the UK (27%), Finland (28%) and Germany (32%), and you will see why Italy continues to suffer from brain drain whereas other European countries are reversing this trend.

Can anybody point out similar statistics for countries like Australia, Canada, Israel and the USA, say? And what about Eastern Europe?

One thing seems clear to me, and it breaks my heart to say so. A country that does not offer better job opportunities to its young academics will suffer in the not-so-distant future and runs the risk of losing whole generations of gifted researchers. I hope that things will change soon, but I am not very optimistic.

Concurrency Column for the BEATCS: June 2008

I have just posted the Concurrency Column for the June 2008 issue of the BEATCS. It is an excellent survey paper entitled 20 Years of Modal and Mixed Specifications by Adam Antonik, Michael Huth, Kim G. Larsen, Ulrik Nyman and Andrzej Wasowski.

Modal transition systems are a variation on the classic model of transition systems where transitions come in two flavours: those that any refinement of the given specification must possess, and those that it may, but is not required to,
have. This model of computation was introduced about twenty years ago by Kim Guldstrand Larsen and Bent Thomsen. Since then, it has been the subject of investigation by several groups of researchers, and interest in this model and in its sibling that goes by the name of mixed specifications has grown over the last few years. In the light of the recent rapid growth in the research literature on modal and mixed specifications, and their applications, I thought that it was appropriate to devote an instalment of the Concurrency Column to a survey of recent results and open problems in the field. I am very happy to be in a position to offer the readers of the Concurrency Column this excellent overview paper by some of the prime movers in the development of the theory and applications of modal and mixed specifications. I trust that this piece will be of general interest, and I hope that it will entice several researchers to contribute to the on-going work on these models. Enjoy!

If you'd like to contribute a piece to the Concurrency Column, do write to me.

Interview to an Opinionated Mathematician

About a fortnight ago, I had to make a sudden trip and, as reading material, brought with me some print-outs that had been lying on my desk for a long time. One of those was An Interview with Vladimir Arnold, which appeared in the Notices of the AMS in 1997. Vladimir Arnold is regarded as one of the great living mathematicians and the number of disciplines in which he has worked is truly astounding. (The areas are Dynamical Systems, Differential Equations, Hydrodynamics, Magnetohydrodynamics, Classical and Celestial Mechanics, Geometry, Topology, Algebraic Geometry, Symplectic Geometry, and Singularity Theory.) What I found out by reading the above-mentioned interview is that he is certainly a man with strong opinions and that he has no qualms about airing them.

One answer of his that really got me thinking was this one:

Lui: Do you notice any differences in the way people from different cultures do mathematics?

Arnold: I was unaware of these differences for many years, but they do exist. A few years ago,
I was participating in an International Science Foundation (ISF) meeting in Washington, DC.
This organization distributes grants to Russian scientists. One American participant suggested
support for some Russian mathematician because “he is working in a good American style.”
I was puzzled and asked for an explanation. “Well,” the American answered, “it means that he is traveling a lot to present all his latest results at all our conferences and is personally known to all experts in the field.” My opinion is that ISF should better support those who are working in the good Russian style, which is to sit at home working hard to prove fundamental theorems which will remain the cornerstones of mathematics forever!

It is certainly true that travel and networking are fundamental parts of our daily life at work. What Arnold seems to be saying, however, is that we may be pushing this part of our work too far, and that this might be detrimental to the purely scientific part of our work. Of course, each of us has different work pattern, but there seems to be a tendency these days to shun good old scholarship for the modern gods of networking, leadership and what not.

Arnold also paints a picture of his days as a student at Mechmat (Moscow State University Mechanics and Mathematics Faculty) in the fifties. He says:

"The constellation of great mathematicians in the same department when I was studying at the
Mechmat was really exceptional, and I have never seen anything like it at any other place. Kolmogorov, Gelfand, Petrovskii, Pontriagin, P. Novikov, Markov, Gelfond, Lusternik, Khinchin,
and P. S. Alexandrov were teaching students like Manin, Sinai, S. Novikov, V. M. Alexeev, Anosov, A. A. Kirillov, and me."

I guess that it is hard to argue against his opinion. I looked up some of these names on the web, and this is really a most impressive collection.

Finally, to add a little more to the debate, Arnold seems to indicate that in 1997 it was still possible for a Western mathematician to build a good career rediscovering weaker versions of results known earlier to Russian mathematicians. And I have not mentioned his opinions on Bourbaki and the French mathematical establishment :-)

There are definitely worse ways to spend a few minutes during a flight than reading that interview.

ICALP 2008 Early Registration Deadline TOMORROW

The early registration deadline for ICALP 2008 is tomorrow. I strongly encourage you to register by May 5 at the latest to take advantage of the early registration rate and secure suitable accommodation.

In the meantime, the list of accepted papers/speakers for the affiliated workshops are being made available. See

• Foundations of Information Management in Networks (July 6)
• Quantum Physics and Logic/Developments in Computational Models (July 12 and 13) and
  
• Second International workshop on Mobility, Algorithms and Graph theory In dynamic NEtworks (IMAGINE 2008) (July 12).

Call for Nominations: The 2008 Edsger W. Dijkstra Prize in Distributed Computing

The call for nominations for the 2008 Edsger W. Dijkstra Prize in Distributed Computing is now out. See here. The prize is given for outstanding papers on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing has been evident for at least a decade, and is sponsored jointly by the ACM Symposium on Principles of Distributed Computing (PODC) and the EATCS Symposium on Distributed Computing (DISC). The award is presented annually, with the presentation taking place alternately at ACM PODC and EATCS DISC - this year it will be presented at PODC 2008.

Let's think up outstanding nominations!

Complete Scientific Programme for ICALP 2008

The scientific programme for ICALP 2008 is now available here. It looks like we are going to have a scientific feast, and hopefully many of you will come and join us.

ICALP 2008: Bird's Eye Programme

In case you are wondering what is going to happen at ICALP 2008, and when, I encourage you to look at the skeleton of the conference programme, which is available here. Some more detail is presently available for track B.

The conference organizers strongly recommend that you register for the ICALP conference and book accommodation before May 5th, as that date is the deadline for registering at the lower fee. After May 5th hotel rooms will also start to get released since July is the prime holiday season in Iceland and the demand for hotel accommodation is very high.

NOTE: For those who have not decided yet which workshop(s) they are going to attend when registering for the conference, it is possible to register for workshops at the lower fee until June 5th by sending an e-mail to the Conference Secretariat.

Look Who's Doping

The inimitable Dr. Z wrote in his April 1, 2008, opinion:

But I strongly disagree with the unfortunate decision to forbid the use of any result, or solve any open problem posed by, the great Paul Erdös, on the grounds that he was "doping" by using stimulants like amphetamines. While I definitely do not recommend anyone to start taking prescription drugs, mathematics is not (yet) the tour-de-France, and if we start forbidding them, what's next? coffee?. It is no coincidence that Erdös quipped that a mathematician is a machine that turns coffee into theorems. Without coffee (and unfortunately other stimulants) we would not have progressed beyond Euclid. Coffee is so much part of our culture that it would take much more than one committee to disallow it at AMS meetings.

On the same day, a press release written by evolutionary biologist Jonathan Eisen of the University of California, Davis, declared that the US National Institutes of Health is to crack down on scientists 'brain doping' with performance-enhancing drugs such as Provigil and Ritalin.

These were, of course, intended as two funny pranks. Now, however, Nature is spotlighting a study on the use of cognition-enhancing drugs by academics. (Alas, a subscription is needed to access the text.) The article in Nature reports on the results of a survey conducted by that journal on whether readers of Nature (scientists) would consider “boosting their brain power” with drugs. The article states that 1,400 people from 60 countries responded to the online poll.

Apparently "one in five respondents said they had used drugs for non-medical reasons to stimulate their focus, concentration or memory." Moreover, use of drugs did not differ greatly across age-groups. According to the article, "the numbers suggest a significant amount of drug-taking among academics." So, not only academics drink more than rest of population on average (or so I seem to recall reading somewhere recently), but they also enhance their performance by taking drugs :-) Will we soon have to sign declarations that our work was not done under the influence of performance-enhancing drugs as well as copyright release forms? Or will we have to have drug tests taken when we submit papers to conferences or journals? And will all authors of an article have to take such tests?

On a more serious note, as a parent, I was a little concerned when I read that

When asked whether healthy children under the age of 16 should be restricted from taking these drugs, unsurprisingly, most respondents (86%) said that they should. But one-third of respondents said they would feel pressure to give cognition-enhancing drugs to their children if other children at school were taking them. Morein-Zamir found this coercive factor very interesting. “These numbers strongly suggest that even if policies restricted their use by kids, pressure would be high for parents,” she says.

(The emphasis is mine.) Would you give drugs to your children to enhance their mental performance?

Sometimes I wonder what our answer would be if we were offered a Faustian pact promising that we would solve, say, two fundamental problems of our choice at the price of our "soul". What would your reaction to this "two-for-the-price-of-one" offer be? Has any science-in-fiction novel ever been written on this theme?

Addendum: After I wrote this post, Luca Trevisan pointed out to me the delightful short story "The devil and Simon Flagg" by Arthur Porges. I recommend it!

Accepted Papers for ICALP 2008--Track C

The list of accepted papers for track C of ICALP 2008 is now available here. You can get an overview of all of the accepted papers from this web page.

I strongly encourage all of you who are planning to come to Iceland for ICALP 2008 to start planning your trips now. In addition, if you register now you can take advantage of the present strength of many foreign currencies vis-a-vis the Icelandic crown :-)

I also strongly recommend signing up for the conference dinner. The conference dinner will be held at Perlan (The Pearl). (See the photo above.) The Perlan restaurant is consistently one of the best restaurants in town and is Reykjavik's latest landmark. Towering over the city from one of its highest hills, Perlan sits atop the geothermal reservoir tanks overlooking the city. The top floor restaurant is enclosed in a glass dome and the floor rotates 360^o degrees every 90-120 minutes. The restaurant offers a stunning panoramic view of Reykjavik and the surrounding areas.

See also the other events in the social programme. I'll post more information on ICALP 2008 on this blog at a later date. In particular, the Gödel prize winner for 2008 will be announced very soon.

Terence Tao Receives NSF Award

The NSF has bestowed the Waterman Award to Terence Tao. (The press release is here.) The list of Tao's awards is already very long, and includes the Salem Prize in 2000, the Bochner Prize in 2002, the Fields Medal and SASTRA Ramanujan Prize in 2006, and the MacArthur Fellowship and Ostrowski Prize in 2007.

And he even finds the time to write very detailed and informative blog posts!

Accepted Papers for ICALP 2008, Track B

The list of accepted papers for track B of ICALP 2008 is now available. The list of accepted papers for ICALP Track A has been posted yesterday evening, and already a few blogs have pointed to it. See the Complexity Weblog, David Eppstein, and Michael Mitzenmacher. It seems to me that the PCs for the ICALP tracks have faced some very hard choices this year since the quality of the submissions was very high.

I'll post the list of accepted papers for track C when it becomes available.

Rankings of CS Departments in the USA

I learned from Mihai Patrascu's blog that the US News rankings for 2008 have been released. The rankings for computer science, for CS theory, and for mathematics do not show any truly major surprises.

In your opinion, what are the best CS departments in theory outside the US? And how would you compare them with the top departments in the US News ranking? Perhaps more modestly, what are the best CS departments in TCS in your country?

The Equational Theory of Prebisimilarity over Basic CCS with Divergence

I recently posted the short paper

Luca Aceto, Silvio Capobianco, Anna Ingolfsdottir and Bas Luttik. The Equational Theory of Prebisimilarity over Basic CCS with Divergence. March 2008.

This paper studies the equational theory of prebisimilarity, a bisimulation-based preorder introduced by Hennessy and Milner in the early 1980s, over basic CCS with the divergent process Omega.

It is well known that prebisimilarity affords a finite ground-complete axiomatization over this language. This finite axiomatization is obtained by adding the inequation

Omega <= x

to the complete axiomatization of bisimilarity over basic CCS. In the above paper, we prove that this ground-complete axiomatization is also complete in the presence of an infinite set of actions. Moreover, in sharp contrast to this positive result, we show that prebisimilarity is not finitely based over basic CCS with the divergent process Omega when the set of actions is finite and non-empty.

February 2008 Issue of the BEATCS

Volume 94 of the Bulletin of the EATCS is now available on line, freely and to everybody as it should be.

Of course, you should read the two pieces that make up the concurrency column :-) In addition, apart from the contributions to the other columns in the Bulletin, I encourage you to have a look at A "big-ideas" approach to teaching Computation Theory , a contribution to the educational column by Arnold L. Rosenberg. I have not had time to mull over his proposal yet, but it is certainly worth thinking about it and contributing our two-cent worth to what is an interesting opinion on how to teach one of our flagship courses.

Let me encourage you to support the EATCS by becoming a member of that association. For a mere 25 € 30 € per year (25€ if you are also a SIGACT member), you will make sure that the EATCS can continue supporting TCS research as a whole.

What is the Shortest PhD Thesis in TCS?

Gmail's webclips feature alerted me to the availability of Edmund Landau's PhD thesis in English translation. The thesis is 13 pages, which is substantially shorter than any PhD thesis in CS I am aware of.

I suspect that PhD theses in mathematics are, by and large, shorter than those in TCS. What is the shortest PhD thesis in either subject you are aware of? (In the case of mathematics, let's restrict ourselves to modern times, but if anyone knows of a thesis that is shorter than Landau's I'd be interested in knowing the details.)

Here is my own contribution. Off the top of my head, I recall that Jay Loren Gischer's PhD thesis from Stanford (year: 1984; topic: the theory of pomsets; supervisor: Vaughan Pratt, see also here) was between 45- and 50-page long.

Abel Prize 2008

The Norwegian Academy of Science and Letters has decided to award the Abel Prize for 2008 to John Griggs Thompson, University of Florida and Jacques Tits, Collège de France. Thompson and Tits receives the Abel Prize “for their profound achievements in algebra and in particular for shaping modern group theory”.

The committee's citation can be read here. Thompson and Walter Feit are the authors of the famous Odd Order Paper, filling a whole issue of the Pacific Journal of Mathematics. Georges Gonthier is leading an effort that aims to produce a computer-checked proof of this famous result in group theory.

The Usefulness of Bisimilarity Checking in Practice

I am collecting information as well as opinions on the practical usefulness of bisimulation checking. I feel that there are disparate views out there and they may be worth recounting. I plan to solicit opinions from experts in the verification community, but I am also interested in the thoughts on this topic of the readers of this blog. Feel free to email me your opinions or to post a comment. I would also appreciate receiving bibliographic references where the usefulness of bisimulation checking and bisimulation minimization are discussed.

Thanks in advance!