Tuesday, November 20, 2007

Acknowledging Author Contributions to Papers

Yesterday, I had a quick look at a news item published on the Italian on-line science magazine Galileo. (Warning: It's in Italian.) The news item describes work on computational biology carried out by Niko Beerenwinkel (ETH Zürich) and co-workers. The authors develop a new mathematical model for the somatic evolution of colorectal cancers and use it to derive an analytical approximation for the expected waiting time to the cancer phenotype.

This all sounds very interesting, but what caught my eye as a casual observer was the following information on page 19 of the resulting paper.

Author Contributions
K.W.K., V.E.V., and B.V. performed experiments; N.B., T.A., D.D., A.T., and M.A.N. developed the mathematical model; and N.B., T.A., D.D., B.V., and M.A.N. wrote the paper.
Have any of you ever written anything similar on any of your papers? I wonder what similar piece of text might accompany a TCS paper. Will we ever see a TCS article stating anything like the following piece of text?

X and Y proved Lemmas 1-4 and Theorem 2, Z proved Theorem 1, contributed ideas to the proof of Lemma 3 and found an error in the original proof of Theorem 1. Author W wrote the paper and was the main driving force in previous joint work that led to the development of this paper.

And what about papers that also report on implementations? I can't imagine how detailed the description of author contributions would have to be then.

I feel relieved to live in a research environment where we collaborate and mainly use alphabetical order amongst the authors---and not just because my surname is Aceto :-) I personally like to work by closely following the Hardy-Littlewood Rules for collaboration, whose spirit is very much at odds with the identification of author contributions.

Friday, November 16, 2007

A Wonderful Read On Gödel's Theorem

I recently finished reading the book Gödel's Theorem: An Incomplete Guide to its Use and Abuse by Torkel Franzén. This is a book I would recommend to all of the readers of this blog. (Not "This is a book I would recommend to all of the readers of this book", as I had written originally. Thanks to Luca Trevisan for spotting this embarrassing statement of mine. Haste generates monsters, alas :-() It is accessible yet precise, and it sets the record straight on what Gödel's theorem implies and what it does not imply. While reading it I quickly learned that, despite my previous reading of texts on Gödel's theorem, I suffered from some of the misunderstandings that Franzén discusses in his lovely book.

To quote from the overview chapter in the book:

The aim of the present addition to the literature on Gödel’s theorem is to set out the content, scope and limits of the incompleteness theorem in such a way as to allow a reader with no knowledge of formal logic to form a sober and soundly based opinion of these various arguments and reflections invoking the theorem. To this end, a number of commonly occurring such arguments and reflections will be presented, in an attempt to counteract common misconceptions and clarify the issues. The formulations of these arguments and reflections, when not attributed to any specific author, are adaptations of statements found on the net, representative of many such reflections.
I think that the book succeeds beautifully to do just that, and will repay re-reading.

Torkel Franzén also maintained the page Gödel on the net, from which the book eventually originated.

You might have noticed the use of the past tense in the previous sentence. Unfortunately, I just discovered that the author passed away in 2006. He left some books that, like this one, have received praise from many sources. I certainly enjoyed reading this book, and I am feeling tempted to open my purse and purchase a copy of this volume for my personal library.

Addendum (17 November 2007): I encourage any reader who wants to catch a glimpse of what this book is about, and of the writing style of the author, to have a look at this short article Torkel Franzén wrote for the Notices of the AMS (volume 53, number 4). Here is an example of one of the many things I personally learned from the book.

Let us say that a formal system has an arithmetical component if it is possible to interpret some of its statements as statements about the natural numbers, in such a way that the system proves some basic principles of arithmetic having to do with summation and multiplication. Given this, we can produce (using Barkley Rosser’s strengthening of Gödel’s theorem in conjunction with the proof of the Matiyasevich-Davis-Robinson-Putnam theorem about the representability of recursively enumerable sets by Diophantine equations) a particular statement of the form “The Diophantine equation p(x1 , . . . , xn ) = 0 has no solution” which is undecidable in the theory, provided it is consistent.

Franzén remarks that

....it is mathematically a very striking fact that any sufficiently strong consistent formal system is incomplete with respect to this class of statements,....

However, no famous arithmetical conjecture has been shown to be undecidable in ZFC.....From a logician's point of view, it would be immensely interesting if some famous arithmetical conjecture turned out to be undecidable in ZFC, but it seems too much to hope for.
Wikipedia has a short list of mathematical statements that are independent of ZFC on this page. You may find it interesting.

Saharon Shelah's result to the effect that the Whitehead problem is undecidable in ZFC is discussed in this paper by Eklof. Shelah has also shown that the problem is independent of ZFC+CH.

There is also an interesting post on a combinatorial problem that is independent of ZFC on the complexity blog. That post also includes several pointers to pieces that are well worth reading.

Thursday, November 15, 2007

Rejecta Mathematica

Silvio Capobianco pointed out to me a new mathematical journal, whose existence he discovered by looking at this opinion of Doron Zeilberger's. The journal is called Rejecta Mathematica, and its description reads

Rejecta Mathematica is a new, open access, online journal that publishes only papers that have been rejected from peer-reviewed journals (or conferences with comparable review standards) in the mathematical sciences.
A unique aspect of Rejecta Mathematica is that each paper will be published together with an open letter from the authors discussing the paper's original review process, disclosing any known flaws in the paper and stating the case for the paper's value to the community.

Is this a joke? This and other natural questions are discussed here. In case you wonder who the editors of this journal are, look here.

I am looking forward to seeing what papers will appear in the first volume of the journal :-)

Tuesday, November 13, 2007

My Web Page Has Moved

My directories in Aalborg are about to be closed down, so after three years I have finally needed to move my web pages to Reykjavík University. I have been loathe to do so until now because Aalborg was ensuring adequate visibility on the web to my pages. My web page used to come out as first link in a Google search for "Luca Aceto" and was one of the top hits in a Google search for "Aceto" (where I am competing with the vinegar producers :-)).

My fears have now materialized. This search does not find my RU web page on the first page, which is not good. I'll have to explain to our web administrator that if Google can't find my home page, I basically don't exist.

Luckily, however, this blog is still visible and from there one can find my home page in a rather roundabout way :-)

Monday, November 12, 2007

The Origins of Bisimulation and Coinduction

I recently finished reading the paper On the Origins of Bisimulation, Coinduction, and Fixed Points by Davide Sangiorgi.

I had the pleasure of hearing Davide give a talk on the topic of this survey paper during a workshop I co-organized in August 2005 in Bertinoro, and I had been waiting for the paper to appear in print ever since. The wait has now been vindicated by this truly excellent piece of scholarship. I suggest that any reader of this blog grabs a copy of this paper and reads it. I myself learned something new from it and enjoyed reading it immensely.

In this well-organized paper, Davide takes us on a historical journey tracing back the origins of the ideas of bisimulation and coinduction through the three fields where they emerged independently: Computer Science, Modal Logic and Set Theory. He highlights the role played by some key figures in the development of bisimulation and co-induction, but he does not forget to mention the interesting contributions of less-known players. Each section of the paper ends with a discussion of the ideas it presents and speculates on the reasons why some authors went very close to defining bisimulation, but did not take the extra step needed to discover/invent bisimilarity.

The level of scholarship in the paper is outstanding. We need to thank Davide for making the effort to find appropriate sources, to read them so carefully and to present his findings in such a well-organized survey paper.

I trust that the writing of this paper took a lot of work and I hope that our community will recognize the importance of writing articles like this one. Shouldn't journals accept historical papers of this quality? I believe they should!

Thanks again to Davide for making the effort to write this piece. I firmly believe that we should have more articles like this one and hope that this paper will enjoy a wide readership throughout the TCS community as a whole.

Friday, November 09, 2007

BEATCS Is Open Access

Vladimiro Sassone, the editor in chief of the Bulletin of the EATCS, has posted the appended message on several theory-related mailing lists. I hope that my readers will enjoy reading the Bulletin and will feel enticed to contribute to it by sending in survey articles for its columns, technical articles, conference and workshop reports, position papers, puzzles, obituaries etc.

I have always been a staunch supporter of an open-access Bulletin. A professional society like the EATCS must suppport the TCS research community in all possible ways. Having an open-access publication like the Bulletin is one of the contributions that the EATCS can have. Compare with SIGACT News, whose access is restricted to SIGACT members. Is this the best way to serve the TCS community?

I also believe that an open-access Bulletin of the EATCS will entice more colleagues to contribute to the Bulletin since their contributions will stand a better chance to be read and appreciated by anyone within the TCS community. This will also increase the quality of the contributions.

Support the EATCS and the open-access Bulletin by becoming a member of the EATCS! Becoming a member is easy, and only costs € 30 for a period of one year. (In fact, it is only 25 € if you are also member of SIGACT.)
To quote from the classic Nike ad, "Just do it"


Dear Colleagues,

Since 2003 all issues of the Bulletin of the EATCS, the European
Association for Theoretical Computer Science, have been produced
entirely electronically and made available on the web for members only.

The EATCS is now piloting the idea of Open Access for the Bulletin,
in the spirit of best serving its research community. So, until
further notice the volumes from no 79 onwards of the Bulletin of the
EATCS will be available from


With best regards (and apologies for cross-posting)

Friday, November 02, 2007

Joining Our "User Group"

In case you are using the book Reactive Systems: Modelling, Specification and Verification for one of your courses, I'd love to hear from you! I'll then mention your course on the list of classes that use the book and you'll be informed once we make supplementary material available on the book's website (or via other channels).

I look forward to hearing from you.

Thursday, November 01, 2007

Submissions for ICALP 2008 Now Open

The submission page for ICALP 2008 is up. See here. (The submission site for track C will be available soon.) Be sure to submit your best paper to the conference!

The deadline for workshop proposals passed yesterday, and I can already say that we will be able to offer a very varied and large selection of workshops. Watch this space and be the first to know which workshops will be co-located with the conference :-)