Tuesday, February 08, 2011

One week to the ICALP deadline

This is to remind any interested reader that the  deadline for submissions to ICALP 2011 is Tuesday, 15 February. The submission server will close at 23:59 CET. The deadline is strict.

See here for information on how to submit.

If you plan to submit to ICALP 2011, as my fellow PC chairs, the organizers and I hope, bear in mind that
  1. you are invited to submit an extended abstract of no more than 12 pages in LNCS style;
  2. material other than the abstract, references and the first 12 pages may be considered as supplementary and will be read at the committee's discretion.
If you are submitting to track B, I encourage you to place all supplementary material in a clearly marked appendix. As usual, the 12-page extended abstract should really speak for itself.

We look forward to receiving your best papers!

Sunday, February 06, 2011

Logic and Computer Science: A Piece for Reykjavik University's Magazine

The following piece will appear in the 2011 issue of Reykjavik University's magazine. I am posting it here in case it may be of interest/use to any of the readers of this blog.

Athens, 330 BC

Dear Plato,

I am writing to you because, as my former mentor and teacher, you will no doubt rejoice at the success of some of the ideas of one of your pupils. I have to warn you that what I am about to recount is a dream I had last night, and may be construed as wishful thinking on my part. However, the dream was so vivid that I believe that what happened in it will come to pass, even though this will take well over 2000 years.

Last night, I had a dream that took me to a year the people around me referred to as 2011 AD. I was standing in front of a large building located in a land that our explorer Pytheas calls Thule. Don't ask me why, but I knew that the building I entered through doors that opened by themselves was a descendant of your Academy and of my Lyceum. Young men and women were obviously there to learn in large numbers. This heritage is already something the two of us should be proud of, but it is not what I wanted to tell you most.

As you know, I consider the development of logic one of my main contributions to human knowledge. I was always a bit miffed by the fact that many people consider logic a very abstract subject with no applications. In my heart, I always felt that logic ought to be the foundation of science, be it basic or applied. I now know that my beliefs will be vindicated within 2300 years and in spectacular fashion.

I know that you will find it hard to believe, but in 2011 humankind will have at its disposal a machine like no other. It is an object they call "computer", which, unlike any other man-made machine, can be told to do many different things by feeding it with appropriate instructions. In 2011, computers will be everywhere. I saw many with my very eyes, but most of them will also be embedded in physical devices, and are therefore invisible to their users. By 2011, this population of "effectively invisible" computers will be in the fabric of our homes, shops, vehicles, farms and some even in our bodies! They will help humankind command, control, communicate, do business, travel and entertain themselves. And you know what? All of this will have to do with logic!

This truly wonderful machine, the computer, will be an engine of logic. Logic, my beloved creation, will be used to construct computers and to breathe life into them. I was told by people in what they call the "School of Computer Science at Reykjavik University" that the design of such a complex machine is only possible because George Boole (a follower of our ideas) invented a simple logic, now called Boolean logic, which deals with the truth and falsity of simple propositions and is the basis of modern digital computer design. Moreover, the languages that future humans will use to communicate with those machines, which they call "programming languages", are themselves special kinds of logical systems. Programming computers will make
logic come alive.

You will no doubt remember my famous syllogism:

All men are mortal.
Socrates is a man.
Therefore Socrates is mortal.

Today, people that call themselves "computer scientists" view syllogisms like the one above as basic steps of computation, which computers carry out at amazing speed and that take place while the computers are doing their job. But this is not all. You might recall that some of my lesser known work dealt with what I called "temporal logic". In a temporal logic, we can express statements like "I am always hungry", or "I will eventually be thirsty", or "I will be hungry until I eat a peach". Well, in 2011 people at this institution of learning in the Thule, like many others throughout the world, will be using this creation of mine to describe properties that computer systems must exhibit, such as "the computer system will never stop working." Another creation of mine, modal logic, lies at the heart of applications of logic to reasoning about possible and necessary behaviour of computing agents. Moreover, computers can be instructed to check whether other computer systems have properties that can be expressed using temporal logic!

There is a lot more I could tell you, but I do not want to bore you more with the contents of this dream of mine. Indeed, I am sure that you will have already realized why this dream has made me proud. In fact, I hope that soon I will have a dream showing me the development of this science in 2050. Even in 2011, computer science will be a young field and its marriage with logic is bound to produce amazing changes to human life and to science as a whole. Indeed, during my visit to that university, I was told that Donald Knuth, a famous computer scientist, said that: "Science is what we understand well enough to explain to a computer. Art is everything else we do." So, science is everything that can be expressed in terms of logic, and in particular the living logic that runs in computers!

Before waking up, I had a glimpse at something they call a "movie", where talking images resembling real life are projected on a screen. In fact, in 2011, computers will also be used to great effect to make movies, games and many other forms of entertainment. I wonder what our playwrights would be able to achieve, if they had access to such a technology.

The movie I watched was entitled "Twins". I did not find it good, but in it an actor by the name of Arnold Schwarzenegger utters the following memorable sentence while talking to a thug: "You have no respect for logic. I have no respect for people who have no respect for logic." He then proceeds to beat up the thug, an act that I abhor. But at that point I woke up, knowing that in 2011 logic will be the most applied branch of mathematics. All this, thanks to the young damsel called computer science.

I hope you are resting well in the world of ideas.

Your former pupil,


Tuesday, February 01, 2011

Writing papers the hard way

For readers who do not speak Italian, the text roughly reads "Inventing the wheel hasn't been too hard....it´s writing the paper that is back-breaking!"