Vardi Receives The Blaise Pascal Medal in Computer Science For 2008

I just learned that Moshe Vardi is the recipient of the Blaise Pascal Medal in Computer Science for 2008 of the European Academy of Sciences. This is outstanding news for TCS as a whole and for the logic in computer science community in particular.

The motivation for the prize reads:

In recognition of his outstanding contributions in several areas of computer science connected by their use of logic as an underlying methodology. His work has had fundamental and lasting impact on automatic verification, logic of knowledge, database theory, and finite-model theory.

Moshe also contributes to the development of activities in TCS in my small corner of the world by sitting on the advisory board of ICE-TCS.

Congrats to Moshe! Somehow I feel that there will be more and even more prestigious awards in store for him.

Concurrency column for the October issue of the BEATCS

I just posted the instalment of the concurrency column for the October issue of the Bulletin of the EATCS. The article, entitled Formalizing operational semantic specifications in logic, has been contributed by Dale Miller.

I strongly recommend this article not only to the standard readership of the concurrency column, but also to those readers who normally focus on logic in computer science and on programming languages amongst others. By publishing it, I feel like I am killing at least three birds with a stone.

Enjoy.

TCS 2008: Take Two

I am attending the session before lunch of TCS 2008, after which I will go to Milan central station to catch a train back to Pescara, my home town.

Today's invited talks were delivered by two Italian computer scientists, Antonio Restivo and Luca Cardelli.

Over the last 35 years or so, Restivo has been one of the prime movers in the Italian community of researchers working on automata and formal language theory. In his talk, he addressed the following basic question:

What is the "right" way of extending the notion of recognizability from word languages to picture languages?

He described the approach he has developed with his co-workers, which is based on the notions of locality and projection. This notion turns out to coincide with the class of picture languages that are definable using existential monadic second-order logic. This leads Restivo to believe that it is the "right" notion of recognizable 2D language.

The notion of recognizable 2D language offers some surprises, at least for a non-expert like me. For instance, the language consisting of the square pictures over alphabet {a,b} that contain an equal number of a's and b's is recognizable, and so is the language of pictures of a's whose sides have prime length.

Luca Cardelli needs no introduction. In his talk, which was based on this paper, Luca presented a basic process-algebraic language that can be used to describe the ordinary differential equations that one meets in (bio-)chemistry. He showe several interesting applications of this language and how it can be used to investigate the discrete vs. continuous modelling dichotomy. The talk was excellent, as usual, and I am sure that the slides will appear very soon on this web page. It was great to see that a simple process calculus based on a stochastic version of Milner's CCS can be used to specify ODEs in a compositional way. For TCS people like us, the automata described by terms in the language "explain" the ODEs and why they take they form they take. Luca also showed us that his compilation of terms into ODEs produces exactly the known ODEs for some classic examples, such as the predator-prey one.

Yesterday, Tim Roughgarden gave a very interesting and beautifully delivered invited talk entitled Algorithmic Game Theory: Some Greatest Hits and Future Directions. You can read the paper here.

TCS 2008: Invited Speakers for the First Day

I am in Milan for TCS 2008, the bi-annual conference organized by IFIP TC1 in conjunction with the World Computer Congress (WCC). TCS 2008 aims at covering both volume A and volume B TCS, and this year features as many as seven 45-minute invited talks over three days. (IMHO, this is an exceptional number of invited talks for such a short conference.)

Being part of an event like the WCC, which features many events for IT professionals, makes TCS a very expensive TCS conference to attend, and the atmosphere is somewhat different from that of the typical conference TCS folks tend to attend. The early registration fee for an IFIP member was 525 euros (the late one is 680 euros for IFIP members and 800 euros for non-members), it does not include lunches and at the coffee breaks we get just coffee! Not surprisingly attendance at the conference is small and, despite the number of CS departments in Milan and surrounding areas, there are preciously few locals taking part in the event. I guess that there is a definite lesson to be learnt here.

Here I will limit myself to discussing some of the invited talks at the conference. TCS 2008 was kicked off by a presentation delivered by Grzegorz Rozenberg entitled Natural Computing. In his talk, he discussed models of computation inspired by nature and how they differ from classical computational models we use in computer science. I have not found his presentation on line, but you can read Rozenberg's views on the subject of natural computing vis-a-vis classical computer science in his acceptance speech for a honorary degree he received from the University of Bologna as well as in the many (and I really mean "many") technical papers he has written on the topic.

Rozenberg's invited talk was followed by a truly remarkable presentation by Javier Esparza. Javier was one of our invited speakers at ICALP 2008 and I already sang the praises for his presentation in Reykjavík. I really wish that more students had been there to see how to deliver an excellent talk despite a lack of slides for the first ten minutes or so because of technical problems. This was an example of how very good story-telling skills can easily overcome technological failures (at least at the beginning of a technical talk). After all, a conference speaker or a teacher are not so different from ancient story tellers, minstrels or gurus.

Javier's talk reported on results that he has obtained with his students on the solution of monotonic polynomial equations, a subject that one would expect to have been completely settled by mathematicians a long time ago, and that instead has been the source of interesting recent developments in the computer-science literature. The key point here is that one can obtain very strong results on methods for solving polynomial fixed-point equations if one restricts oneself to monotonic equations. I let you browse through Javier's slides since nothing I could write here would do justice to the many exciting results he has achieved with his students. The slide also list some interesting open problems. In particular, consider the problem

MSPE-DECISION: Given an MSPE X = f (X) with rational coefficients and k rational, decide whether the first component of the least solution of that system of monotonic polynomial equations is at most k.

The above problem is in PSPACE and unlikely to be in P. It might be solvable using a polynomial number of arithmetic operations. According to Javier, a proof of this fact would be a sensational result. Some of you might like to sharpen their pencils and try to solve this problem.

I was again pleased to be in the room to listen to yet another inspiring talk by Javier, who is rapidly becoming one of the favourite invited speakers at European TCS conferences.

I will try to report on the other invited talks I heard at some point soon.

Bereavement in Italian Theoretical Computer Science

On the night between August 19 and August 20, Italian TCS prematurely lost Stefano Varricchio (University of Rome "Tor Vergata") while he was on holiday with his family. He was 48, or so I am told.

Stefano's research was in the classic areas combinatorics on words, automata theory and formal languages. I am not qualified to offer an assessment of his research contributions, and I hope that some of my readers who work on the aforementioned topics will post comments on Varricchio's work. I met him once a few years ago during a visit to the University of L'Aquila, where he was a full professor at the time. I recall that, after my presentation based on this paper, he kindly pointed out the relevance of a famous theorem by Fine and Wilf for some of the results I presented.

Here is the theorem.

Theorem (Fine and Wilf, 1965) If a word x has periods p and q, and has length at least p + q − gcd(p, q), then x has also a period gcd(p, q).

A relative of mine and his wife, who followed Stefano's compilers course in L'Aquila, told me that he was one of the best teachers they had during their studies.

To quote a poem by Giuseppe Ungaretti,

Si sta come, d'autunno, sugli alberi, le foglie.
G. Ungaretti - Soldati Bosco di Courton luglio 1918