EATCS Award 2007

Breaking news. The EATCS award 2007 will go to Dana Scott (CMU). The official motivation for the award is appended. I nominated somebody else, but there is no arguing about an award to the father of the denotational semantics of programming languages :-)

Dana Scott has also received the following prizes:

LeRoy P. Steele Prize	American Mathematical Society, 1972
Turing Award (with Michael Rabin)	Association for Computing Machinery, 1976
Harold Pender Award	University of Pennsylvania, 1990
Rolf Schock Prize in Logic and Philosophy	Royal Swedish Academy of Sciences, 1997
Bolzano Medal for Merit in the Mathematical Sciences	Czech Academy of Sciences, 2001

See here for some biographical information.

===========================

EATCS AWARD 2007
MOTIVATION

Dana Scott is an outstanding scientist with a deep and lasting influence on Theoretical Computer Science. In a few words his contributions belong to three tracks of fundamental research:

- The introduction, in collaboration with Rabin, of non-deterministic machines in Automata Theory, which earned them the 1976 ACM Turing Award.

- The mathematical foundation to the denotational semantics of programming languages, also known as the Scott-Strachey approach to semantics, for which he is best known in Theoretical Computer Science.

- The invention of LCF (Logic for Computable Functions), which was hugely influential in the development of program logics and modern proof checking technology.

More recently he has further advanced the foundations of denotational semantics in two directions: Synthetic Domain Theory (a way to view domains as sets in a non-standard set theory) and Equilogical Spaces, which appear to be a natural extension of domains.

In 1930-40 the work of mathematicians such as Goedel, Turing, Tarski, and Church had profound consequences on Mathematical Logic and gave origin to Computability Theory. Dana Scott is among the top researchers who carried that mathematical tradition into Computer Science. Denotational semantics is the natural evolution of Tarskian (compositional) semantics for logical languages into the realm of programming languages, and Domain Theory provides the needed semantic objects. In particular, effectively-given domains (and Information Systems) extend the notion of computability well beyond natural numbers and strings.

LCF was a major contribution to program logics, which led to work on PCF, sequentiality, higher-type computability, and modern proof checking technology.

Dana Scott has obtained fundamental results also in Set Theory, Model Theory, Modal Logic, Topology, Category Theory, and Realizability. His work on constructive mathematics, and also his lucid expositions of the work of others, had a great influence on the uses non-classical logics (e.g. constructive reasoning, modal logics for concurrency, propositions-as-types) in computing. He made a whole generation see the potential of non-standard logics, an idea as revolutionary as the one of non-standard geometries had been.

Dana Scott's research career has spanned Computer Science, Mathematics, Logic, and Philosophy, and has been characterized by a concern for elucidating fundamental concepts, with a focus on mathematically hard problems that bear on these concepts. His influence in forming
mathematical foundations for Computer Science is now visible over a period of over 40 years. The European research community of Theoretical Computer Science owes a lot to his thoughts and is flourishing while pursuing the directions he started.

Brain Drain and Brain Gain, Redux

I have received the following comments on my brain drain post from Jorge A. Perez, a Colombian student who just started his PhD studies at the University of Bologna under the supervision of Davide Sangiorgi, one of the Italian TCS researchers who made it back home safely. I am happy to post Jorge's comments, as they indicate that Italian CS is moving in the right direction.

I've read your recent post with interest, as I make part of the minority that has chosen Italy as a place to do a PhD. I am a Colombian, and have recently joined the CS department at Bologna,
under a new scheme for admitting (and reserving scholarships) for foreigner students.

Two specific comments on the post:

- It is certainly surprising to observe that Italy and Colombia share this "runaway brains" problem. This, of course, occurs because of very different reasons. Naturally, the surprise behind all this is that Italy is a G8 country and Colombia is a third-world country that spends most of its money on military expenses.

- Recently, there has been an increasing offer of PhD positions in CS for foreigners. Indeed, a number of CS departments (e.g., Bologna, Pisa, Verona, Trento) now admit foreign applications, usually based on CV and recommendation letters. This seems to be the right direction in order to compete with other European countries. Moreover, this initiative could be imitated in several other fields.

I have to say that even with the problems Italy has in some aspects of doing research, at Colombia Italy is seen as a very attractive option to do a PhD in CS. The possibility of working with strong researchers is an incredible advantage that, in several ways, compensates some
things that could be considered as drawbacks.

Brain Drain and Brain Gain

Nature has a short article that tries to explain the context for the "Brain Gain" plan of the Italian Ministry for University and Research, including some recent developments related to abuses of the ministerial plan. There are also online comments. (These are substantially fewer than I would have expected for such a contentious topic.) I invite all of you to read the piece, and Luca Trevisan's excellent post on the The Runaway Brains phenomenon.

I do not have that much to add to Luca T.'s analysis, so I'll just limit myself to adding a couple of comments, and to reiterating some opinions and facts that I already stated in some related posts.

First, let me go on record once more as stating clearly that there is a lot of talent in Italian universities. Italian researchers perform very well despite the lack of support the system gives them. However, Italy must do its very best to attract outstanding, foreign scientists (and students) in order to compensate for its brain drain. (I hate this expression, but it has become so widely used that I am forced to use it too.) This won't happen unless much needed, expensive, and probably very unpopular structural changes are made.

Every CS department in virtually every university that matters in the world has foreign members of staff and foreign students (at least at MSc and PhD level). A look at an average Italian department paints a different picture. According to the interesting little book Ipotesi sull'università by the mathematicians Mariano Giaquinta and Angelo Guerraggio only 2% of the students in Italian universities are foreigners. Moreover, for good or for worse, an observer is not unlikely to notice a certain amount of academic inbreeding in the lineage of members of staff.

Something is badly wrong when a school of the outstanding quality of the Scuola Normale Superiore di Pisa has 11 PhD scholarships in mathematics, receives only 13 applications (all from Italian candidates, and none from the school itself), and selects only 4. (Source: Una storia inquietante (An unresting story) by Mariano Giaquinta and Angelo Guerraggio in Lettera Matematica Pristem 60, pp. 4-6.) Does this mean that even a school of that quality does not advertise its vacancies internationally? Or, possibly even worse, does this mean that no student out there perceives that school in Italy as a good location for PhD education? The lack of local applicants might be read as indicating that Italian students with an MSc in mathematics from the Scuola Normale Superiore di Pisa prefer to work on their PhDs somewhere else, and most likely abroad. This is great, but history shows that not many of those people will make the trip back to Italy to bring back to my home country the experience they have amassed abroad.

One of the online comments to the Nature news item reads:

Usually Italian scientists working in Italy are the best one.
In fact, an Italian scientist will not go abroad for a Ph.D. or postdoc
if she/he can remain in Italy with a good salary.
This is due to the fact that Italy is a wonderful place to live.

So, it is true that in Italy there are very few research positions
but they are usually occupied by the best ones.

Italy is indeed a lovely place to live. However, data like the aforementioned ones seems to indicate that it is not quite correct to say an Italian scientist won't go abroad if (s)he can remain in Italy. A look at at the list of people I compiled off the top of my head while writing this post indicates otherwise. The writer of that comment might ask himself why foreign researchers do not consider Italy as an attractive working place despite being a lovely place to live. The answer won't be pretty.

As an Italian abroad, I sincerely hope that things will change soon.

Advertisement for Deanship

As promised in a previous post, here is the "call for dean" just issued by the School of Science and Engineering at Reykjavík University. I am curious to see what applicants we'll get. (Note: I am not a member of the evaluation committee :-))

Corrigendum 4/2/2007: The deadline for applications is 1 March 2007, and not 15 February 2007, as incorrectly stated in the above announcement.

New Chair for the Etaps Steering Committee

Breaking news: Vladimiro Sassone has just been elected as the chair of the ETAPS steering committee. Congratulations to Vladimiro, and thanks to Perdita Stevens, the outgoing chair, for her sterling work.

Bourbaki

Lance Fortnow recently devoted a post to The Bourbaki Lecture. Reading his post, reminded me that I had in mind of scribbling a couple of lines on the book Bourbaki: A Secret Society of Mathematicians by Maurice Mashaal, Pour la Science - AMS, 2006, 168 pp. I came across that book while looking for another one at the university library, and decided to borrow it. I am glad I did!

For one, I did not know that André Weil (1906-1998) introduced the symbol for the empty set that we now universally use. (A whole issue of the Notices of the AMS is devoted to Weil.) Nor did I know that Boubarki coined the terms injection, surjection and bijection, and invented the notion of filter. Not to mention the striking similarity between André Weil and Eugenio Moggi! (Eugenio, I hope that you don't mind me mentioning this!)

More seriously, I really enjoyed reading that book, and I warmly recommend it. It tells what was good, and what was bad, with Bourbaki and its view of mathematics. It is also full of eminently quotable sentences from the Bourbaki members. Examples?

"You can't do good work in applied mathematics until you can do good work in pure mathematics." (Jean Dieudonné (1906-1992), cited on p. 119)

"[...] logic is the mathematician's hygiene, but it does not provide his meals. The big problems constitute the daily bread on which he lives." (André Weil in The Future of Mathematics, 1948) Shame on you Weil!

The closing paragraph of the book is poignant:

"Despite some mistakes, Bourbaki did add a little to the "honour of the human spirit." In an era when sports and money are such great idols of civilization, this is no small virtue."

Indeed, not to mention that the members of Bourbaki have included some of the greatest mathematical minds of the last century.

Great minds can also make great mistakes (for instance, Bourbaki's disdain of probability theory had a very negative effect on French work in that very important area of mathematics, and Bourbaki was very dogmatic in his view of mathematics), and one of the virtues of the book is that these are not swept under the carpet. Read it, and form your own opinion on this non-existent, and most prolific mathematician.

Change of Dean

At a meeting with the staff members of the School of Science and Engineering held yesterday, the new rector, Svafa Grönfeld, announced that the dean of the school, Bjarki Brynjarsson, is stepping down from his position.

A five-person evaluation committee will be formed by early next month, and its first assignment will be to set down criteria for the selection of the new dean for the School. I expect that an advertisement for the position will be published in early March.

Watch this space if you are interested in the job!

Trying to Influence Research Funding in Iceland

Parliamentary elections are coming up in Iceland, and a bunch of scientists are trying to put funding for research on the political agenda. This group blog is an attempt at keeping the discussion of this issue alive. As you can see, most of the posts are encrypted in Icelandic. However, since my knowledge of Icelandic is not what it should be, I use English for my posts on that blog.

In case anybody is interested, I posted an entry entitled More Funding and More Variety! In that post I sing the praise of some types of funding that is available in countries like The Netherlands and Denmark, but not in Iceland. Comments are most welcome.

Too Many People Have Way Too Much Money

Icelandic business is thriving, and Icelandic businessmen are buying companies, football teams, supermarket chains etc. all over the place. There is a new breed of very wealthy people out here, who are not particularly bothered by the fact that, e.g., food is 65% more expensive than the European average here.

I just heard that the director of Samskip, one of the local new rich man, has just turned 50. For his birthday, he had Elton John sing for his guests. Cost: over 100 million ISK (about 1,110,789 euros)! This is one sixth of the annual budget of the Icelandic research council. I estimate that, with that money, I could hire at least 11 visiting professors for a year, changing the face of my department.

Life is not fair.

Lack of Funding for Italian Researchers Logic

Not so long ago, I reported with pleasure on a success story for Italian research in logic. Unfortunately, it looks like it is now time for bad news regarding research in logic in Italy.

Over the last few days, I have been reading a sequence of messages posted on the mailing list of the Italian Association for Logic and its Applications (AILA) related to the results of the applications for PRIN projects. (I think that PRIN is an Italian acronym standing for "Projects of National Interest".) The list of PRIN projects funded in the subject area of mathematics and computer science is here. A quick browse through the list gives me the impression that not enough of the funded projects are from computer science. Moreover, the only funded project related to logic in computer science is

OMODEO Eugenio

Università degli Studi di TRIESTE

22.680

Sviluppo su grande scala di dimostrazioni certificate

(Large scale development of certified proofs. Amount: 22.680 euros.)

One can also make the case that the project

DEGANO Pierpaolo

Università degli Studi di PISA

94.500

Sistemi e calcoli di ispirazione biologica e loro applicazioni -- BISCA

impacts on logic in computer science, broadly construed. (By the way, well done Pierpaolo!)

Funding for projects in mathematical logic and its relationships to computer science is conspicuously absent, despite the strength of Italian researchers in this area. Albeit the lack of funding will have very negative consequences on logic research in Italy, this is not the only thing that is bothering Italian logicians. From what I gather, all of the projects proposals from logicians received the same one-line evaluation, namely interesting, but marginal, as well as the same numerical score.

I do not know who the reviewers of the projects were, and I know nothing about the quality of the submitted projects. However, I feel that I have to take a firm and public stance against this uniform, general and vague "scientific" evaluation for 50-page long proposals. Would any of us be happy to write a long paper and have it rejected with a one-liner? And can logic research be at all labelled as being marginal?

Logic is the calculus of computer science! Apart from its intrinsic scientific and cultural interest, this fact alone shows that logic research is by no means marginal. In fact, thanks to its close connections with computer science, logic is the most applied branch of mathematics! (This is not just the opinion of your truly. I invite Italian readers --- assuming they exist, of course :-) --- to check out pages 108-109 of the interview with Enrico Giusti in the excellent book Professione Matematico. Note that Giusti is not a logician.)

I hope that the Italian mathematical community does not consider logic a marginal subject, and that, in the future, the evaluation of project proposals will involve expert reviewers from abroad, as it is done essentially everywhere else. This will be a great step forward towards the use of proper peer review in the distribution of the funding available for scientific research, and will increase the transparency of the whole process.

A Flurry of Prizes in Maths

It is prize time in the mathematical world. The Wolf Foundation has announced that Harry Furstenberg (Hebrew University of Jerusalem) and Stephen Smale (University of California, Berkeley) will share the US$100,000 2006-7 Wolf Prize in Mathematics.

The AMS has instead awarded its prizes for 2007. Once more the AMS-MAA-SIAM Morgan Prize for Outstanding Research by an Undergraduate Student went to an MIT student, Daniel Kane. It is humbling experience to see that this BSc student has already about 16 papers under his belt :-(

The February 2007 issue of the Notices is out. It features an interview with Lennart Carleson coauthored by my former Aalborg colleague Martin Raussen, and a beautiful book review Symmetry and the Monster: One of the Greatest Quests of Mathematics--A Book Review by Robert Griess. I liked it so much that I could not resist buying the book today. I might report on the book when I read it.

Three Billion Down the Drain?

Last Thursday the Icelandic Minister of Education and the rector of the University of Iceland unveiled a , previously very much secretive, plan aimed at bringing the University of Iceland amongst the top 100 best universities in the world. (Yes, you read that right!)

The heart of the plan is an increase in governmental funding to the University of Iceland amounting to 640 million ISK a year over the next five years (roughly 7 million euro a year). It is not completely clear to me yet what milestones the University of Iceland will have to meet to justify this investment of tax payers money. What is, however, abundantly clear is that the main competitor of the university I am working for right now (Reykjavík University) is much more powerful now than it was only four days ago, provided they will make good use of the extra funding. If previous events are anything to go by, this is very unlikely to happen in computer science unless the CS department at the University of Iceland is forced to hire according to the qualifications of the applicants.

Iceland being what it is, even your truly decided to enter the political arena for a few minutes by writing the following email message:

Subject: Financing Universities and Research


Dear Minister of Education,

It is an excellent idea to increase the level of funding for universities and research in Iceland. It is also a positive step to have some form of financing that is not linked to specific, and often narrow, project work. This is done in many other countries with great benefit to the level and quality of research. It is, however, very unclear at best that donating a large sum of money to HI the way the Ministry did yesterday is the best way to promote international quality research in Iceland.

Financial support should go to those individual researchers, research centres and laboratories where high quality academic research has been performed consistently, irrespective of the university where they are located. Allocation of resources should be made based on merit, as established by fair and objective peer review. Centuries of scientific work have shown that this is the best, if not the only, way to ensure that whatever support is available be used in the best possible way.

By way of analogy, I invite you to consider the choice of an investment fund where to invest some of your savings. Before choosing one, you would most likely examine the interests that specific funds have guaranteed their customers over the last few years. Why are political decisions on how to invest in research not based on the same principles?

Sincerely Yours,

Luca Aceto

Do I expect to receive any answer? Certainly not, but, as present head of the CS department at Reykjavík University, I felt like I had to write to the Minister on behalf of my colleagues.

I'll write a post with my first views on the HoD job over the next few days. Not surprisingly, the executive summary will be that the job is a huge time sink :-(

Concurrency Column for February 2007

Earlier this week, I posted the concurrency column for the February issue of the Bulletin of the EATCS. This column will be devoted to a paper entitled Characteristic Formulae: From Automata to Logic co-authored by Anna Ingolfsdottir and me.

The piece is loosely based on three posts I wrote for this blog. (Parts 1, 2 and 3.) This is the first time that I use this blog as a a sort of scratchpad while planning the writing of a paper. I think that I'll experiment with this use of the blog again in the future---assuming that I have anything at all to write about, that is.

Quality of Life of Researchers in Italy

Not so long ago, I wrote a post on research in Italy. In that post, I criticized the lack of sensibility of Italian politicians towards science and basic research, and praised Italian researchers for being very active in my field and in TCS as a whole despite the lack of support they are faced with.

I just read an article in La Repubblica that adds fuel to the fire. (The article is in Italian.) According to a report commissioned by the trade union Nidil Cgil, Italian researchers earn on average between 800 and 1.200 euro per month before taxes. Moreover 31% of the people interviewed by the report writers earns less than 800 euro per month after taxes. It is not surprising to read that those who do not have permanent positions yet are not optimistic about their futures. About 25% of the people who do not have a permanent position are over 35 years old, and half of those are over 40. (At this age, in most other countries other you have a tenured position of some sort or you have found a different type of job altogether.) This uncertainty about the future has obvious repercussions on the quality of life, and on family planning. It turns out that 82% of the interviewees do not have children.

How can this be at all good for my own country? And why doesn't Italian society see that it is undermining its own future by not supporting the researchers who work in Italy? Can Italy ever attract foreign researchers by offering those wages? Of course, money is not everything, but it does help, and is necessary to lead a decent life. Surprise, surprise: researchers are fully fledged human beings, with human needs and desires!

Post Scriptum: The article I am refererring to also has statistics regarding the long working hours of researchers. I chose not to focus on those statistics at all here because, in my modest experience, this is the norm, rather than the exception, throughout. My present dean often tells me that "academic freedom is not the freedom of doing nothing", to which I always reply that academics have often much longer working hours than many other people.

Back to the Future

The new year is three days old, I have been head of department for two, and I have been thinking about doing a 2006 rewind, following the tradition of The Wire, one of my favourite music magazines despite the fact that I stopped subscribing to it last summer after about 15 years. However, the more I thought about it, the less I felt I had anything meaningful to say about concurrency theory in 2006. My colleagues produced several excellent papers, and a look at the proceedings of conferences like CONCUR 2006, FSTTCS 2006, ICALP 2006, and LICS 2006 will suffice to get an idea of some of the best work done last year.

Others have done a great "2006 rewind" for complexity theory and mathematics. (From the latter blog, I encourage you to read the opinions on category theory. Savour John Baez's one liner `I hope most mathematicians continue to fear and despise category theory, so I can continue to maintain a certain advantage over them.')

I encourage all of us to learn from Lance Fortnow's advice on how to deliver a job talk. That piece of advice, and the comments to the post, apply to any talk, not just our job talks.

Finally, I hope that during this year I'll follow the following piece of advice from Allan Bay, an Italian cook and food writer, whose sixth piece of advice in Cuochi Si Diventa (one of my favourite cookbooks) reads:

Cook with calm; haste and anxiety are your worst advisors. If you know you have little time, opt for a quick recipe, one that you can cook as well as you can in the little time you have at your disposal. This virtue is useful well beyond your kitchen....

Indeed, haste and anxiety are usually not conducive to good research work either. (The advice we give others is the advice we ourselves need.)

Hopefully 2007 will be a great year for concurrency theory, ICE-TCS, all of my collaborators and friends, and, why not, a decently productive one for me too. I wish that I could begin by attending this talk :-)

Christmas Reading

Science magazine has chosen Perelman's proof of the Poincare Conjecture as breakthrough of the year for 2006. See this article by Dana Mackenzie. You can also read about the nine runners-up as well as the scientific fraud of the year.

The January 2007 issue of Scientific American features an article by Bill Gates entitled A Robot in Every Home.

Happy reading and merry Christmas.

Sussex in 1987

Julian Rathke is moving from Brighton to Southampton, where he joins Vladimiro Sassone (another former member of the School of Informatics at the University of Sussex). It does not take magical powers to foresee that Southampton will soon have a very strong theory group.

Julian tells me that it is a strange time at Sussex. Half of the department is moving buildings, so the department office and all of the secretaries are gone, the good old debugging room (the unofficial coffee room of the department at a time when the university regulations essentially did not allow for such rooms, hence the name) is also no more. Just an empty shell of a room now. Very sad.

Reading Julian's description prompted me to look back to a windy September-October 1987, when I arrived in Brighton to work for a year as a research assistant under Matthew Hennessy. The department of computer science was very small then. Yet, there was already a tightly knit group of theory people that created a very good atmosphere for intellectual growth. At that time, Marek Bedcnarzyk was putting the final touches to his PhD thesis, and Allen Stoughton was finalizing his monograph on fully abstract models of programming languages. Mark Millington, one of Matthew's former Edinburgh students, was there teaching Software Engineering. (It is a pity that Mark's PhD thesis is not very well known. It was a good piece of work.) I shared an office with Rance Cleaveland, a freshly minted PhD from Cornell, where he had formalized theories of processes using NuPRL. (Rance was working on the development of the Concurrency Workbench, but did a lot more than that---not least, he taught me a lot over beers at our local pub :-)) Across the fire doors leading to the Mathematics department, Andy Pitts was spending some time at Sussex, supported by a grant from the Royal Society.
Already the year after, the theory group grew substantially in size, with the arrival of PhD students from Britain and from abroad, postdocs, and later new members of staff. The rest, as they say, is history. It is a pity that not so much is left of that theory group at Sussex. (The linchpin, Matthew Hennessy, is still there, but many people have come and gone in the meantime.)


This is one of the pros and cons of academic life. One travels from place to place, possibly grows attached to each of the departments/centres one works for, and the colleagues one meets there, but eventually we all leave for somewhere else.

Good luck to Julian for his new job at Southampton, and congratulations to Vladi for having enticed an excellent collaborator like Julian to join his new department.

Being Head of Department: A New Experience

As of 1 January 2007, and for at least about eight months, I'll be the acting head of the CS department at Reykjavík University.

Not surprisingly, I am trying to gather some useful advice on how to survive this new experience, and hopefully live to tell the tale as far as research, teaching and service to the academic community are concerned. So far, I have found some useful information on the CRA web site, but I'd love to hear any advice you might have on how to manage one's time while being head of department, and what aspects of the job one should be particularly aware of. Drop me a line, or use the comments section. I'll be grateful for any piece of information you might provide.

I apologize to those of you who kindly invited me to serve on PCs for conferences during the first half of 2007. I was honoured by your consideration, but decided to politely decline all of those invitations rather than do a bad job. (I must freely admit that the prospect of chairing the department is worrying me somewhat :-() I hope that I made the right choice.

Research in Italy

Yesterday I travelled back to Reykjavík after a very short visit to Italy. During the trip back to the North Atlantic, I was reading La Repubblica, an Italian newspaper. One of the news items that caught my eye dealt with the protests by the rectors of Italian universities, who are very unhappy about the cuts to their institutions' budgets that are part of the latest financial law passed by the Italian government.

I am afraid that I do not know enough about the developments to express an informed opinion about the whole thing. However, I have always sternly refused to buy the argument that, unlike other countries, Italy does not have the cash to support universities and research. How can a member state of the G8 elite be short of money to support its future? Let's not mask lack of interest in science and technology as supposed poverty. By way of example, BRICS and the other research centres of the Danish National Research Foundation were richly funded for five-year periods (14 years for BRICS) with the interests resulting from the privatization of an insurance company! The outcome for Danish science is for everybody to see.

Why shouldn't the same type of investment in basic research be possible in a country like Italy? The reasons must be the same that prevent Italy from investing in its schools and universities. Three figures in the article I was reading yesterday paint an amazingly bleak picture. Italy boasts only about 3 researchers every 1000 workers. This is less than each of the other countries mentioned in the list. We (Italians) spend only about 1.2% of the GNP in research. Only Greece, Spain and Portugal invest less. Last but not least, Italy spends only 8000$ a year per university student. This is the same as Hungary, and half of what Sweden spends. Why are we Italians so masochistic?

Still, if I look at Italian research in TCS, I can only classify it as being very strong, despite the lack of money for research and the sub-optimal support. Yes, I know that I am biased. Even though I have never worked in an Italian university myself, I try to maintain good ties with my colleagues based in Italy. It is, however, an incontrovertible fact that there are many very active and very strong Italian TCS researchers. The strongest Italian CS departments are high class, and Italy exports talent. Off the top of my head, I could come up with the following list of Italian TCS researchers working abroad (with apologies to those whose names have not crossed my mind right now):

1. Luca de Alfaro
   
2. Roberto Amadio
   
3. Antonio Bucciarelli
   
4. Cristiano Calcagno
   
5. Luca Cardelli
6. Ilaria Castellani
   
7. Giuseppe Castagna
   
8. Roberto Di Cosmo
   
9. Luigi Liquori (who is from Pescara like me)
10. Giuseppe Longo
11. Sergio Maffeis
    
12. Pasquale Malacaria
    
13. Silvio Micali
    
14. Catuscia Palamidessi
    
15. Luigi Santocanale
16. Vladimiro Sassone
    
17. Luca Trevisan
    
18. Daniele Varacca
19. Luca Viganò
    
20. Francesco Zappa Nardelli
    

(Notice how many of these researchers work in France, and how many of them are located in Paris!) I believe that the above people would be considered as forming a very strong theory group anywhere in the world, and there are many more strong TCS researchers in Italy itself. I can only encourage the Italian political establishment and Italian universities to give Italian researchers a suitable environment for producing the best research they can. To my mind, this would be a win-win situation for Italy as a whole. Unfortunately for Italian science, it looks like Italy's politicians disagree with me.

Addendum 19/12/2006: Yesterday I read an article by Princeton philosopher Peter Singer, on the subject of philantropy, poverty and ethics. (Thanks to Luca Trevisan for his post on this very interesting article, which is a must read during the crazy Christmas period.)

The following excerpt from that article struck me as being very relevant to this disjointed post of mine:

The Nobel Prize-winning economist and social scientist Herbert Simon estimated that “social capital” is responsible for at least 90 percent of what people earn in wealthy societies like those of the United States or northwestern Europe. By social capital Simon meant not only natural resources but, more important, the technology and organizational skills in the community, and the presence of good government. These are the foundation on which the rich can begin their work.

If instead of wealth, we consider "intellectual output", how much would Italian researchers produce in the presence of better technology and organizational skills in the community, and in the presence of good government? What if they could devote more of their time to not fighting against the system?

Zeilberger's 76th Opinion

Dr. Z strikes again. Read his 76th opinion, entitled Why P Does Not Equal NP and Why Humans Will Never Prove It by Themselves, and form your own counter-opinion. As usual, reading Zeilberger's opinion won't leave you cold.

Zeilberger writes:

All the problems in, say, Garey and Johnson, are essentially one problem, since they are all trivially equivalent.

Well, I am not sure that I agree that those problems are "trivially" equivalent. "Triviality" is in the eye of the beholder, and maybe one has to be a top notch mathematician like Zeilberger in order to find all of the reductions between NP-complete problems trivial. I admit that I do not find most of them to be trivial at all.

I also find the characterization of the work of complexity theorists as "just proving yet-another reduction theorem" somewhat restrictive.

I am expecting to see some comments on this opinion on the complexity theoretic blogs.

Addendum posted on 15 December 2006: Read Luca Trevisan's thoughtful comments.

Let me also mention another statement of Zeilberger's from opinion 76:

There is no hope, as smart and "creative" as you and your cronies are, that you will be able to prove it by yourselves. Your only hope is to enlist that "simple" mechanical device, that ironically, you computer-scientists, do not use very much, not even for spell-checking!

Now that I have algebraic combinatorialists working near me, I can vouch that they use computers a fair amount in their work---possibly more than many theoretical computer scientists. However, in concurrency theory, people construct and use software tools to make models of computing devices and to analyze their behaviour algorithmically. Readers who have never used such tools might wish to play with Uppaal or HyTech to mention but two such tools.

Accepted Papers for FOSSACS 2007

The list of accepted papers for FOSSACS 2007 is now available. (Thanks to Jun Pang for the pointer.) The conference looks interesting, and I hope to report on some of the papers when, if ever, I have time to read them.

Accepted Papers at ETAPS 2007

The list of accepted papers for TACAS 2007 is out, and so is the one for ESOP 2007. TACAS accepted as many as 54 papers, and the list of contributors looks very impressive. Several papers have an all-star list of authors, e.g.,

Multi-Objective Model Checking of Markov Decision Processes by Kousha Etessami, Marta Kwiatkowska, Moshe Y. Vardi, and Mihalis Yannakakis.

ESOP features a list of accepted papers that is definitely of interest to concurrency theorists.

Most accepted papers at TACAS and ESOP have at least three authors, further confirming the trend to higher and higher degrees of collaboration in most fields of TCS.

Happy browsing! I am still awaiting the list of accepted papers for FOSSACS 2007. In any event, the tenth anniversary edition of ETAPS looks already like a conference one should attend. I myself, however, will be attending a marriage of mathematicians that will be held in Chicago at around that time.

RIP (Research In Peace)

The Institut Mittag-Leffler has just celebrated its ninetieth birthday. It is a Nordic research institute for mathematics, under the auspices of the Royal Swedish Academy of Sciences, created by Gösta and Signe Mittag-Leffler who donated their house, library and fortune to the Academy. The Institute runs year-long research programs in specialized areas of mathematics, and I am told that it is a great place to visit.

One of their programmes is called RIP (Research in Peace). This is a programme allowing mathematicians from Scandinavian universities, who are not directly connected to the current scientific programme, to visit the Institute for shorter periods. My colleague, and frequent indirect contributor to this blog, Anders Claesson is presently visiting Mittag-Leffler using the RIP programme.

Maybe some of you will be interested in organizing a programme on some topic in TCS at that institution.

Characteristic Formulae for Timed Automata

The last installment of this series of three posts on characteristic formulae deals with characteristic formulae for behavioural equivalences over timed automata.

The first construction of a characteristic formula for timed bisimilarity over timed automata I am aware of was presented in the paper

François Laroussinie, Kim G. Larsen, and Carsten Weise. From Timed Automata to Logic - and Back. Jirí Wiedermann, Petr Hájek (Eds.): Mathematical Foundations of Computer Science 1995, 20th International Symposium, MFCS'95, Prague, Czech Republic, August 28 - September 1, 1995, Proceedings. Lecture Notes in Computer Science 969 Springer 1995, ISBN 3-540-60246-1.

In that paper, the authors propose a timed version of Hennessy-Milner logic Lnu, and show thateach timed automaton can be uniquely characterized by a single formula in that logic up to timed bisimilarity.

The construction in that paper relied on the region graph of the timed automaton, and thus produces "large" formulae. (See yesterday's post on the number of regions in a timed automaton.) In the setting of timed automata without invariants, the construction by Laroussinie, Larsen and Weise was improved upon in the paper

Luca Aceto, Anna Ingólfsdóttir, Mikkel Lykke Pedersen, and Jan Poulsen. Characteristic Formulae for Timed Automata. ITA 34(6): 565-584 (2000).

That paper offers characteristic formula constructions in the real-time logic Lnu for several behavioural relations between (states of) timed automata. The behavioural relations studied in op. cit. are timed (bi)similarity, timed ready simulation, faster-than bisimilarity and timed trace inclusion. The characteristic formulae delivered by the constructions offered in the aforementioned paper have size which is linear in that of the timed automaton they logically describe.

Finally, the paper

Luca Aceto, Patricia Bouyer, Augusto Burgueño, Kim G. Larsen. The power of reachability testing for timed automata. Theor. Comput. Sci. 300(1-3): 411-475 (2003)

uses a property language characterizing the power of reachability testing over timed automata in the context of "test automata" to provide a definition of characteristic properties with respect to a timed version of the ready simulation preorder, for nodes of τ-free, deterministic timed automata.

I am not aware of a timed counterpart of the results by Browne, Clarke and Grümberg on the characterization of bisimulation-like equivalences over Kripke structures using characteristic formulae in fragments of CTL. Is Timed CTL expressive enough to describe characteristic formulae for timed bisimilarity? This has been an item on my "to do" list for quite some time, but I have never had the guts to start working on the problem yet.

Number of Regions in a Timed Automaton

While working on the book Reactive Systems: Modelling, Specification and Verification, my co-authors and I were looking for a formula counting the number of regions in a timed automaton exactly in order to motivate the introduction of the notion of zone. Thanks to Rajeev Alur and Tom Henzinger, I now know the answer, which I report here in case anybody else is interested.

There is a characterization of the number of regions where all clocks lie between 0 and 1 in terms of Stirling numbers of the second kind in this paper (page 13 bottom).

Peter Kopke's PhD thesis available from Tom's web page at http://mtc.epfl.ch/~tah/Students/kopke.pdf also contains that characterization. The section that starts on page 164 (of the file) offers the following formula:

Regions(2n) = sum_k=1²ⁿ S_k²ⁿ k!

where Regions(2n) is the number of equivalence classes over 2n clocks each constrained to lie in the interval (0,1), and S_k²ⁿ is the number of ways of partitioning a set with 2n elements into k subsets. So Regions(2n) is exactly the number of ways of partitioning a set with 2n elements into k ordered subsets.

As the algebraic combinatorialists here at Reykjavík University know well, I am always very impressed by these counting formulae :-)

IFIP WG1.8 Workshop at CONCUR

The IFIP WG1.8 on Concurrency Theory will organize a strategic workshop at CONCUR 2007. (The workshop proposal is below.) I'll post more details on the workshop as they become available. In particular, a web page for the event will be ready by 15 January, 2007. For the moment, I am happy to inform you that Hubert Garavel has accepted to deliver one of the addresses at the event.

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


TITLE: IFIP WG 1.8 Workshop on Applying Concurrency Research in Industry (7 or 8 September 2007)

DURATION: Half a day

ORGANIZERS: Luca Aceto, Jos Baeten, Wan Fokkink, Anna Ingolfsdottir, and Uwe Nestmann (on behalf of WG1.8)

SUMMARY: This strategic workshop, held under the auspices of IFIP Working Group 1.8 on Concurrency Theory, aims at highlighting the challenges that arise in applying concurrency theory research in an industrial setting, broadly construed. Its purpose is to be a forum for the discussion of the state-of-the-art in the transfer of results from concurrency theory to industry, and for distilling the lessons to be learned from the successes and failures so far. Moreover, we shall discuss, e.g., how to increase the impact that concurrency research can have in industry, the role of software tools in this technology transfer effort, and what are possible novel industrial application areas of concurrency theory research. The ultimate goal of the meeting, and subsequent discussions, will be to establish road map(s) for the concurrency theory community, or parts thereof, in applying its research in industrial settings.

The topic of the workshop is strongly related to all of the areas of CONCUR interest. Semantics, logics, and verification techniques for concurrent systems are necessary for the development of languages and methods for use in industrial applications. Conversely, the industrial applications of methods from concurrency theory research stimulate further advances in the basic theory covered by the CONCUR conference series. Successful applications of concurrency theory in industry further highlight the fundamental scientific and technological relevance of work done within the CONCUR community.

SELECTION OF PAPERS: The workshop will consist of three-four invited presentations, followed by discussions. We might summarize the presentations and discussions in an article for the concurrency column of the Bulletin of the EATCS. The theme of the workshop could form the basis for a special issue of a journal (for instance JLAP), but such a special issue would not be necessarily based upon presentations at the workshop. There would be a separate call for contributions for that volume.

Italian Success in Logic

I have just read an email message on the mailing list of the Italian Association for Logic and its Applications (AILA). The news is that Matteo Viale has been awarded the 2006 Sacks Prize of the ASL.

Matteo Viale finished his doctorate last September at the University of Turin and the University of Paris VII (co-supervised by Alessandro Andretta and Boban Velickovic) . In his thesis, he has solved one of the major open problems in logic and set theory by showing that the proper forcing axiom (PFA) implies the singular cardinal hypothesis (SCH). The result is reported in this paper.

Congrats to Matteo!

News from EATCS

The Call for Papers of ICALP 2007 has been published. I hope you will contribute to that success of that conference by submitting the best results of your research work to it. The PC for track B looks definitely concurrency friendly.

The Call for Nominations for the 2007 Gödel Prize has been posted on the EATCS web site. The deadline for nominations is January 31, 2007.

The Call for Nominations for the 2007 EATCS Award has been published (page 13 of Bulletin issue 90). The nominations should be sent to Wolfgang Thomas by December 15, 2006. Hurry up if you do intend to nominate one of our colleagues in concurrency theory!

A Google Talk by Luis von Ahn

If you have a few spare moments, look at this very interesting talk by Luis von Ahn:
http://video.google.com/videoplay?docid=-8246463980976635143&q=google+TechTalks.
(Thanks to Anders Claesson for this pointer.)

Luis von Ahn is the winner of one of the MacArthur genius awards for 2006. I just tried his ESP game ( http://www.espgame.org/) for the first time. It is actually rather smart, in a way, and apparently some people play it a lot (even over 10 hours a day, according to von Ahn). In so doing, they help label images on the web, using all those human brain cycles devoted to game playing for a good cause.

Characteristic Formulae (continued)

In a previous post, I briefly discussed the notion of characteristic formula for a state in a labelled transition system using Hennessy-Milner logic (HML) as the underlying property specification language. In light of its beautiful connection with bisimilarity, HML and its variations are prime candidates for logics in which to express characteristic properties for bisimulation-like relations. However, there are other options.

A classic result on characteristic formulae was obtained in the paper

Browne, M. C.; Clarke, E. M.; Grümberg, O. Characterizing finite Kripke structures in propositional temporal logic. Theoret. Comput. Sci. 59 (1988), no. 1-2, pp. 115-131.

The above paper shows that for any finite Kripke structure, i.e., a labelled transition graph with an initial state, it is possible to construct a Computation Tree Logic formula uniquely characterizing that finite Kripke structure. Browne, Clarke and Grümberg call the notion of equivalence matching "logical equivalence wrt CTL" E-equivalence. Two states are said to be E-equivalent if they have the same labelling of atomic propositions, and transitions to other states preserve the E-equivalence. (Surprise, surprise! This is just bisimilarity for Kripke structures.) It turns out that, modulo E-equivalence, finite Kripke structures are characterized by CTL formulae containing the "next-time" operator. (A formula of the form X φ, read "next φ", states that φ has to hold at the next state of the computation path.)

Another characteristic formula result is presented in that paper for an equivalence between states called S-equivalence (equivalence with respect to stuttering) . Two state sequences are said to correspond if each can be partitioned into finite blocks of identically labelled states such that each state of the ith block in one sequence is E-equivalent to each state in the ith block of the other sequence. Two states are said to be S-equivalent if, for each state sequence starting at one, there is a corresponding state sequence that starts at the other.

Theorem: S-equivalence classes of states in a finite Kripke structure are completely characterized by next-time-free CTL formulae.

The absence of the next-time operator is expected in light of the inability of S-equivalence to "count" the number of steps in a stuttering sequence. S-equivalence is closely related to van Glabbeek's and Weijland's branching bisimilarity. Logical characterizations of branching bisimilarity have been offered by De Nicola and Vaandrager in the paper:

R. De Nicola and F.W. Vaandrager. Three logics for branching bisimulation. Journal of the ACM, 42(2):458-487, 1995.

Kucera and Schnoebelen have presented a refinement of the above classic theorem by Browne, Clarke and Grümberg in the paper

A. Kucera and Ph. Schnoebelen. A general approach to comparing infinite-state systems with their finite-state specifications. Theor. Comput. Sci. 358(2-3): 315-333 (2006).

In a follow-up post, I'll try to wind up this brief three-part discussion of characteristic formulae by mentioning a couple of results on characteristic formulae for timed automata.

Bulletin of the EATCS, October 2006

The October 2006 issue of the Bulletin of the EATCS is now available on line. This 90th volume of the Bulletin marks an important date in the life of this publication in that it is the first volume that is available freely on the web from the moment of its publication. This is a one year open access experiment that I hope will be continued in the future. If you have not done so already, I warmly encourage you to become a member of the EATCS, also to support the open distribution of the Bulletin.

I firmly believe that having the Bulletin open access will further increase its quality and impact, turning it into an even more useful and widely read publication than it already is. Thanks to Vladimiro Sassone for his great editorial work on the Bulletin.

This issue of the Bulletin has at least two papers of direct interest to concurrency theorists (see the concurrency column and the programming languages column). I also enjoyed reading Leonid Libkin's contribution to the logic in computer science column.

Support the Bulletin, an open access publication in theoretical computer science, by, amongst other things, becoming a member of the EATCS and publishing articles in the Bulletin. Feel free to contact me if you'd like to write a piece for the concurrency column.

Characteristic Formulae

A piece of classic concurrency theory that is perhaps not so well known as it deserves to be concerns the characterization of the equivalence class of a process p (modulo a suitable notion of behavioural equivalence) by means of a single formula F(p) in a logic. This means that, no matter what process q we consider, q is equivalent to p iff it satisfies the formula F(p). The formula F(p), when it exists, is usually referred to as the characteristic formula of p (modulo the chosen notion of equivalence). Of course, the formula F(p) is unique up to logical equivalence, and that's why we allow ourselves the liberty to talk about the characteristic formula for p.

Why is this notion interesting at all? A classic result in the theory of concurrency is the characterization theorem of bisimulation equivalence in terms of Hennessy-Milner logic (HML) due to Matthew Hennessy and Robin Milner. (See this paper.) This theorem states that two bisimilar processes satisfy the same formulae in Hennessy-Milner logic, and if the processes satisfy a technical "image finiteness condition", then they are also bisimilar when they satisfy the same formulae in the logic. This means that, for bisimilarity and HML, logical equivalence coincides with behavioural equivalence, and that whenever two processes are not equivalent, then we can always find a formula in HML that witnesses a reason why they are not. This distinguishing formula is useful for debugging purposes, and can be algorithmically constructed for finite processes. (Algorithms for computing such distinguishing formulae for strong and weak bisimilarity are implemented in tools like the Edinburgh Concurrency Workbench.)

The characterization theorem of Hennessy and Milner is, however, less useful if we are interested in using it directly to establish when two processes are behaviourally equivalent using the logic. Indeed, that theorem seems to indicate that to show that two processes are equivalent we need to check that they satisfy the same formulae expressible in the logic, and there are countably many such formulae, even modulo logical equivalence. Isn't it possible to find a single formula that characterizes the equivalence of a process p?

To the best of my knowledge, this natural question was first addressed by Susanne Graf and Joseph Sifakis in their paper

Susanne Graf and Joseph Sifakis. A modal characterization of observational congruence on finite terms of CCS. Inform. and Control, 60 (1986), no. 1-3, pp. 125--145.

In that paper, they offered a translation from recursion-free terms of Milner's CCS into formulas of a modal language representing their equivalence class with respect to observational congruence.

Can one characterize the equivalence class of an arbitrary finite process---for instance one described in the regular fragment of CCS---up to bisimilarity using HML? The answer is negative because each formula in that logic can only describe a finite fragment of the initial behaviour of a process. (The "sight" of a formula is limited by the maximum nesting of modal operators occurring in it.)

Consider, for instance, the automaton over set of labels {a,b} with only one state p and a self-loop edge labelled a. The characteristic formula for p modulo bisimulation should state the following properties, which together completely characterize the behavior of p.

1. Process p affords an a-labelled transition leading to itself (that is, to a process that is bisimilar to p).
   
2. No matter how p makes an a-labelled transition, it always ends up in a state that is bisimilar to p.
3. Process p affords only a-labelled transitions.

If we let F(p) stand for the characteristic formula for p, then we can express the above properties in HML by means of the following recursively defined formula:

F(p) = diamond(a) F(p) AND [a]F(p) AND [b] False,

where I write diamond(a) for the a-labelled may modality in HML to prevent the blogging software from interpreting the standard notation as a HTML tag :-)

The right-hand side of the above formula determines a monotonic endofunction over the collection of sets of processes. The famous Knaster-Tarski fixed-point theorem yields a complete lattice of fixed-points for that function. It turns out that the largest fixed-point is the collection of all processes that are bisimilar to p. So, we can give characteristic formulae modulo bisimulation for states of finite labelled transition systems using HML enriched with a facility for the recursive definition of formulae, where recursively defined formulae are interpreted using largest fixed-points.

I believe that this characteristic formula construction was first noticed in the relatively unknown MSc thesis

Anna Ingolfsdottir, Jens Christian Godskesen and Michael Zeeberg. Fra Hennessy-Milner Logik til CCS-Processer. Department of Computer Science, Aalborg University, 1987

The thesis, supervised by Kim G. Larsen, was unfortunately encrypted in Danish, and this is one of the reasons why it is not as well known as it deserves to be. Some of ideas and technical developments from that work then appeared in the paper

Bernhard Steffen, Anna Ingolfsdottir: Characteristic Formulae for Processes with Divergence Inf. Comput. 110(1): 149-163 (1994),

which is by now the standard reference for the development of characteristic formulae for bisimulation-like behavioural relations over finite processes.

New Rector at Reykjavík University

The new rector of Reykjavík University was suddenly announced at 15:30 today by the chairman of the Board of Directors, Bjarni Ármannsson. The new rector is another woman, Svava Grönfeldt, who was the deputy of the CEO of Actavis. (See also her brief CV at the University of Iceland, courtesy of MohammadReza Mousavi.) She is also the author of Service Leadership: The Quest for Competitive Advantage with Judith B. (Banks) Strother. (Check the price!)

I will refrain from passing judgement on this choice until I see her in action. One word about the selection process, though. One of our contacts at Columbia University wrote to us saying:

First, most established American universities would announce a Search Committee to search for a new president. The Search Committee would typically comprise members of the board of directors, faculty, and even a staff member and student. Second, once a Search Committee was in place, a formal announcement would be made, with a deadline for applications and nominations. The principal publication that most universities--American or European--use to make these announcements is The Chronicle of Higher Education and sometimes even The New York Times education employment section. The Search Committee would meet to review applications and nominations and typically will select between 7 and 10 potential candidates for initial interviews. Following that, finalists, perhaps 3 individuals, would be interviewed in-depth and even asked to write a statement of their vision for the university. The selection of a final candidate is usually a consensus process.

Whatever process they chose, it was nothing like this, and the decision was not a consensus one. I hope it was a good one, especially because Reykjavík University is at a watershed, and a clear message has to be sent out as to whether the university wants to be what the Americans call a "research university" or some kind of teaching and service institution. However, I can already say that I did not like hearing the chairman of the Board of Directors talk about the university as an "educational company". I might be old fashioned, but a university is not a firm, and has very different purposes from a company.

Fingers crossed.

Predicting the Future

Last Friday, I read this article on La Repubblica, an Italian newspaper. The article discusses the special issue of the New Scientist that marks its 50th birthday. For this special issue, the New Scientist asked about 70 "brilliant minds" (their words) to take a peek at their crystal balls, and predict what science will have brought us by the year 2056.

A few well-known scientists talk about mathematics and computing. In fact, even one of the mathematics contributions focus on computer science! Tim Gowers' prediction discusses the P versus NP problem. He writes:

There are about half a dozen problems that almost all mathematicians agree are supremely important. One that I particularly like is the "P = NP" problem. ....

This problem gets to the heart of mathematics, because mathematical research itself has the property I have described: it seems to be easier to check that a proof is correct than to discover it in the first place. Therefore, if we found a solution to the P = NP problem it would profoundly affect our understanding of mathematics, and would rank alongside the famous undecidability results of Kurt Gödel and Alan Turing.

Thanks for the further publicity Timothy!

As for Gregory Chaitin, he went on record as saying that:

In my own field, I hope the current desiccated, formal approach has died out and people are more adventurous and creative.

I cannot believe that this statement will win him many friends :-) I, for one, am overawed to live in a research world which is full of very creative people. Sure, the heights of "creativity" are the realm of a chosen few, but one should never underestimate the importance of contributing small bricks of knowledge to the scientific enterprise. If everybody just looked for the next quantum leap in a field all of the time, the result will probably be stagnation.

I'll try to get hold of a copy of that number of the New Scientist.

On a local note, I had my own personal peek at my crystal ball last October, when I forecast that the rector of Reykjavík University will be chosen as one of the candidates to run for parliament at the next Icelandic elections. It did not take special powers of predictions to come to that conclusion. I am eagerly waiting to see who the next rector will be. Above all, I hope that the new rector will be "research friendly".

Spinoza

Last September I finished reading the book Betraying Spinoza: The Renegade Jew Who Gave us Modernity by Rebecca Goldstein. Reading that book brought back memories of my high school days, when I was taking philosophy classes and my teacher---a grey-haired, fine man by the name of Angelo Giordano I remember fondly---used to tell us about Baruch Spinoza's Ethics. I also recalled that, when I was a visiting researcher at INRIA-Sophia Antipolis in 1991, Gérard Boudol once told me that the "Dutch are more Cartesian than us French". (I hope I am quoting him correctly after all these years :-))

Reading Goldstein's warm account of Spinoza's philosophy and of his social and intellectual environment made me think that Spinoza's thought really has had a deep influence on the Dutch way of thinking (whatever that may be), and might indeed be one of the sources of the rationality that inbues Dutch society.

As Spinoza hints at in his writings, for every fact that is true, there is a reason why it is true. Since there are no arbitrary aspects of reality, logic itself must explain the world. In fact, logic itself is the world, which is just the collection of logical implications that make Nature.

Spinoza wrote:

"Thus in life it is before all things useful to perfect the understanding, or reason, as far as we can, and in this alone man's highest happiness, or blessedness, consists...."

I do not know whether I feel like endorsing Spinoza's vision completely, but I certainly feel that the intellectual process of beholding his vision of the world is an enriching one.

The closing words of Goldstein's book are a fitting climax to a well-written volume that I recommend heartily:

"The world has been transformed (though not enough) by a long and complicated chain of causes and effects that reaches back to Spinoza's choice to think out the world for himself."

I cannot help but feeling that the exercise of "thinking our way toward radical objectivity" would be a useful exercise for many of our leaders today.

You can also listen to a podcast interview with Rebecca Goldstein on the Nextbook website. Enjoy.

You might also wish to check out Rebecca Goldstein's other books. In particular, the novel The Mind-Body Problem is a favourite of mine. Readers of this blog will also enjoy the well-written, but at times somewhat flawed, Incompleteness: The Proof and Paradox of Kurt Gödel.

The Number of Labelled Trees over n Nodes

Yesterday, my colleague Anders Claesson, from the combinatorics group at Reykjavík University, gave a very good talk at the Icelandic Mathematical Society entitled "The Art of Bijective Proofs and the Science of Generating Functions". During the talk, Anders used as a running example a theorem of Cayley's to the effect that the number of labelled trees over n nodes is n^n-2.

Anders presented a bijective proof of this counting result due to André Joyal. (Concurrency theory buffs will recall that Joyal, together with Mogens Nielsen and Glynn Winskel, was one of the authors of the famous paper Bisimulations from Open Maps. Anders tells me that Joyal is also the father of the theory of combinatorial species.)

The proof is truly beautiful, and establishes a bijection between doubly rooted trees over {1,...,n}, and functional digraphs over that set. (A digraph is functional if the out-degree of each of its nodes is 1.) I encourage all of you to have a look at it.

Anders then showed how to obtain a proof of Cayley's theorem using the very general machinery of generating functions. (See this freely available book.) I must admit that I find the latter proof a little "magical", but this is due to my ignorance of the machinery of formal power series, generating functions and Lagrange inversion :-)

Addendum 18/11/2006: I have noticed that the classic textbook A Course in Combinatorics (2nd Edition) by J. H. van Lint and R. M. Wilson presents three different proofs of Cayley's theorem. (I think that the book offers five proofs of that result overall.)

As reading on generating functions, Anders recommends the draft book Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick even more than Herbert Wilf's book.

Advice from David Patterson

A while back, I stumbled the following advice for new CS professors by David Patterson. (In case you don't know him, David Patterson led the design and implementation of RISC I, likely the first VLSI Reduced Instruction Set Computer, and was a leader, along with Randy Katz, of the Redundant Arrays of Inexpensive Disks project (or RAID), which led to reliable storage systems from many companies. He has been chair of the CS division at Berkeley, the ACM SIG in computer architecture, and the Computing Research Association, was the former president of the ACM.)

Patterson's advice is crystallized into the following Patterson Rules for increasing productivity at work, and reducing the frustration that ensues from coming in earlier, staying later, and getting less work done.

Use startup funds/personal funds to have office at home as nice as office nice desk/chair, fast modem (>=ISDN), printer, big screen, ...

Determine time of day most creative/effective: early morning, after 6PM, ...?

Work at home alone during those time slots

Do creative work uninterrupted at most creative time

Be sure to be at school from lunch (social) and afternoon (lectures, student/colleague dropin, seminars ...)

Other pieces of advice from him include the following nuggets.

Learn to say: NO! (but in a very polite way)

always think about it overnight, ask trusted friend before you say yes
(saying no lets you say yes later)

Make daily, weekly, semester to do lists

Find ways to keep a secretary/assistant busy: travel, fill out grade forms, schedule, ...

Read email <= once a day (when less productive)

Circadian rhythms: 20 minute nap at about 3PM adds > 1 hour of productivity in evening

Travel is #1 time synch; budget it appropriately

I feel that I fare embarrassingly badly on all of these accounts, but I do make daily, weekly, semester to do lists---which have a tendency to grow, rather than shrink, as time progresses---, and I am at school essentially every day. (Can you hear the sound of the barrel being scraped?) Some of those items do not apply to me at all. (Startup funds/personal funds? Secretary? Budgeting travel?) And, as for reading email <= once a day, well probably I should give it a try, but, as a friend of mine used to say, "The spirit is strong, but the flesh is weak."

Do the Patterson rules apply to your work practices?

Workshop on Emerging Trends in Concurrency Theory

The colloquium Emerging Trends in Concurrency Theory will be held at LIX, École Polytechnique de Paris, during 13-15 of November 2006. The colloquium is organized by Catuscia Palamidessi and Frank D. Valencia, and will be held under the auspices of Working Group 1.8 on Concurrency Theory of IFIP TC1. The guest of honor will be Turing Award winner Robin Milner, who was awarded one of the prestigious Blaise Pascal International research chairs to visit LIX for the 2006-2007 academic year.

The event will have well over 10o participants, and has a programme of talks to whet anybody's appetite. I am really sorry to have to miss this event, which clashes with the exams for our courses in Reykjavík---a rather mundane reason for having to miss what will be a great event.

Fortunately, Wan (Fokkink), the co-chair of WG1.8, will be there, you will be able to discuss with him matters related to the proposal to hold a WG workshop at CONCUR 2007.

It would be great if one or more of the participants could report on the workshop using the blog. All you need to do is to email me your report(s), and I'll take care of posting them on this blog.

I, for one, would be happy to read about yet another great event I am missing.

Book off to the Publisher

Lester Burnham: Remember those Posters that said, today is the first day of the rest of your life? Well that's true with everyday except one, the day you die.

I have just posted the final manuscript of the book "Reactive Systems: Modelling, Specification and Verification", co-authored with Anna Ingolfsdottir, Kim G. Larsen and Jiri Srba, off to Cambridge University Press.

We'll maintain a web site for the book, that will be published in the spring 2007. (At the moment it is empty, sorry!) On the web site, an instructor will find suggested schedules for his/her courses, exercises that can be used to supplement those in the textbook, links to other useful teaching resources that we will make available on the web, further suggestions for student projects and electronic slides that can be used for the lectures. We'll also make available CWB and Uppaal models for all of the proposed projects. Students will have access to the solutions for the mandatory and strongly recommended exercises in the book.

For the moment, you can read the preface, and have a look at the table of contents here. Then, tell your library to buy copies in due course, make a note to buy your own copy when the book is out, and consider it for course use :-)

I must say that it really feels like "the first day of the rest of my life", hence the quote from American Beauty. Now it is time to catch up with several outstanding other projects, hoping that my co-workers will still want to work with me at this stage.

Brief News from the Math World

The December issue of the Notices of the AMS is out. It is not one of the most interesting I have seen, but it has a report on the International Congress of Mathematicians 2006 by Allyn Jackson, and a report on the 2006 Fulkerson Prize.

Terence Tao continues to collect prizes and awards. He has also landed the SASTRA Ramanujan Prize.

Anders Claesson, from the combinatorics group at Reykjavík University, has pointed out the following two math blogs to me: Mathematics under the Microscope and A Neighbourhood of Infinity. Maybe some of you might enjoy looking at them.

Bill Gasarch has a guest post on the Complexity Weblog on the topic of private information retrieval. He mentions the following papers:

An Ω(n^1/3) lower bound for bilinear group based Private Information Retrieval by Alexander Razborov and Sergey Yekhanin, FOCS 2006.

New Locally Decodable Codes and Private Information Retrieval Schemes, by Sergey Yekhanin

Apparently, the former paper models 2-Database-Private Information Retrieval via Latin Squares and then uses representation theory of finite groups to push through the lower bound. The latter uses Mersenne primes.

I have not looked at the papers, but that sounds like yet another application of very hard maths in volume A TCS.

Process Algebra on Lambda the Ultimate

MohammadReza Mousavi pointed out to me this post on Lambda the Ultimate (the programming languages weblog), which will please process calculi buffs. (Thanks Mohammad!) That post points out some, more or less recent, work on process calculi for transactions.

The references provided in that post are to the point. As Mohammad pointed out to me, relevant process algebraic work along those lines may also be found in the paper

H.M.A. van Beek. An algebraic approach to transactional processes. CS-Report 02/18, Department of Mathematics and Computing Science, Technische Universiteit Eindhoven, December 2002. Harm's Ph.D. thesis contains that report as a chapter (Chapter 8).

As far as I know, the earliest studies of "atomic transactions" within the field of process calculi were presented by Gérard Boudol and Ilaria Castellani in two papers that appeared in the late 1980s:

• Gérard Boudol, Atomic actions, in EATCS Bulletin Vol. 38 (1989), 136-144.
  [Abstract, PostScript, .ps.gz]
• Gérard Boudol and Ilaria Castellani, Concurrency and atomicity, in Theoretical Computer Science Vol. 59 (1988), 25-84.
  [Abstract]

It would be good if younger researchers rediscovered those two papers. I read them at the early stages of my "career", and I warmly recommend them.

I encourage my readers to post further reading suggestions on the topic of process calculi for atomic transactions. As Charles Stewart writes on Lambda the Ultimate, this topic will repay a closer look.