Friday, April 29, 2011

Quick reflections on ICALP 2011 (track B), part II: Conferences and long papers

During the review process for ICALP track B, a colleague wrote to me saying that he was planning to submit a paper longer than 70 pages to the conference, but eventually decided not to do so. While he was considering submitting the paper, this colleague was naturally wondering about the implications of submitting such a long paper to a conference with a 12-page limit on submissions. This academic told me that he thought that it would not be unreasonable to reject a very long paper submitted to ICALP  without even reading it. Such a decision could be backed up by a notification notice stating that "the paper is unverifiable given the available time and resources" or even "considering the paper is pointless since only 12 pages will be published."

I can understand very well why this colleague decided not to submit the paper to ICALP. Shrinking a 70+-page paper to 12 pages is a major effort, and one has to wonder whether a conference is the right outlet for such a lengthy piece of work. Indeed, one may argue that our conference publication structure does not lend itself to the publication of (very) long papers. However, I know of at least three exceptions (listed here in chronological order).
  1. The ICALP 1990 paper in which Daniel Krob presented his equational axiomatizations of equality of regular expressions was 14 pages long, but the journal paper Complete Systems of B-Rational Identities (solving two problems posed by John Horton Conway in his monograph Regular Algebra and Finite Machines) that appeared in TCS in 1991 was 137 pages long. 
  2. The ICALP paper in which Sénizergues introduced the decidability of DPDA equivalence is only 10 pages long, but the journal paper is 166 pages long.
  3. The short paper by Martin Grohe at http://www2.informatik.hu-berlin.de/~grohe/pub/gro10.pdf was published in LICS 2010, but the full work takes a book that is still under development. See http://www2.informatik.hu-berlin.de/~grohe/pub/cap/index.html.
Now, one might ask what the purpose of those conference papers is. In some sense, my colleague was right in saying that they are "unverifiable" (given the length and time constraints imposed by conferences). I doubt that the conference reviewers went through all the details of the full versions of those papers, when they were available. Even a journal reviewer would probably not do so.

I guess that the answer is simply that the conference versions announce the results and "mark the territory" by saying "I did it". However, IMHO, the results only stand after the interested community has not found any serious errors in the full versions of the papers for a long time.

A separate issue is that of writing a conference paper based on a long full paper, which does justice to the main results and techniques presented by the authors in the full version in all the gory details. IMHO, conference papers reporting  on very long and technical developments are "trailers"  for the full version of the story, which is told elsewhere in all its glory. As a movie trailer, the conference paper serves the purpose of enticing potential readers to check out the full version by motivating the work, putting it in context, stating the achieved results, discussing their importance and giving a high-level sketch of the techniques and of the tools involved in the proof. (I am thinking here, for example, of the above-mentioned paper Grohe published at last year´s LICS, where he did precisely what I wrote above and, to my mind, did it well.) Of course, this is easier said than done..

Wednesday, April 27, 2011

Quick reflections on ICALP 2011 (track B): French TCS is alive and well

This is the first in what I hope will be a series of posts devoted to some reflections on ICALP 2011 track B. The executive summary is that, for what it is worth, I believe that French TCS is alive and well (at least as far as volume B TCS is concerned).

France was the country with the largest number of track B authors (42), the largest number of submitted papers (21.79) and the largest number of accepted papers (7). Easychair statistics aside, France is home to some research groups in TCS that have amazing strength in depth and breadth. To wit, consider the following three exhibits, with apologies to those that I am unable to mention explicitly here.
  • Paris Diderot (aka Paris 7). This university is home to LIAFA and PPS, two large research laboratories hosting an enormous wealth of talent. (In passing, let me mention that PPS is a kind of little Italy, with six Italians holding permanent positions.)
  • LSV at ENS Cachan.  The Laboratoire Spécification et Vérification (LSV) is the Computer Science laboratory of ENS de Cachan, and was founded in 1997. I had the pleasure of spending a month there in May 1998 as a visiting professor, but the LSV of today hosts a much larger team of researchers than it did then. The list of members is impressive. When Hubert Comon received a CNRS silver medal in 2008, he said that "I think that this is the best environment in the world to carry out research in computer science, thanks to a unique way of working and to a great scientific homogeneity." (See here, page 34, for the French original.) Of course, one can always debate this kind of statements, but it is hard to question the strength and focus of that group of academics. 
  • LaBRI in Bordeaux. This is home to figures such as Bruno Courcelle, Anca Muscholl, Géraud Sénizergues, Igor Walukiewicz  and Pascal Weil, who are all members of the Formal Methods Group, which currently has 55 members.
It seems to me that these research centres are just the tip of a strong research iceberg in TCS. May they continue this way. 

    EATCS Award 2011 to Boris (Boaz) Trakhtenbrot

    The EATCS Award for 2011 will go to Boris (Boaz) Trakhtenbrot  for "his decisive influence on the developments of algorithms, and, more generally, of computer science as a whole in many ways." You can read a scientific "autobiography" written by Boaz for an LNCS volume devoted to his 85th birthday here (requires access to LNCS). I found the piece a fascinating read.

    Congratulation to Boaz.

    Here is what the EATCS web site says:

    The EATCS Award is awarded annually to honor a scientist with widely recognized contributions to the field of theoretical computer science throughout a distinguished scientific career. The Committee, consisting of Pavlos Spirakis (Chair), Friedhelm Meyer auf der Heide  and Eugenio Moggi in charge of evaluating the nominations to the 2011 EATCS Award has come to the decision to honor Boris (Boaz) Trakhtenbrot with the EATCS Award 2011 for his decisive influence on the developments of algorithms, and, more generally, of computer science as a whole in many ways.The decision has been unanimously approved by the EATCS Council. The Award will be assigned during a ceremony that will take place in Zürich (Switzerland) during ICALP 2011 (July 4-8, 2011).

    Friday, April 15, 2011

    Best paper awards at ICALP 2011

    The best paper awards for the three tracks at ICALP 2011 will go to the following papers:

    Track A

    Track B
    • Olivier Carton, Thomas Colcombet and Gabriele Puppis. Regular Languages of Words Over Countable Linear Orderings.
    •  Martin Delacourt. Rice's theorem for mu-limit sets of cellular automata. (Best student paper)

    Track C
    • Martin Hoefer.Local Matching Dynamics in Social Networks.
    • Shiri Chechik. Fault-Tolerant Compact Routing Schemes for General Graphs. (Best student paper)
    Congratulations to all the awardees!

      Wednesday, April 13, 2011

      Accepted papers for ICALP 2011 tracks A and C

      The lists of accepted papers for ICALP 2011 tracks A and C are now available from the web site for the conference (both with and without abstracts). See here for track A and here for track C. I am no expert, but the lists of accepted papers look very impressive to me. It is also clear that blogging has a positive influence on acceptance of one's papers at ICALP track A :-) Congrats to Andrew, Bill, Lance and Scott, with apologies to other volume A bloggers I might have missed.

      Tuesday, April 12, 2011

      Source of a quote by Lazlo Babai

      I once read the following quote attributed to Lazlo Babai: "What we need are not more theorems, but more proofs." I think that I originally read it on his Wikipedia entry, but the quote is not there anymore.

      Can anyone tell me from where the quote originates, assuming my memory is not playing tricks with me? Thanks in advance!

      Accepted papers for ICALP 2011 track B

      The notifications and the reviews for ICALP 2011 were posted earlier today. I was the PC chair for track B and I freely admit that, during the electronic PC meeting,  I often felt that the job was too big for me. I owe all of my PC a great debt. I could not have mastered this PC chair job without the support of the members of the PC and without relying on their scientific judgement and professionalism. Indeed, I feel that I have learned a lot from my PC during the meeting.

      The overall quality of the submissions to ICALP 2011 track B was unbelievably high. (My co-chairs tell me a similar story for the other two tracks, and this bodes well for the future of ICALP.) I feel that I have never been involved in the PC for a conference where the threshold for acceptance was so high. I wish that we could have selected at least ten more papers, but the number of slots was limited and we had to make some very hard choices. The authors of the many good papers that we could not select have my sympathy. I have no doubt that they will publish their submissions in a top-notch conference and/or journal soon.

      There are several interesting topics for discussion that emerge from the field of submissions at this year's ICALP track B. I plan to devote a short series of posts to some of those that I have penned down during the PC meeting. However, this will have to wait until I have caught up with some of the many chores that have piled up on my desk over the last two months. For the moment, the list of accepted papers for track B is here. (See here for the list with abstracts.)

      I look forward to a very exciting meeting in Zürich in July.

      Saturday, April 09, 2011

      Student Scholarships at ICALP 2011

      If you are a student and you are planning to attend ICALP 2011, read below. 

      The EATCS (partly sponsored by MPI-INF) has provided ten 500-Euro student scholarships.  The ten scholarships will be used to support participation of students in ICALP 2011 by covering early registration and possibly some of the local expenses.

      To apply for one of these scholarships, please send an email to . The application should be sent by April 19th, 2011, and should contain a motivation for the sponsorship request, one letter of recommendation, the curriculum vitae of the applicant, together with an indication of whether the applicant is an author or co-author of one of the papers selected for the conference.

      The applications will be reviewed by the ICALP 2011 conference chairs and the PC chairs. Preference will be given to PhD students from countries where access to funds is limited who will present papers at the conference. Each applicant will receive a notification of acceptance/rejection of her/his application by email by April 30th, 2011.

      Monday, March 21, 2011

      SOS 2011: Call for Papers

      The call for papers for SOS'11 (Structural Operational Semantics 2011) is out. SOS 2011 will be held as an affiliated event of CONCUR 2011 on September 5, 2011, in Aachen, Germany. The important dates are as follows:
      • Submission of abstract: Friday 27 May 2011
      • Submission: Friday 3 June 2011
      • Notification: Friday 1 July 2011
      • Final version: Friday 15 July 2011
      • Workshop: Monday 5 September 2011
      SOS is an event that is very close to my heart, so I strongly encourage my readers to submit good papers to the workshop. Let´s start sharpening our pencils now, but not in the sense of Halmos :-)

      Friday, March 11, 2011

      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,

      Aristotle

      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!"

      Tuesday, January 18, 2011

      Faculty position in computer systems at Reykjavik University

      In order to implement its strategy in research and teaching, the School of Computer Science at Reykjavik University seeks to hire a faculty member for a new academic position in the field of computer systems, broadly construed. We are interested in an ambitious, highly-qualified academic who, apart from developing her/his research programme, is interested in working with existing faculty, and in bridging between research, in one or more of the research areas within the School, in particular artificial intelligence, software engineering and theoretical computer science (the emphasis is mine). See here for the details regarding the position.

      Friday, January 14, 2011

      Second call for papers: ICALP 2011

      The submission server for ICALP 2011 is now open. See the call for papers and the page with information on how to submit. A wonderful piece of news is that the EATCS (partly sponsored by MPI-INF) has provided ten 500-Euro student scholarships.  The ten scholarships will be used to support participation of students in ICALP 2011 by covering early registration and possibly some of the local expenses.

      I trust that you will consider submitting your best work to one of the three tracks of ICALP 2011.  (As PC chair for track B, I am, of course, very keen on seeing many strong submissions to that track of ICALP!) The deadline for submission is February 15, so now is the time to write your paper if you have not already done so.

      Tuesday, January 11, 2011

      Concurrency Column of the BEATCS for February 2011

      I have just posted the contribution to the Concurrency Column of the Bulletin of the EATCS for February 2011. It is a piece entitled Sessions, from types to programming languages by Vasco Thudichum Vasconcelos.

      I hope that the readers of the column will enjoy it.

      Feel free to contact me if you would like to contribute a piece to the Concurrency Column. 

      Friday, December 03, 2010

      Pushdown Automata and Vector Addition Systems

      Philippe Schnoebelen just sent me an email announcing the forthcoming event Pushdown Automata and Vector Addition Systems: A New Look At Two Classical Problems, which will be held at LSV in Cachan on January 20, 2011.Quoting from the web page for this one-day event:
      This special event focuses on two recent major claims/results:
      • a new proof, by P. Jančar, for the decidability of equivalence for deterministic pushdown automata, first established by G. Sénizergues, and
      • a new proof, by J. Leroux, for the decidability of accessibility in vector addition systems, or equivalently in Petri nets, first established by E. Mayr (and S. R. Kosaraju).
      Our aim here is to provide an exceptional opportunity for Jančar and Leroux to provide an in-depth presentation of their proofs in front of a large audience of expert specialists as well as younger researchers interested in the field. This will be a unique occasion for the kind of interaction and attention to details that is only possible in a 3-hour tutorial format.
      This sounds like a very interesting event. If you happen to be in Paris at around that time, do make a point of attending it. For those of us who cannot be there,  Jančar and Leroux have posted write-ups of their results here and here.

      Tuesday, November 02, 2010

      Springer's LNCS

      Over the last few days, I have been exchanging emails with the chief librarian at my university to find out how much Springer charges us for access to its LNCS proceedings series. My enquiries were prompted by some remarks from a colleague from outside Iceland who told me that her library will likely stop subscribing to LNCS starting in 2011.  

      Yesterday, my contact at our library wrote to me saying that LNCS is not part of the Icelandic National Licence to Springer journals, SpringerLINK. Our library used to buy it as a special subscription and we had a deal with Springer for a three year period. This subscription was one of the special subscriptions we had to cancel after the financial crisis. She also told me that the subscription fee for access to LNCS for the year 2009 was the "special price" of  7.566,00 EUROS. (I wonder what the standard price is.) 

      I wonder whether your library will continue subscribing to LNCS. (Do post a comment if you have any information on this!) Times are hard for everyone, or so it seems, and perhaps university libraries are becoming more selective in choosing what journals and proceedings series they subscribe to. 

      Friday, October 29, 2010

      Call for nominations for EATCS awards

      The calls for nominations for the EATCS Award, the Presburger Award and the Gödel Prize for 2011 are now out. See here for details. The deadlines are approaching fast, so get your nominations ready now!

      Wednesday, October 20, 2010

      Postdoctoral position at Reykjavik University

      Processes and Modal Logics

      School of Computer Science, Reykjavik University

      One postdoctoral position


      Applications are invited for one postdoctoral position at the School of Computer Science, Reykjavik University.  The position is part of a research project funded by the Icelandic Fund for Research, under the direction of Anna Ingolfsdottir and Luca Aceto. The general aim of the project is to contribute further advances to the study of the connections between the theory of reactive systems, modal logics and logics of knowledge, amongst others. See the web page of the project at


      for more details on the project.

      The successful candidates will benefit from, and contribute to, the research environment at the Icelandic Centre of Excellence in Theoretical Computer Science (ICE-TCS). For information about ICE-TCS and its activities, see


      Qualification requirements

      Applicants for the postdoctoral position should have a PhD degree in Computer Science, Mathematics or closely related fields. Previous knowledge of at least one of concurrency theory, modal/epistemic logics and their applications in computer science, and process calculi is highly desirable.

      Remuneration

      The wage is 330,000 ISK (roughly 2,120 euros at the present exchange rate) per month before taxes. The position is for one year, starting in January 2011 or as soon as possible thereafter, and is renewable for another year, based on good performance and mutual satisfaction.

      Application details

      Interested applicants should send their CV, including a list of publications, in PDF to the addresses below, together with a statement outlining their suitability for the project and the names of two referees.

      Anna Ingolfsdottir
      email: annai@ru.is

      Luca Aceto
      email: luca@ru.is

      We will start reviewing applications as soon as they arrive, and will continue to accept applications until the position is filled.