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.