Process Algebra Diary

First Alan Turing Year event at Reykjavík University

2012-01-15T12:19:00.000Z

Last Thursday, I kicked off the Alan Turing Year at Reykjavik University by delivering a talk for the general public entitled Alan Turing: The Father of Computer Science (organized jointly by ICE-TCS , the School of Computer Science at Reykjavik University and the Icelandic Mathematical Society). In case anyone is interested, the audio of the talk, with the accompanying slides, is here in .avi format.

We plan to record all the talks in the series and to make them available on line here.

It is not easy to give a talk for a general audience. In enjoyed the experience, but I was mightily relieved when the talk was over :-)

The Alan Turing Year at Reykjavik University is part of the Alan Turing Year, a centenary celebration of the life and work of Alan Turing.

What is a good research environment?

2012-01-15T12:11:00.000Z

On January 27, I will be giving a ten-minute presentation at a town-hall meeting that will take place at Reykjavik University on the theme "What is a good research environment?". I roughly know what I am going to say, but I am curious to hear what would be the items on my readers' wish list when they think about a good research environment.

What do you look for in a research environment you would be happy to work in?
What are the best aspects of your current research environment?
What would you improve in your current research environment?

Two PhD fellowships at Reykjavík University in Design of Ad-Hoc Wireless Networks

2011-12-30T18:44:00.000Z

I am very happy to post the following announcement of two Ph.D. fellowships on behalf of my colleague, and work-space neighbour, Magnús M. Halldórsson. I trust that it will be of interest to some of the readers of this blog and/or their students. The project "Design of Ad-Hoc Wireless Networks", which has Magnus as PI and sees the participation of ICE-TCS members Pradipta Mitra, Eyjólfur Ásgeirsson, Henning Úlfarsson and Ymir Vigfusson, has just been awarded a three-year excellence grant by The Icelandic Research Fund.

Design of Ad-Hoc Wireless Networks

School of Computer Science, Reykjavik University

Two Ph.D. fellowships

Applications are invited for two Ph.D. fellowships at the School of Computer Science (SCS), Reykjavik University. The positions are part of a three-year research project funded by a grant-of-excellence by the Icelandic Research Fund, under the direction of Magnús M. Halldórsson.

Aim of the project

The aim of this project is to elucidate fundamental properties of wireless networks, broadly construed. Our focus is on general provable properties that hold for arbitrary configurations and are independent of situation-specific characteristics. We explore realistic models of interference, with the aim of bridging some of the gap between theoretical and applied research. We will also investigate practical protocols to disseminate information in general networks.

Some of the aspects of the projects include:

· Spectrum management, including game theory and spectrum auctions, and cognitive radio.

· Analysis of increasingly realistic models of wireless communication, including shadowing and obstacles, mobility, and network coding.

· Installation of a comprehensive wireless testbed, and the implementation of empirical confirmation studies.

· Resolution of fundamental open questions on wireless scheduling and capacity, and the design of communication primitives.

· Creating and evaluating protocols for information dissemination in combined wired and wireless networks.

· Devising practical systems and implementing applications for general networks.

The mode of operation of the project is three-pronged:

· Designing and implementing systems and kernel primitives.

· Conducting empirical studies in a wireless testbed, along with simulations studies.

· Designing and analysing algorithms with provable performance bounds.

Research environment

The research group consists of faculty members from three schools at Reykjavik University and collaborators at TU Aachen and ETH Zurich. The group includes Ýmir Vigfússon, Henning Úlfarsson and Pradipta Mitra (SCS), Eyjólfur Ásgeirsson (School of Science and Engineering) and Sverrir Ólafsson (School of Business and School of Science and Engineering). The project director is Magnús M. Halldórsson (SCS). Our primary collaborators are Berthold Vöcking (TU Aachen) and Roger Wattenhofer (ETH Zurich); we also collaborate with other world-class researchers in Europe, N-America, and Asia. The research group website is http://alnet.ru.is/sinr.html.

The successful candidates will benefit from, and contribute to, the research environment at the Icelandic Centre of Excellence in Theoretical Computer Science (ICE-TCS). ICE-TCS has currently 14 permanent members, five postdoctoral researchers and three Ph.D. students. For more information about ICE-TCS, its members and its activities, see http://www.icetcs.ru.is/.

Qualification requirements

Applicants for the Ph.D. fellowships should have a MSc degree in Computer Science, or closely related fields, and have a solid background in the analysis of algorithms and a good understanding of networking. One of the studentships is expected to be systems-oriented, for which an experience with systems design and implementation is essential. The other will be focused on algorithmic analysis, for which mathematical competence is crucial.

Remuneration

Each Ph.D position provides a stipend of 250,000 ISK (roughly 1600€[1]) per month before taxes, for three years, starting as early as possible and no later than September 2012.

Application details

By Friday, 15 February 2012, interested applicants should send their CV, including a list of publications where applicable, as a PDF document to mmh@ru.is, together with a transcript of their academic record, a 1-2 page statement outlining their suitability for the project and the names of two referees who can comment on the research potential of the candidate.

We will start reviewing applications as soon as they arrive, and will continue to accept applications until the positions are filled. However, we strongly encourage interested applicants to send in their applications as soon as possible.

About the School of Computer Science at Reykjavik University

The School of Computer Science at RU (http://en.ru.is/CS) has approximately 440 students at the undergraduate, masters and doctorate levels. The School is home to several strong research groups and the main research areas are algorithmics, artificial intelligence, combinatorics, concurrency theory, databases, human-computer interaction, natural language processing, engineering software systems, theoretical computer science and virtual environments.

The School of Computer Science at Reykjavik University has ties with several leading foreign universities, facilitating collaboration, as well as faculty and student exchanges. In particular, the School has a joint M.Sc. degree in Computer Science with the University of Camerino, Italy, and joint Ph.D. degree programs with KTH, Stockholm, Sweden, and Eindhoven University of Technology, Holland.

Information about Ph.D. studies at the School of Computer Science is available at
http://en.ru.is/departments/school-of-computer-science/ph.d-studies/

[1] Up-to-date Exchange Rate can be obtained from http://sedlabanki.is/?PageID=183

Merry Christmas, if it comes.....

2011-12-23T15:17:00.000Z

From xkcd. My daughter would not be very happy with this Zeno behaviour :-)

Accepted papers for FOSSACS 2012

2011-12-19T22:11:00.000Z

The list of accepted papers for FOSSACS 2012 is now available. The competition for the available slots was very hard, and several deserving submissions could not be selected for the conference.

On a personal note, the more I serve on PCs for competitive conferences, the more I have the feeling that the quality of the competition is increasing. The same holds true for grant applications, job applications, promotions and just about any other aspect of academic life.

News from the LICS Community

2011-11-23T13:49:00.002Z

Here is some news I just discovered by looking at the web page for LICS 2012.

Highlights and changes for LICS 2012

Starting 2012, LICS is jointly organized by ACM and IEEE, and is cosponsored by ACM SIGACT and the IEEE Computer Society's Technical Committee on Mathematical Foundations of Computing.
In response to concerns about LICS becoming overly selective with a too-narrow technical focus, the program committee will employ a merit-based selection with no a priori limit on the number of accepted papers.
LICS 2012 will continue the tradition of pre-conference tutorials that was initiated in 2011. This year, Jan Willem Klop will give a tutorial on term rewriting systems and Andre Platzer will give a tutorial on logics of dynamical systems.
Special Events and Invited Lectures: There will be an invited lecture by Robert J. Aumann, winner of the 2005 Nobel Prize in Economic Sciences, and a plenary session in honor of Alan Turing on the occasion of his centenary, with talks by Robert L. Constable, E. Allen Emerson (co-winner of 2008 A. M. Turing Award), Joan Feigenbaum, and Leonid Levin.

These are very interesting developments for the LICS community, some of which should be of interest for the TCS community as a whole.

Development A above paves the way to the formation of an ACM Special Interest Group on Logic in CS, say a SIGLOG, about which I have heard reports in private conversations with key players in the LICS community. Such a special interest group would play an important role in the development of volume B TCS research in North America.

Development B is most interesting and might be a watershed event, if it pans out. LICS plays the role of FOCS/STOC for the volume B TCS community and I believe that all of TCS will be interested in observing the outcome of the LICS 2012 experiment. Typically, the quality of an average LICS submission is very high and this new policy might encourage even more submissions to the conference than usual. How will the PC handle these submissions? Will the conference move to parallel sessions? Will this development decrease the value of the "LICS currency"? Will other conferences follow the lead of LICS, if the experiment "succeeds"?

Time will tell. In any event, this is a courageous step taken by the LICS conference and I look forward to seeing how it will affect the conference and the LICS/TCS community.

Last, but not least, items C and D above look exciting. I have heard from several sources that the tutorials at LICS 2011 were a resounding success. (See here, here and here for the slides used by Prakash Panangaden, one of my favourite speakers, in his tutorial on Semantics. Albert Atserias gave a tutorial on Finite Model Theory.)

Standards for promotions

2011-11-22T11:53:00.000Z

My department is developing its strategy for the next five years. As part of this strategy work, we are working on a "promotion strategy" and we are discussing standards for promotion to associate and full professor positions. Needless to say, there is a wide array of opinions amongst my colleagues on this point. In order to obtain a broad survey of current best practices, let me ask any reader out there:

What does it typically take to be promoted to associate and full professorships at your institution?
What role does teaching performance play in such decisions? And how is it measured?
What are the incentives to undergo a promotion process, apart from the obvious ones like tenure and possibly higher wages?

Thanks in advance!

Dr. Cimini, I presume

2011-11-22T11:31:00.000Z

Last Friday, Matteo Cimini successfully defended his PhD thesis entitled Contributions to the Meta-theory of Structural Operational Semantics. Congratulations to Dr. Cimini! I expect that his thesis will be available on line soon, but, for the moment, you can read some of the papers that form the bulk of that tome.

A PhD is not enough, however. I wish Matteo the best of luck for his future career.

EATCS ballot on the future of the publication of the ICALP proceedings

2011-10-06T09:47:00.000Z

Today, the European Association for Theoretical Computer Science started a ballot on the future of the publication of the proceedings of ICALP. This is a very important decision for the EATCS, and for the ICALP community in general. As chairman of the publication committee of the EATCS, I urge all the members of the TCS community who have a right to vote as members of the EATCS, to give this matter serious thought and exercise their right to express an opinion on whether future ICALP proceedings should be published with Springer or with LIPIcs. Note that if you attended ICALP 2011, ESA 2011 or MFCS 2011, you have the right to vote since your registration fee probably included a one-year membership of the EATCS.

Note also that the result of the ballot will only take effect if at least 25 % of the EATCS members participate. Otherwise, the proposal of the EATCS council to recommend to the EATCS membership to go along with Springer for the next four years will take effect automatically.

The ballot on the future of the publication of the ICALP proceedings, as well as all the supporting documentation, can be found here. I do hope that you will take time to consider this matter and vote as soon as possible.

Assistant Professor position in Modelling and Analysis of Concurrent Systems at IMT Lucca (deadline October 31st)

2011-10-05T10:35:00.001Z

Perhaps this announcement will be of interest to some of the readers of this blog. IMT Lucca is an exciting place and there will definitely be some competition for the position.

Addendum dated 7 October: This video issued by IMT Lucca gives an enticing introduction to that academic institution. Do have a look, if you are interested in applying for this position.

The IMT Institute for Advanced Studies Lucca invites applications for an Assistant Professor position in the areas of foundations and formal specification of concurrent (distributed, mobile, autonomic) systems; quantitative and qualitative modelling and analysis of concurrent systems and design and development of software tools to support their formal analysis; applications to socio economic systems.

IMT Lucca (http://www.imtlucca.it) is a public international Graduate School and Institute of Technology that acts as a research university with the aim of forming human capital in disciplines characterized by their high potential for concrete applications. IMT strives to reach the fusion of theoretical comprehension and practical relevance.

The Assistant Professor will be a part of the Research Unit "System Modelling and Analysis" (SysMA, http://sysma.lab.imtlucca.it/) in the Computer Science and Applications area of the Institute, and will perform research activities, tutorship and mentoring of Ph.D. students, limited teaching of graduate courses and participation in the development of the research activities of the Institute.

Appointment compensation packages will depend on the candidates and their records of accomplishment, but are competitive on an international level. Applicants must be able to teach graduate courses in English; knowledge of Italian is not required.

The deadline for application is October 31st, 2011 12:00 pm CET.

Interested candidates must apply before the deadline by filling in the online application form at http://www.imtlucca.it/faculty/positions under "Junior Faculty Recruitment Program". They will also be asked to submit a CV, a research paper (published or working) and the name and contact details of three referees.

For further information about the position, applicants can refer to

http://www.imtlucca.it/faculty/positions/junior_faculty_recruitment_program.php#modelling_concurrent_systems

or can contact either Rocco De Nicola or Sara Olson: researchers.opening@imtlucca.it.

LICS 2012 Test-of-Time Award

2011-09-18T14:51:00.001Z

The latest issue of the LICS Newsletter (dated July 29) mentioned the appended information related to the LICS 2012 Test-of-Time Award.

I strongly encourage the members of the LICS community to send their comments to Andre Scedrov (scedrov@math.upenn.edu), who chairs the award committee. As usual, the committee is faced with a very hard choice and they can do with some input from the community.

LOGIC IN COMPUTER SCIENCE (LICS) - TEST OF TIME AWARD

The LICS Test-of-Time Award recognizes a small number of papers from the LICS proceedings from 20 years prior that have best met the "test of time".
The LICS 2012 ToT Award committee consists of

Martin Grohe,
Prakash Panangaden,
Andre Scedrov (Chair), and
Ashish Tiwari.

The committee will select between 0 to 3 papers that appeared in LICS 1992 proceedings. All papers are nominated by default, but the committee welcomes input from our community: please send your comments to Andre Scedrov (scedrov@math.upenn.edu) which will be shared only among the committee members.
LICS 2012 ToT award will be presented during the business meeting at LICS 2012 to be held in Dubrovnik from June 22 to 25, 2012.
The list of papers from LICS 1992 is available at http://www2.informatik.hu-berlin.de/lics/archive/1992/index.html
The information about LICS ToT award and the list of past winners is available at http://www2.informatik.hu-berlin.de/lics/archive/test-of-time-award.html

October 2011 issue of the BEATCS Concurrency Column

2011-09-16T10:18:00.002Z

I have just submitted the material for the October 2011 issue of the BEATCS Concurrency Column. This instalment of the column consists of a double bill:

Interval Temporal Logics: a Journey by Dario Della Monica, Valentin Goranko, Angelo Montanari and Guido Sciavicco. [PDF]
Assertional and Behavioral approaches to concurrency by Uri Abraham. [PDF]

The first piece is a survey devoted to interval temporal logics. The article presents the main developments in the study of interval temporal logics over the past 10 years (a field of research to which the authors have contributed substantially) and outlines some landmark results on expressiveness and (un)decidability of the satisfiability problem for the family of interval logics. The authors give us a guided tour of this body of work, which, to my mind, deserves to be better known within the concurrency-theory community.

The second contribution is a a piece by Uri Abraham in which he compares two proofs of the mutual-exclusion property for the well known algorithm by Peterson: an assertional proof and a behavioural one. The article outlines a framework within which the behavioural approach can be formalized in a way that retains the intuitive content of the behavioural reasoning.

This is my last issue as editor of the Concurrency Column. I have been editing the column for the last eight years, and I feel that it is time to step down. The column will benefit greatly from a fresh perspective on the world of concurrency theory and I look forward to reading the pieces that will appear in future issues.I thank the contributors to the Concurrency Column over the last eight years and all my readers.

12 PhD positions in Computer Science and Engineering at IMT Lucca

2011-09-13T16:09:00.000Z

Courtesy of Rocco De Nicola, here is an exciting opportunity for excellent students, which I am happy to advertise.

The institute for advanced studies IMT Lucca (Italy) announces 12 PhD positions in Computer Science and Engineering. The deadline for applications is September 28, 2011.

IMT (http://www.imtlucca.it/) is a research institute located in Lucca (Italy); courses are taught exclusively in English.

The PhD Program (https://www.imtlucca.it/phd_programs/computer_science_engineering/) coordinated by Rocco De Nicola aims at preparing researchers and professionals with broad training in the foundations of informatics as well as in applications to a variety of cutting-edge systems and disciplines.

A number of PhD students will be selected for working within the the two newly founded Research Unit:

SysMA (http://sysma.lab.imtlucca.it/

)
lead by Rocco De Nicola doing research on concurrent (distributed, mobile, autonomic) systems modelling and analysis
and
Dysco (http://dysco.lab.imtlucca.it/)
lead by Alberto Bemporad doing research on control and optimization technologies.

In addition, students will be selected to work on topics related to medical imaging, and imaging for the life sciences
http://users.eecs.northwestern.edu/~stsaft/#Openings

We hope that you may consider applying for and/or signaling these opportunities to colleagues and collaborators.

======= DETAILS ON THE ADVERTISED POSITIONS =======
6 IMT scholarship (12.423 EUR after taxes) plus accommodation and free meals (lunch and dinner).
1 MIUR scholarship (12.423 EUR after taxes) plus free meals (lunch and dinner).
5 positions to be funded with internal projects or third-party scholarships (negotiable salary) that come with a research budget of 3.000 EUR offered by IMT and free meals (lunch and dinner).

For further information please visit
http://www.imtlucca.it/phd_programs/call_for_applications/index.php
and/or contact the sender of this mail.

PhD positions at the University of Camerino, Italy

2011-08-24T14:36:00.000Z

Emanuela Merelli has asked me to circulate the following announcement of eight PhD positions at the University of Camerino, Italy. The deadline for applications is very close, but perhaps some readers (or some of their students) might want to apply.

---------------------

We kindly remind you that the PhD call for applications at University of Camerino is still open. See

http://www.unicam.it/laureati/dottorato/call.asp

There are 8 fellowships available for the Doctoral Study Programme in Information Science and Complex Systems. See

www.cs.unicam.it/merelli/PhD-Informatica.pdf

The deadline is approaching, 26 August 2011.

2011 CNRS Silver Medal to Jean Goubault-Larrecq

2011-07-14T15:46:00.000Z

Jean Goubault-Larrecq receives the 2011 CNRS Silver Medal. The web site with the list of medal winners states that:

La Médaille d'argent du CNRS distingue un chercheur pour l'originalité, la qualité et l'importance de ses travaux, reconnus sur le plan national et international.

So, Jean is recognized for the originality, the quality and the importance of his research work. Congratulations to Jean for the award, and to LSV as a whole for yet another achievement.

The silver medal for mathematics went to François Loeser.

Accepted papers at ESA 2011 and MFCS 2011; CFP for FSTTCS

2011-06-24T11:56:00.000Z

The list of accepted papers for ESA 2011 is here. (My colleague Magnús Halldórsson was the PC chair for ESA 2011.) Ditto for MFCS 2011.

The submission deadline for FSTTCS is just two weeks away. The call for papers is here. The list of invited speakers for the event is stellar:

Susanne Albers (Humboldt-Universität zu Berlin, Germany)
Phokion G. Kolaitis (Univ. of California, Santa Cruz, USA)
John C. Mitchell (Stanford University, USA)
Madhu Sudan (currently at Microsoft Research New England, and on leave from MIT, USA )
Moshe Vardi (Rice University, USA)
Umesh V. Vazirani (Univ. of California, Berkeley, USA)

Do submit!

LICS 2011 Test-of-Time Award

2011-06-23T09:56:00.000Z

The LICS 2011 Test-of-Time award was given yesterday to

Patrice Godefroid and Pierre Wolper for their paper A Partial Approach to Model Checking,
Dale Miller and Joshua Hodas for their paper Logic Programming in a Fragment of Intuitionistic Linear Logic and
Dexter Kozen for his paper A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events.

This year's award was given to papers presented at LICS 1991 that have stood the test of time and have had considerable impact since their publication. (Source: Prakash Panangaden)

Congratulations to all the award recipients!

FPSAC 2011

2011-06-23T09:19:00.000Z

I have received the following short report on FPSAC 2011 from Henning Úlfarsson, which I post with pleasure. Sources within my extended family told me that the conference was very well attended. The lecture hall was packed and it was nearly impossible to get close to the posters. The lure of Iceland as a conference location strikes again :-)

The 23rd International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2011, was held in Reykjavik, Iceland on June 13-17, on the premises of the University of Iceland. This year's conference was dedicated to the memory of Philippe Flajolet, who passed away recently, and was very influential in the field of algebraic and analytic combinatorics. (An obituary for Philippe Flajolet may be found here.)

The conference featured 10 invited speakers, 27 talks, 53 poster presentations as well as an afternoon of software demonstrations. The topics ranged from various aspects of combinatorics to applications such as shallow water waves and genome arrangements.

More information can be found on the website http://combinatorics.is/.

Videos of talks by Friedman and Macintyre

2011-06-21T15:56:00.000Z

There has been a fair amount of discussion recently on the FOM mailing list on whether the consistency of Peano Arithmetic is a legitimate mathematical problem in present day mathematical culture. This discussion has been sparked by the talk Foundational Concerns and Mathematical Concerns that Angus Macintyre gave at the New Trends in Logic meeting. The video of Angus' talk is here. Perhaps some of the readers of this blog will want to have a look and reach their own conclusions. The person who asks most of the questions to Angus Macintyre is Harvey Friedman, whose own talk at the Vienna meeting can be seen here.

I have to say that Angus Macintyre kept his cool and maintained his thread admirably during his talk.

The videos of all the lectures may be found here, including the one delivered by Thierry Coquand when he received one of the prizes for 2008.

Jan Bergstra turns sixty

2011-06-20T10:54:00.001Z

Jan Bergstra turns 60 today. Jan is one of the concurrency theorists whose work has had a lot of influence on mine, as well as on that of many others. However, his research interests are much broader and his research so far gives excellent examples of the power of algebraic tools and ideas in TCS.

According to Jan's Wikipedia entry, his main theoretical research programmes are:

a systematic study of specification methods for abstract data types (starting in 1979, with John V. Tucker);
the invention, development and application of process algebras, especially ACP (starting in 1984, with Jan Willem Klop, Jos Baeten and others);
Module Algebra (starting in 1986, together with Paul Klint and Jan Heering);
Program Algebra (starting in 1998, with Marijke Loots).

This gives a pretty fair reflection of the main thrusts in Jan's research work, and match pretty closely the topics covered by the five papers he has published in the JACM.

Apart from his scientific work, Jan Bergstra has had considerable influence on computer science in the Netherlands via his research and organizational activities. As an example of the impact he has had on CS in the NL, I limit myself to mentioning here that he has supervised over 40 PhD students, many of whom have become academic computer scientists (according to Wikipedia, at least 12 at professorial level).

As a recognition of his work, on May 18 this year, Jan has been inducted into the Royal Netherlands Academy of Arts and Sciences.

I wish Jan many happy returns for his 60th birthday and many more years of seminal scientific activity.

Addendum dated June 23: A special issue of Theoretical Computer Science devoted to the festschrift in honour of Jan Bergstra, edited by I. Bethke, A. Ponse and P.H. Rodenburg, is now available.

Rector Corradini, I Presume

2011-06-16T12:57:00.000Z

This is not news anymore, but I am happy to report that Flavio Corradini was elected rector of the University of Camerino (Italy) on June 8. To the best of my knowledge, Flavio is now the youngest rector of an Italian university, and the first concurrency theorist to become rector of an Italian university. I wish him the best of luck for his new role, and hope that he will be able to continue doing some (theoretical) computer science.

Jos Baeten new general director of CWI

2011-06-06T21:51:00.000Z

On June 1, I congratulated Jos Baeten for officially becoming the new chair of IFIP WG 1.8. Now, more congratulations to Jos are in order. Indeed, today the General Board of the Netherlands Organisation for Scientific Research (NWO) confirmed Jos' appointment as the new general director of the Centrum Wiskunde & Informatica (CWI) in Amsterdam. I learned the news from Jos himself, who is here in Reykjavik to attend Discotec 2011 and to deliver an invited talk at PACO.

The appointment of Jos as general director of CWI is excellent news for concurrency theory, and volume B TCS at CWI and in the Netherlands as a whole. In a way, it is also the "return of SEN 2", It is a bit ironic that Jos, who was one of the early directors of the very successful SEN 2 project, which was closed in 2008, returns now as general director of the whole institute. This may be seen as a case of "SEN 2 strikes back."

In any event, congratulations to Jos. I wish him a very successful term as director of CWI, which is one of the hotbeds of TCS research in the world. I look forward to seeing how CWI will develop under his expert leadership.

New Chair for IFIP WG 1.8

2011-06-01T15:47:00.000Z

Jos Baeten has formally taken over the chairmanship of IFIP WG 1.8 on Concurrency Theory. I say "formally" because Jos has acted as de facto chair of the working group for some time already, since I decided not to run for a second term as chair.

Congratulations to Jos! I wish him the best of luck for his work as chairman of WG 1.8.

Accepted Papers for CONCUR 2011

2011-05-30T09:29:00.000Z

I noticed that the list of accepted papers for CONCUR 2011 is available here. As usual, there are several interesting papers to look at. I just hope to have the time to do so. As someone said once: "Fermate il mondo! Voglio scendere!" ("Stop the world! I want to get off!")

Hubert Garavel received the Gay-Lussac Humboldt Research Award

2011-05-19T10:01:00.000Z

These are good days for concurrency theory and computer-aided verification, at least judging by the awards bestowed on members of our community.

Yesterday I mentioned that the Presburger Award 2011will go to Patricia Bouyer. Holger Hermanns has now made me aware of the fact that Hubert Garavel recently received the Gay-Lussac Humboldt Research Award. (Thanks Holger!) Hubert is the fourth French scientist in the field of computer science to be awarded this prize. You can read more about the award to Hubert here. For the few readers who might not know his work, here I just limit myself to mentioning that Hubert is a pioneer in formal methods and verification tools for critical industrial systems. He is perhaps best known for being the prime mover behind the development of CADP, which is a popular toolbox for the design of communication protocols and distributed systems. CADP has been developed now for over twenty years, reflecting the very strong commitment to tool development based on elegant and useful theory that underlies Hubert's work.

Congratulations to Hubert and to Holger, who will be his host in Germany.

I note in passing that the awards to Hubert and Patricia offer further, albeit circumstantial, support on the strength of French TCS research.

Presburger Award 2011 to Patricia Bouyer-Decitre

2011-05-18T15:59:00.000Z

The Presburger Award 2011 will go to Patricia Bouyer-Decitre. See here for the details.

Patricia has contributed important results to the theory and applications of timed automata, a fundamental model of real-time systems. In 2007 she received CNRS Bronze medal, awarded for outstanding achievements by a junior researcher.

I am very happy that this award went to Patricia. I had the pleasure of doing some work together with her at the very beginning of her career, and she has gone from strength to strength.

Congratulations to Patricia!

ERC Advanced Grant to Glynn Winskel

2011-05-06T16:11:00.000Z

I just saw that Glynn Winskel has been awarded an Advanced Grant from the European Research Council for the period 1/05/2011-30/4/2016. The grant is for the project Events, Causality and Symmetry---the next generation semantics. (Extended Synopsis.)

This grant recognized one of the key players in the theory of concurrency over the last 20 years. Glynn's work on event structures, amongst other things, has had a lot of influence within my research community and it is good to see that this model plays a key role in the funded proposal. Glynn was also the director of BRICS, a research centre that had an enormous influence on TCS research in Europe and beyond.

Congratulations to Glynn!

Accepted papers for CALCO and TARK

2011-05-03T13:18:00.000Z

The list of accepted paper for CALCO 2011 is here. The list of selected papers for TARK XIII is also available.

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

2011-04-29T22:34:00.000Z

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).

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.
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.
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..

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

2011-04-27T22:10:00.001Z

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

2011-04-27T12:59:00.000Z

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).

Best paper awards at ICALP 2011

2011-04-15T09:52:00.000Z

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

Track A

Malte Beecken, Johannes Mittmann and Nitin Saxena. Algebraic Independence and Blackbox Identity Testing.
Shi Li. A 1.488-approximation algorithm for the uncapacitated facility location problem. (Best student paper)

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!

Accepted papers for ICALP 2011 tracks A and C

2011-04-13T09:29:00.001Z

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.

Source of a quote by Lazlo Babai

2011-04-12T22:25:00.001Z

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

2011-04-12T14:41:00.000Z

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.

Student Scholarships at ICALP 2011

2011-04-09T09:16:00.000Z

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.

SOS 2011: Call for Papers

2011-03-21T18:02:00.002Z

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 :-)

Accepted papers for LICS 2011

2011-03-11T18:14:00.000Z

The list of accepted papers for LICS 2011 is out (with abstracts). The programme looks very strong, as usual.

One week to the ICALP deadline

2011-02-08T09:42:00.000Z

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

you are invited to submit an extended abstract of no more than 12 pages in LNCS style;
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!

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

2011-02-06T18:38:00.004Z

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

Writing papers the hard way

2011-02-01T23:22:00.000Z

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

Faculty position in computer systems at Reykjavik University

2011-01-18T10:41:00.000Z

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.

Second call for papers: ICALP 2011

2011-01-14T09:20:00.002Z

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.

Concurrency Column of the BEATCS for February 2011

2011-01-11T22:19:00.000Z

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.

Pushdown Automata and Vector Addition Systems

2010-12-03T20:45:00.000Z

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.

Springer's LNCS

2010-11-02T07:52:00.000Z

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.

Call for nominations for EATCS awards

2010-10-29T08:27:00.001Z

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!

Postdoctoral position at Reykjavik University

2010-10-20T06:56:00.000Z

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

http://www.ru.is/faculty/luca/PROJECTS/PROMOLO/

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

http://www.icetcs.ru.is/.

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.

LICS 2011 Test-of-Time Award Nominations

2010-10-06T09:28:00.000Z

The LICS Test-of-Time Award recognizes a small number of papers from the LICS proceedings from 20 years prior that have best met the "test of time". The LICS 2011 Test-of-Time Award committee is, as usual, stellar and consists of Tom Henzinger, Radha Jagadeesan, Catuscia Palamidessi, and Andy Pitts (Chair). All papers published in the LICS 1991 Proceedings are eligible, see here for the complete list. Any member of the LICS community is welcome to send recommendations to Andy Pitts at Andrew.Pitts@cl.cam.ac.uk.

I already sent in my nomination yesterday, and I encourage my readers to recommend their favourite paper from LICS 1991. This is my fourth nomination this year, and so far I am zero out of three. Let's see whether the author of the paper I recommended will be any luckier.

Call for Papers for FSEN 2011

2010-09-29T09:43:00.000Z

I have been asked to distribute this call for papers. Consider submitting to FSEN 2011, thereby supporting a young, good-quality conference in formal approaches to software engineering, broadly construed!

########################################
CALL FOR PAPERS

Fourth International Conference on
Fundamentals of Software Engineering 2011
Theory and Practice
(FSEN '11)

http://fsen.ir/2011

Tehran, Iran
April 20-22, 2011

########################################

About FSEN

FSEN is an international conference that aims to bring together
researchers, engineers, developers, and practitioners from the academia
and the industry, who work in every area of formal methods. This
conference seeks to facilitate the transfer of experience, adaptation of
methods, and where possible, foster collaboration among different groups.
The topics of interest cover all aspects of formal methods, especially
those related to advancing the application of formal methods in the
software industry and promoting their integration with practical
engineering techniques. Following the success of the previous FSEN events
in 2005, 2007 and 2009, the next event in the FSEN series will take place
in Tehran, Iran, April 20-22, 2011.
---------------------------------------------------------------------

In cooperation with

ACM SIGSOFT
IFIP WG2.2
---------------------------------------------------------------------

Important Dates

Abstract Submission: October 18 , 2010
Paper Submission: October 25 , 2010
Notification: December 13, 2010
Camera Ready: January 10 , 2011
Conference: April 20-22, 2011
---------------------------------------------------------------------

Keynote Speakers

Carlo Ghezzi, Politecnico di Milano, Italy
Joost-Pieter Katoen, RWTH Aachen University, Germany

(Third speaker to be announced)
---------------------------------------------------------------------

Topics of Interest

The topics of this symposium include, but are not restricted to, the
following:

* Models of programs and systems
* Software specification, validation and verification
* Software architectures and their description languages
* Object and multi-agent systems
* Coordination and feature interaction
* Integration of formal and informal methods
* Integration of different formal methods
* Component-based development
* Service-oriented development
* Model checking and theorem proving
* Software and hardware verification
* CASE tools and tool integration
* Application to industrial cases

The length of each paper including figures and references must not exceed
15 pages and should conform to the Springer LNCS style. All papers must be
submitted in PDF or postscript format. Submissions should explicitly state
their contribution and their relevance to the theme of the conference.
Other criteria for selection will be originality, significance,
correctness, and clarity. Simultaneous or similar submissions to other
conferences or journals are not allowed.
----------------------------------------------------------------------

Proceeding and Special Issues

The post-proceedings of FSEN11 will be published by Springer Verlag in the
LNCS series. There will also be a pre-proceeding for the accepted papers,
which is printed locally by IPM. This pre-proceeding will be made
available at the conference.

The proceedings of FSEN07 and FSEN09 were published in the LNCS series. A
special issue of Science of Computer Programming is being published,
containing the extended versions of a selection of papers of FSEN09. A
special issue of Fundamenta Informaticae was published, containing the
extended versions of a selection of papers of FSEN07. The proceedings of
FSEN05 was published in the ENTCS series: ENTCS 159 (2006). Two special
issues were published containing the extended versions of a selection of
papers of FSEN05 in Fundamenta Informaticae (FI, vol. 82, 2008) and in
Journal of Universal Computing (J.UCS, 13(13), 2007).

----------------------------------------------------------------------
General Chair

Hamid Sarbazi-azad - IPM, Iran; Sharif University of Technology, Iran

Program Chairs

Farhad Arbab - CWI, Netherlands; Leiden University, Netherlands
Marjan Sirjani - Reykjavik University, Iceland; University of Tehran, Iran

Steering Committee

Farhad Arbab - CWI, Netherlands; Leiden University, Netherlands
Christel Baier - University of Dresden, Germany
Frank de Boer - CWI, Netherlands; Leiden University, Netherlands
Ali Movaghar - IPM, Iran; Sharif University of Technology, Iran
Hamid Sarbazi-azad - IPM, Iran; Sharif University of Technology, Iran
Marjan Sirjani - Reykjavik University, Iceland; University of Tehran, Iran
Jan Rutten - CWI, Netherlands; Vrije University Amsterdam, Netherlands

Program Committee

Luca Aceto - Reykjavik University, Reykjavik, Iceland
Gul Agha - University of Illinois at Urbana - Champaign, USA
Farhad Arbab - CWI, Netherlands; Leiden University, Netherlands
Jos Baeten - Eindhoven University of Technology, Netherlands
Christel Baier - University of Dresden, Germany
Frank de Boer - CWI, Netherlands; Leiden University, Netherlands
Marcello Bonsangue - Leiden University, Netherlands
Mario Bravetti - University of Bologna
James C. Browne - University of Texas at Austin, USA
Einar Broch Johnsen - University of Oslo, Norway
Michael Butler - University of Southampton, UK
David Clarke - CWI, Netherlands; K.U.Leuven, Belgium
Wan Fokkink - Vrije Universiteit Amsterdam, Netherlands
Masahiro Fujita - University of Tokyo, Japan
Maurizio Gabbrielli - University of Bologna, Italy
Radu Grosu - State University of New York at Stony Brook, USA
Jan Friso Groote - Technical University of Eindhoven, Netherlands
Joost Kok - Leiden University, Netherlands
Ramtin Khosravi - University of Tehran, Iran
Kim Larsen - Aalborg University, Denmark
Zhiming Liu - United Nations University, Macao, China
Seyyed Hassan Mirian - Sharif University of Technology, Iran
Sun Meng - Peking University, China
Ugo Montanari - University of Pisa, Italy
Peter Mosses - Swansea University, UK
Mohammad Reza Mousavi - Technical University of Eindhoven, Netherlands
Ali Movaghar - IPM, Iran; Sharif University of Technology, Iran
Andrea Omicini - University of Bologna, Italy
Saeed Parsa - Iran University of Science & Technology, Iran
Hiren Patel - University of Waterloo, Canada
Jan Rutten - CWI, Netherlands; Vrije University Amsterdam, Netherlands
Davide Sangiorgi - University of Bologna, Italy
Marjan Sirjani - Reykjavik University, Iceland; University of Tehran, Iran
Carolyn Talcott - SRI International, USA

CNRS Bronze Medal to Thomas Colcombet

2010-09-21T09:31:00.001Z

Thomas Colcombet of LIAFA, Université Paris Diderot - Paris 7, has been awarded a CNRS bronze medal. See here for the full list of awardees. As you can see, Thomas is the only recipient of the award in the field of computer science. It is good for TCS at large to see one of its researchers receive such a prestigious national award.

This has been quite a year for researchers working on the classic theory of automata, logic and their applications. Earlier in 2010, one of Thomas' collaborators, viz. Mikolaj Bojanczyk, received the first Presburger Award and Anca Muscholl was awarded a CNRS silver medal.

Congrats to all of them!

SOS 2010

2010-09-09T22:40:00.001Z

On August 30, Pawel Sobocinski and I co-chaired SOS 2010, an affiliated workshop of CONCUR 2010. The workshop programme was interesting and we had 18 participants. (It was hard to compete with EXPRESS 2010, which had 35 registered participants.) The proceedings for the workshop are available as an EPTCS volume.

Apart from five contributed talks touching on a fairly wide variety of topics, the workshop featured two invited presentations. MohammadReza Mousavi kicked off the workshop in style with a talk entitled How to cook a security-enabled semantics. In his talk, which was partly based on this paper, Mohammad introduced notions such as restricted revocable delegation and studied their consequences in language-based security. Listening to Mohammad speak I felt, not for the first time, that language-based security is one of the (alas, many) topics that I should make an effort to understand better.

The second invited talk was joint with EXPRESS, and was delivered by Catuscia Palamidessi. Catuscia had a very large audience for a workshop, and fortunately we had decided to move to a lecture hall that could hold about 100 people before her talk :-). Catsucia's talk, which was entitled Compositionality of Secure Information Flow, dealt with ways in which one can quantify the amount of leakage of confidential information through public outputs in computer systems. Catuscia discussed a proposal for measuring the amount of leakage that is based on the Bayes risk, namely (the converse of) the probability of guessing the right value of the secret, once we have observed the output. In her talk, Catuscia presented a process calculus for the specification of systems composed by concurrent and probabilistic processes, and investigated "safe constructs", namely constructs which do not increase the leakage.

Overall, I like to think that SOS 2010 was a successful workshop. However, I would like to see this workshop series be more visible and receive more submissions. I hope that future chairs will be more successful than I have been in achieving these goals.

A Selection of Papers from CONCUR 2010

2010-09-08T22:23:00.001Z

As I have already mentioned in earlier posts, I enjoyed a lot of talks in the programme for CONCUR 2010. Here are just a few highlights, with apologies to all the speakers whose talks/papers I do not mention in this post. Overall, the conference programme was of very high quality. This bodes well for the future of CONCUR.

Lutz Schröder and Yde Venema. Flat Coalgebraic Fixed Point Logic. Lutz presented the paper and gave a very clear introduction to the coalgebraic approach to the study of modal logics. Technically, this paper presents a unified co-algebraic treatment of flat fixed-point logics. (Fixed-point logics, such as the mu-calculus, are widely used in computer science, in particular in artificial intelligence and concurrency.) The main results in the paper are the completeness of the Kozen-Park axiomatization and a general EXPTIME upper bound for flat fixed-point logics.
Fides Aarts and Frits Vaandrager. Learning I/O Automata. The talk was delivered by Frits, who addressed the general question of learning models of reactive systems automatically, e.g., for model-based testing or software engineering.In this work, Fides and Frits establish links between three widely used modelling frameworks for reactive systems: the ioco theory of Tretmans, the interface automata of De Alfaro and Henzinger, and Mealy machines. It is shown that, by exploiting these links, any tool for active learning of Mealy machines can be used for learning I/O automata that are deterministic and output determined. The approach presented in the paper has been implemented on top of the LearnLib tool and has been applied successfully to three case studies, including learning a model of Fides' biometric passport.
Pawel Sobocinski. Representations of Petri net interactions. . Pawel, who was my co-chair for SOS 2010, presented a novel compositional algebra of Petri nets. The algebra contains two binary operators (tensor product and sequential composition) and twelve constants! He also introduced a stateful extension of the calculus of connectors and showed that .these two formalisms have the same expressive power.
Pavol Cerny, Thomas Henzinger and Arjun Radhakrishna. Simulation Distances. The simulation preorder is often used to establish the correctness of an implementation I with respect to a specification S as follows: I correctly implements S if S can simulate the behaviour of I. In other words, this happens if everything the implementation I does is allowed by the specification S. The result of such a verification is boolean and cannot be used to assess how far I is from implementing the behaviour allowed by S. This paper extends the simulation preorder to the quantitative setting by defining three different simulation distances. The correctness distance measures how much the specification must be changed in order to be satisfied by the implementation. The coverage distance measures how much the implementation restricts the degrees of freedom offered by the specification. The robustness distance measures how much a system can deviate from the implementation description without violating the specification. The paper develops a comprehensive theory for those notions of simulation distances.

Reading the papers from CONCUR 2010 will keep me busy for some time.

Milner Session at CONCUR 2010

2010-09-07T22:36:00.000Z

During CONCUR 2010, the concurrency-theory community paid a small tribute to Robin Milner by dedicating a session of its flagship conference to him. The so-called Milner Session was held on Wednesday, 1 September, from 2pm till 4pm. It consisted of a talk by Jos Baeten and of three presentations of papers that were selected for the conference by the PC.

Jos kicked off the session with a talk devoted to Milner's contributions to concurrency theory. He focused on his seminal Calculus of Communicating Systems, providing an overview of its syntax, of some of the design decisions Milner made in that calculus and of its semantics. The presentation by Jos was followed by a short discussion, with remarks from Ugo Montanari, Kohei Honda and myself, amongst others.

My two readers might be interested in reading a short note by Samson Ambramsky entitled Robin Milner's Work on Concurrency that was published yesterday in the Proceedings of MFPS 2010. According to Samson,

Robin’s ideas have become part of the air we breathe in our scientific community.....

CCS was not just a new calculus, but a new paradigm — that has played a central role in the subsequent development of our subject. It opened up the world of compositional behavioural modelling.

I have always found that one of the red threads in Milner's work was the, I believe novel, emphasis on behavioural semantics and on his standpoint that a process is an equivalence class of process descriptions (be they terms in a process algebra/calculus or states in a labelled transition system/automaton) modulo some notion of behavioural equivalence. Milner himself reiterated this point in several of his writings/talks, and I am glad to see this mentioned in Samson's piece.

We knew what functions were already! But what are processes? CCS established the fundamental methodological point of studying them through their observational behaviour (defined in terms of labelled transition systems via SOS).

This led inexorably in turn to notions of observational equivalence.

Thanks to Jos and Samson for their tributes to Milner's work.

Amongst the contributed talks in the Milner Session, let me mention the excellent talk by Edsko de Vries, who presented joint work with Vasileios Koutavas and Matthew Hennessy on Communicating Transactions. Communicating transactions are obtained by dropping the isolation requirement from standard transactions and can be used to model automatic error recovery in distributed systems. Edsko presented a behavioural theory for a version of CCS with communicating transactions that is sound and complete with respect to the may-testing preorder. The technical work looked really impressive.

I really enjoyed Silvia Crafa's talk entitled A Logic for True Concurrency, which presented joint work with Paolo Baldan. Perhaps, I was biased since Silvia's talk brought me back in time some twenty years, when a different version of myself was working on topics related to true concurrency. However, I was not the only one to be impressed by that paper, which proposes a logic for true concurrency whose formulae describe events in computations and their causal dependencies. The induced logical equivalence is hereditary history preserving bisimilarity. The authors also identify fragments of the logic that capture other truly concurrent behavioural equivalences in the literature: step, pomset and history preserving bisimilarity. After Silvia's talk, I felt that her paper with Paolo should have been written long ago.

A Thought Experiment

2010-09-06T11:52:00.000Z

Suppose that a top-class conference to which you usually submit your papers decide to publish its proceedings in an electronic open-access outlet instead of using a commercial publisher, like STACS and FST-TCS have done over the last few years. Would that decision have any effect on whether you submit your papers to that conference? Would you encourage your students to submit to that conference in order to further their future career? Do you think that a prestigious conference has anything to lose in publishing its proceedings in an electronic open-access outlet?

CONCUR 2010

2010-09-05T22:43:00.003Z

From August 30 till the very early hours of September 3, I was in Paris to co-chair SOS 2010 and attend CONCUR 2010. It is always a pleasure to have the chance to attend CONCUR, which is the flagship conference for the concurrency-theory community, and the lure of Paris made this conference even more attractive than usual.

CONCUR 2010 was perfectly organized by Paul Gastin (LSV, ENS Cachan, France), François Laroussinie (LIAFA, Université Denis Diderot - Paris 7, France) and their support team (see the bottom of this page for the details), and was held at Université Denis Diderot - Paris 7.

According to the program chairs, there were 160 people registered for the main conference and 215 people were registered for the conference or one of the eight affiliated events. I am not a CONCUR historian, but I believe that this makes this edition of CONCUR one of the best attended on record, together with the one held in Bologna last year. I do not find this level of attendance particularly surprising----after all, Paris is an attractive city and it is one of the hotbeds of research in concurrency theory. However, it is a great credit to the organizational effort that everything went smoothly and that the atmosphere at the conference was relaxed and conducive to both scientific and social exchanges.

On behalf of the CONCUR community, I'd like to say thanks to François, Paul and their support team for organizing a great conference. We had many excellent talks on a variety of exciting topics, a session devoted to Robin Milner (chaired by Matthew Hennessy and featuring a talk by Jos Baeten), varied and tasty lunches served next to the conference room, and yet another edition of the CONCUR football match (which saw about 20 participants kick a ball around for about one hour before the conference dinner).

I hope to devote another post to the main conference and to SOS 2010. Here I will just limit myself to a few brief remarks on the invited talks that I could attend. (Unfortunately, I had to leave at an ungodly early hour on Friday, 3 September, and therefore I missed Holger Hermann's invited presentation and the last day of the conference. Knowing Holger's communication skills, I am sure that I missed a great talk. I hope that Holger will make a recording of his talk available from his web page.)

The conference was given the best possible start by Vladimiro Sassone, who delivered a very clear talk entitled Trust in Anonymity Networks. In his presentation, after having introduced the basic setting of anonymity protocols, Vladimiro presented an analysis of the privacy guarantees of the Crowds anonymity protocol, with and without onion forwarding, for standard and adaptive attacks against the trust level of honest users.

I had the great honour of chairing the session featuring the second invited talks, which was delivered by Maurice Herlihy. After-lunch sessions are always challenging, especially when the conference is held in France, but Maurice's talk, entitled Applications of Shellable Complexes to Distributed Computing, was the perfect digestive after an excellent lunch. In his talk, Maurice reviewed some of the ideas behind his award-winning application of tools from algebraic topology to distributed computing and then discussed some very recent results that will be presented at DISC 2010 in the paper Concurrent Computing and Shellable Complexes co-authored with Sergio Rajsbaum.

In her talk Taming Distributed Asynchronous Systems, Anca Muscholl delivered a good overview of many results and open problems related to analysis techniques for distributed, asynchronous systems with two kinds of synchronization, namely shared variables and fifo channels. Anca has just received the prestigious CNRS silver medal for 2010 for computer science. Congrats to her!

The last invited talk I was able to attend was delivered by Frank S. de Boer, who gave a presentation entitled Dating Concurrent Objects: Real-Time Modeling and Schedulability Analysis. After giving the audience an overview of the CREDO project, Frank introduced a real-time extension of the concurrent object-oriented language Creol, and showed us how to analyze schedulability of an abstraction of real-time concurrent objects in terms of timed automata. He concluded the talk by telling the audience about techniques for testing the conformance between these behavioral abstractions and the executable semantics of Real-Time Creol in Real-Time Maude. I enjoyed the talk, and I think that Frank was successful in keeping his audience away from their laptops and in making the attendees resist the temptation of checking their email during his talk, which was one of his stated aims!

Addendum. Holger Hermann's invited presentation is now available (in flash) from here. Enjoy!

One year of Electronic Proceedings in Theoretical Computer Science (EPTCS)

2010-08-24T13:48:00.001Z

Electronic Proceedings in Theoretical Computer Science (EPTCS) was launched by Rob van Glabbeek in 2009, as an initiative to have proceedings of all worthy workshops in Theoretical Computer Science freely available on-line. The papers in the proceedings are simply entries in the CoRR repository. DOI numbers are assigned to EPTCS publications, and they are indexed in CrossRef and in the Directory of Open Access Journals. There is no charge for authors or workshops/conferences.

The idea caught on like wildfire, and since EPTCS was launched over 30 proceedings were published, and 22 more have been accepted for publication.

Perhaps one of the reasons is that the procedure for submitting a proposal is very simple, and our response time to a proposal is very fast, usually less than 10 days. Additionally, thanks to efficient workflow, proceedings usually appear within 10 days after all the constituents have been delivered.

We find that it is very important to properly record workshop proceedings in one, easily searchable place. Also, we want to contribute in this way to the growing acceptance of the view that all scientific publications should be freely available on-line.

We hope that researchers working in Theoretical Computer Science will follow the example of the many others in accord with the originators of this idea. Please see http://published.eptcs.org/ for the list of published workshops.

The editors,

Rob van Glabbeek (NICTA, Sydney, Australia)
Editor in Chief
Luca Aceto (Reykjavik University)
Rajeev Alur (University of Pennsylvania)
Krzysztof R. Apt (CWI and University of Amsterdam)
Lars Arge (Aarhus University)
Ran Canetti (Tel Aviv University)
Luca Cardelli (Microsoft Research)
Rocco De Nicola (Universita di Firenze)
Jose Luiz Fiadeiro (University of Leicester)
Wan Fokkink (Vrije Universiteit Amsterdam)
Lane A. Hemaspaandra (University of Rochester)
Matthew Hennessy (Trinity College Dublin)
Bartek Klin (Warsaw University, University of Cambridge)
Evangelos Kranakis (Carleton University)
Shay Kutten (Technion)
Nancy Lynch (Massachusetts Institute of Technology)
Aart Middeldorp (University of Innsbruck)
Benjamin Pierce (University of Pennsylvania)
Gordon Plotkin (University of Edinburgh)
Vladimiro Sassone (University of Southampton)
Robert H. Sloan (University of Illinois at Chicago)
Wolfgang Thomas (RWTH Aachen University)
Irek Ulidowski (University of Leicester)
Dorothea Wagner (Universitaet Karlsruhe (TH))
Martin Wirsing (LMU Munich)
Moti Yung (Google Inc. and Columbia University)

Rolf Nevanlinna Prize to Daniel Spielman

2010-08-19T08:16:00.000Z

Daniel Spielman has been chosen for the 2010 Rolf Nevanlinna Prize for smoothed analysis of Linear Programming, algorithms for graph-based codes and applications of graph theory to Numerical Computing. The full details are here.

Congrats to Daniel for landing another prize after the Goedel prize 2008, which he received in Reykjavik during ICALP 2008.

Details about the other prize winners are here.

An interesting publication experiment in the logic-programming community

2010-07-07T12:13:00.002Z

Krzysztof Apt has alerted me of the changes that have taken place in the Logic Programming community. The Association for Logic Programming (ALP) recently left the Springer LNCS series and embraced a new publication model for the proceedings of their flagship conference (the International Conference on Logic Programming (ICLP)) that tries to upgrade the papers directly to journal papers. Here is how the co-chairs of the 2010 edition of the conference describe the new publication model and its rationale.

The Logic Programming (LP) community, through the Association for Logic Programming (ALP) and its Executive Committee, decided to introduce for 2010 important changes in the way the main yearly results in LP and related areas are published. Whereas such results have appeared to date in standalone volumes of proceedings of the yearly International Conferences on Logic Programming (ICLP), and this method – fully in the tradition of Computer Science (CS) – has served the community well, it was felt that an effort needed to be made to achieve a higher level of compatibility with the publishing mechanisms of other fields outside CS.

In order to achieve this goal without giving up the traditional CS conference format a different model has been adopted starting in 2010 in which the yearly ICLP call for submissions takes the form of a joint call for a) full papers to be considered for publication in a special issue of the journal, and b) shorter technical communications to be considered for publication in a separate, standalone volume, with both kinds of papers being presented by their authors at the conference. Together, the journal special issue and the volume of short technical communications constitute the proceedings of ICLP.

The special issue of the journal Theory and Practice of Logic Programming (TPLP) devoted to the 26th International Conference on Logic Programming Special is the first of a series of yearly special issues of that journal putting this new model into practice. It contains the papers accepted from those submitted as full papers (i.e., for TPLP) in the joint ICLP call for 2010. The collection of technical communications for 2010 will appear in turn as Volume 7 of the Leibniz International Proceedings in Informatics (LIPIcs) series, published on line through the Dagstuhl Research Online Publication Server (DROPS). Both sets of papers will be presented by their authors at the 26th ICLP.

This seems a very interesting way of dealing with some of the concerns that have been aired by some pundits about the publication culture within CS, while preserving the crucial role that conferences play in CS. I think that it is certainly worth a thought.

Call for papers: ICALP 2011

2010-07-05T10:10:00.000Z

The first call for papers for ICALP 2011, which is presently being distributed at ICALP 2010, is here.

I hope that you will make plans to submit excellent papers to ICALP 2011.

Organizing a conference with satellite events

2010-06-22T23:05:00.001Z

Suresh asked me to expand on a comment I posted here, where I described my experience with the organization of ICALP 2008 in Reykjavik, which I believe is still the most attended and event-packed ICALP conference on record.

First of all, even without satellite events, ICALP is a three-track conference, and has been so since 2005, though typically only two tracks are running in parallel at each point in time. At ICALP 2008, in addition we had 12 satellite events, including the DYNAMO training school for doctoral students. There were no tutorials, apart from the lectures at the PhD school, but we hosted a masterclass by Peter Winkler on mathematical puzzles, which I estimate was attended by well over 250 people, including local high-school teachers and students. Overall, nearly 500 people were registered for the main conference and/or the satellite events.

The workshops were held the day before ICALP or during the week-end following it. They were selected by the ICALP organizers amongst a fairly large number of proposals that we received in response to a call for workshops, based on their perceived scientific quality and on their potential interest to the ICALP community. As ICALP organizers, we made sure that each workshop had a suitable room at the university and some minimal amount of logistical and technical support. (Typically, at least a local student or a postdoc was permanently in residence during each workshop.) We also printed the preliminary proceedings of the workshops and took care of arranging lunches and coffee breaks. The costs were covered by the workshop registration fees. Overall, the overhead generated by the organization of the satellite events was minimal, or at least it looks so two years after the facts :-)

Organizing such a conference was not an easy job, but it was not as daunting as it may seem. In hindsight, I think that it was important to organize the event at the university (not a hotel---in passing, I very much prefer attending events held at universities rather than hotels), to have the assistance of the university support services, of some local students and postdocs, and of experienced conference organizers who took care of the registrations, of the lunches and coffee breaks and of the social programme. Magnus Halldorsson, Anna Ingolfsdottir and I organized ICALP and were assisted by Bjarni Haldorsson and MohammadReza Mousavi in the organization of the workshops. I firmly believe that the task of organizing a conference like ICALP should be shared amongst several people. This certainly worked for us and helped us work more cheerfully, and overcome personal problems, mishaps and periods of crisis and panic that arose during the year before the conference took place.

Overall, I do not think that organizing ICALP ended up being much more work than organizing a single-track conference without satellite events.

Let me close by adding that the model used for ICALP is rather common in conferences related to TCS with a "volume B flavour". See, for instance, the experience of the ETAPS conference series, which involves five major conferences, tutorials and a large number of satellite events, and of the Federated Logic Conference (FLoC), featuring eight major conferences and large number of workshops in 2010. Readers of this post may like to know that typically workshops are proposed by members of the community, and so are the tutorials at ETAPS.

As an external observer, I fail to see why STOC could not follow the example of those federated conferences and, at the same time, broaden its scope to cover more topics in TCS and accept a few more papers, if their quality is excellent, rather than relinquish its high-profile, peer-reviewed status.

Gödel Prize 2010

2010-06-09T19:40:00.001Z

I have not seen any official announcement yet, but, according to Wikipedia and to Theory Announcements (thanks to the anonymous commenter who pointed out the latter source), the Gödel Prize 2010 has been awarded to Sanjeev Arora and Joe Mitchell for their concurrent discovery of a polynomial-time approximation scheme (PTAS) for the Euclidean Travelling Salesman Problem. Congrats to Arora and Mitchell!

Extended Deadlines for SOS 2010

2010-05-28T11:30:00.000Z

I am co-chairing SOS 2010, an affiliated workshop of CONCUR 2010, which will be held in Paris. You are still on time to submit a paper to that event! The new submission deadlines are as follows:

Submission of abstract: ~~Friday 28th May 2010~~ Tuesday 1st June 2010 (strict)
Submission: ~~Wednesday 2nd June 2010~~ Monday 7th June 2010 (strict)

Can you resist the lure of Paris in late August-early September?

My Workplace

2010-05-27T13:49:00.002Z

Here are some views of my workplace and its environment. The two photos above picture the entrance to my "professorial work area" :-) The one on the right depicts the entrance to my work area and its immediate environment, with the work places of Anna Ingólfsdóttir (left) and Magnús Halldórsson (right, behind the stand where we place some of our recent papers and books). This is the heart of our ICE-TCS enclave.

Can one work in such an environment? So far, the answer seems to be yes, but this is mainly because I am starting to believe one can work anywhere provided everyone in one's neighbourhood adheres to some basic ground rules.

Is the open-space environment conducive to academic work? This I am much less convinced about.

To conclude, here is what the open-space work environment looks like when I arrive at work in the morning. (The photo is taken from outside my cubicle.)

First Presburger Award to Mikolaj Bojanczyk

2010-05-27T11:25:00.000Z

The Presburger Award Committee, consisting of S. Leonardi, A. Tarlecki, and W. Thomas (chair) has chosen Mikolaj Bojanczyk as the first recipient of the EATCS Presburger Award for young scientists.

The motivation from the award committee reads as follows:

Mikolaj Bojanczyk, 32 years old, has contributed numerous deep results to automata theory and to logic and algebra in computer science. Among them is the theorem stating that tree walking automata are strictly weaker than general tree automata, the definition of new decidable logics based on quantifiers for boundedness, and the development of a novel algebraic framework for the study of properties of unranked trees. His work thus led to the solution of long-standing open problems and introduced methods that open new directions in theoretical computer science (also relevant to neighbour disciplines such as data base theory). The committee recommends Mikolaj Bojanczyk as an exceptional young scientist who not only fully deserves the Presburger Award but is also an ideal first recipient. The committee also would like to mention that more than one excellent nomination was made, a fact which lets us hope that the Presburger Award will receive several nominations of truly exceptional level from all areas of theoretical computer science in the coming years.

Let me add that, in 2005, Mikolaj's doctoral thesis, entitled ”Decidable Properties of Tree Languages”, received the Ackermann award of the European Association of Computer Science Logic. In 2006, he was awarded the ”Witold Lipski prize for young Polish researchers in computer science”. In 2007, he received the Kuratowski award for young Polish mathematicians, awarded by the Polish Mathematical Society. In 2009, Mikolaj became one of the very few young computer scientists to obtain a European Research Council Starting Grant.

Congrats to Mikolaj for yet another well-deserved award. May his work go from strength to strength.

Fifth International Summer School on Rewriting

2010-05-15T14:55:00.000Z

The 5th International School on Rewriting will be held in the period July 3-8, 2010, in Utrecht, The Netherlands. The programme includes both basic and advanced lectures. Perhaps some of your graduate students will be interested in attending the event.

Term rewriting is a core area in Theoretical Computer Science. It is powerful model of computation underlying much of declarative programming, which is heavily used in symbolic computation in logic and computer science. Applications can be found in theorem proving and protocol verification, but also in fields as diverse as mathematics, philosophy and biology.

School of Computer Science at RU on Twitter

2010-05-10T12:09:00.000Z

The School of Computer Science at Reykjavik University, where I work, has made the step to advertise its events and news on Twitter. See here. Our aim is to make potential students and the community at large aware of what the school can offer.

Does your institution have a Twitter page too? Do you think that Twitter is a good channel for spreading news to potential CS students?

ICE-TCS Logo

2010-05-06T14:26:00.000Z

After five years of operation, ICE-TCS (our little research centre in TCS) finally has a logo, which you see displayed above in its full glory. The logo design is courtesy of Emilka Bojańczyk. Do have a look at her graphic design work, which I like a lot. If you need logos, posters or any other kind of TCS- or Maths-related design work, I strongly recommend Emilka.

Apart from being a professional graphic designer, Emilka has a mathematical background (she graduated with honours from the Mathematics Department of Warsaw University in 2002) as well as strong family connections with TCS :-) She has also designed the logo for the STACS conference series, amongst other things.

Thanks Emilka!

LICS 2010 Test-of-time Award Winners

2010-05-06T10:10:00.000Z

I just read an email announcing the papers selected for the 2010 LICS Test-of-Time Award. For the 2010 LICS Test-of-Time Award, all papers from LICS 1990 were considered by an Awards Committee consisting of Glynn Winskel (chair), Jean-Pierre Jouannaud and John Mitchell.

In view of the weight of highly-influential papers, across a range of areas, the committee has taken the exceptional step of selecting four papers! They are:

Model-checking for real-time systems by R. Alur, C. Courcoubetis and D. Dill. This paper was a pioneer in the model checking of real-time systems. It provided a polynomial-space algorithm for the model checking of a real-time logic (an extension of CTL with timing constraints) with respect to a continuous-time model. Its techniques are still used extensively and results of this paper form part of almost any course or tutorial on real-time verification.
Symbolic model checking: 10^20 states and beyond by JR Burch, EM Clarke, KL McMillan, DL Dill and LJ Hwang. This paper revolutionized model checking. Through its symbolic representation of the state space using Randy Bryant's Binary Decision Diagrams (BDDs) and its careful analysis of several forms of model checking problems, backed up by empirical results, it provided a first convincing attack on the verification of large-state systems. The paper was a major agent in establishing BDDs as a tool in mainstream computer science.
The theory of ground rewrite systems is decidable by M Dauchet and S Tison. This paper asked what has proved to be a very important question, whether the first-order theory of one-step rewriting is decidable. The paper settled the question positively for the theory of ground rewrite systems using innovative techniques on tree automata. Its techniques rekindled an interest in automata theory on finite trees, now a major topic, with many current applications from rewriting through to security, program analysis and concurrency.
Recursive types reduced to inductive types by P Freyd. This paper showed what was really going on with the classic method of solving domain equations. By separating positive and negative occurrences of the unknown in a domain equation, it gave an elegant category-theoretic treatment of recursively defined domains that extends the well-understood and widely-used methods of initial-algebra semantics. Its methods are now standard. They led to new techniques for relating operational and denotational semantics, and new mixed induction/coinduction principles.

Congratulations to all the recipients of the awards!

Typos, typos....

2010-04-11T15:29:00.000Z

I always tell my students at all levels that there is no excuse for not spell checking one's writings. There are rather good spell-checking programs out there, and one should use them to spot obvious typos.

Spell-checking programs, however, are no substitute for careful proof reading of one's papers. I was reminded of this fact of professional life some time ago when, while reading the revision of a journal submission of mine, I spotted the mention of a "format for impotence of operators" (in lieu of "format for idempotence of operators"). It would have been embarrassing, but admittedly amusing, to send the paper off with that typo left unspotted, just as it was entertaining for my students to attend a lecture mentioning a "poof technique" (rather than "proof technique") on a slide :-)

No spell-checker can find those typos. I'll use them to motivate my students to proof read their texts with care.

ICALP 2010: Accepted papers

2010-04-08T23:36:00.000Z

The list of accepted papers for ICALP 2010 is out. Based on what I saw as a PC member for track B, the overall quality of the submissions was, in general, very high and many good papers could not be selected for presentation at the conference.

Journal Editors or Black Holes?

2010-03-30T15:53:00.000Z

Sometimes journal editors (or referees) are observationally very similar to black holes. A paper is submitted, but no review escapes the force of gravity generated by the scientist in question. If the academic who is submitting the paper is well established, (s)he might not be overly bothered by this "black-hole-like effect" and live to see the day. However, in case the paper is submitted by a young scientist who might be applying for jobs, the negligence of an editor or a reviewer might have negative consequences on the career of the author of the paper.

Suppose, by way of example, that a young scientist submits a substantial paper to a high-impact journal reporting on the major findings in her doctoral dissertation. The first review round takes a whole year, despite repeated enquiries to the handling editor, and the editor asks for major revisions based on the detailed referee reports. The author works hard at handling the suggestions from her reviewers, and submits a revised paper. One more year passes and the email enquiries by the author receive no answer from the cognizant editor.

What would be the best line of action for the young scientist in question? Should she wait for a second bunch of reports, which might never come, or would she be best served by withdrawing the paper and submitting it elsewhere? What advice would you give in a situation like this one?

What Are The Hot Research Areas in Concurrency Theory?

2010-03-27T10:10:00.000Z

Yesterday Andrei Sabelfeld (Chalmers University of Technology, Sweden) visited ICE-TCS with Arnar Birgisson, a former master student of mine who is now doing doctoral studies under his supervision. Andrei delivered the seminar Information flow in web applications in the ICE-TCS seminar series (the abstract for the talk is here), we talked about liveness and safety properties and about academic matters in general. We at ICE-TCS enjoyed his visit a lot.

Over dinner, Andrei asked me:

What are the big unsolved problems in concurrency theory?
And what are the hot research areas in the field?

I gave my quarter-baked personal answers, but I'd like to hear yours.

I have the feeling that research in concurrency theory is driven more by "hot research areas" than by collections of big open problems, but that's just my personal impression, even though at some point I started collecting a list of open problems and stated some in this essay.

Also, how much does the "hotness of a research area" inform the research you do and that you suggest to your students? For what it is worth, for good or for worse, I mostly tend to follow my own personal interests and inclinations rather than the directions of the field at large. However, one has to "sell" one's work and have it published. It is undoubtedly easier to do so if the work is considered to be hot and timely by a substantial fraction of the research community. Doing work in areas that are considered "important" by many will probably also give a student better opportunities to find further employment.

Overall, I feel that it is important to give one's students a good problem to work on for her/his dissertation. There are certain characteristics that a good problem should have for sure, but is "hotness" one of those?

Addendum: There is a lot of good career advice for everyone here.

LICS 2010 Accepted Papers and Martin Grohe's Latest Opus

2010-03-25T09:25:00.001Z

The list of accepted papers for LICS 2010 is out. As usual, the programme looks very interesting and exceedingly strong.

For an interested, but not very knowledgeable, observer like me, one of the most interesting looking papers that have been selected for the conference seems to be yet another seminal contribution by Martin Grohe. The paper is Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors.

From the abstract of that ten-page paper, I learn that Grohe proves that fixed-point logic with counting captures polynomial time over all classes of graphs with excluded minors. To my untrained eye, this looks like an amazing result. The proof of this theorem will take up the whole of this monograph, which is currently being written and will be well over 200 pages long. The current draft spans 238 pages.

Would such a result meet the current requirements for the Gödel prize, say? It seems to me that it would not, unless Grohe also publishes a journal paper based on a fragment of his monograph. Taking the view that proofs of certain results are likely to be very long and that very few journals in computer science would publish papers that are 250 pages long, say, would it not be reasonable to let a research monograph qualify a piece of research for the Gödel prize? After all, if the result is important, it will be studied in depth by many researchers, ensuring a more thorough level of peer review than the one obtained via a standard refereeing process for a journal.

The loss of a giant: Robin Milner has passed away

2010-03-22T16:13:00.001Z

I just read the following message from Gordon Plotkin. This is really sad news. I plan to post a more elaborate message soon, but we have lost another intellectual giant, a gentleman and a true inspiration for us all.

-----------------------------

Dear Colleagues,

I am deeply saddened to pass on the following message from Barney and Chloë Milner:

"We are sorry to announce that Robin Milner died on Saturday 20th March, in Cambridge, just three days after the funeral of his wife, Lucy.

He will be greatly missed by his family and friends, as well as the academic community."

Gordon Plotkin

SOS 2010

2010-03-19T23:29:00.000Z

I am co-chairing SOS 2010 (Structural Operational Semantics 2010) with Pawel Sobocinski (Southampton). The call for papers has been posted on several mailing lists and all the information on this workshop, which is affiliated with CONCUR 2010, is available from the workshop's web site.

Consider submitting a paper and join us in Paris on August 30 to discuss the latest research on Structural Operational Semantics! I have a series of long-overdue posts describing some of the recent work by my co-authors and me on this topic. I hope to find some time to write those posts after the teaching is over and I have cleared my desk a little.

First Clay Mathematics Institute Millennium Prize Announced Today

2010-03-18T23:11:00.000Z

It looks like the Clay Mathematics Institute (CMI) is parting with its first one million USD. Indeed, today the CMI announced that Grigoriy Perelman is the recipient of the Millennium Prize for the resolution of the Poincaré conjecture. Full details are here and a full-length press release is also available.

What do you think will be the next Millennium Prize Problem to fall? It seems very unlikely that it will be our own P vs. NP problem, but, as Bohr taught us, “Prediction is very difficult, especially about the future".

Magnús Halldórsson receives the first Reykjavík University Research Award

2010-02-21T17:51:00.000Z

This is a belated post on a piece of news that is mostly of local (read, Icelandic) relevance. However, I think that TCS researchers everywhere will be pleased to know that the first research award from Reykjavík University, where I have worked since November 2005, has been given to Magnús M. Halldórsson, for his work on approximation algorithms for computationally hard problems, amongst others. (The announcement in English is here.) It is good to see the first research award go to a TCS researcher, also because this sets high standards for future such awards.

It will be interesting to see whether future award committees will be influenced by considerations related to "academic politics" in selecting awardees for the university research award. If not, I expect to see a few awards in the coming years go to people working in (T)CS and combinatorics.

Belated congratulations to Magnús.

Two PhD Studentships Available

2010-01-24T21:59:00.002Z

Yesterday night, I posted the appended announcement of two PhD studentships, which became available thanks to a successful grant application to the Icelandic Fund for Research (Rannis), on a couple of mailing lists.

I am posting it here too, just in case any of the readers of this blog is interested in applying or has any student who would be a suitable candidate for the studentships.

---------------------------------------------------------

Meta-Theory of Algebraic Process Theories

School of Computer Science, Reykjavik University

Two PhD studentships

Applications are invited for two PhD studentships at the School of Computer Science, Reykjavik University. The positions are part of a three-year research project funded by Rannis (the Icelandic Fund for Research), under the direction of Luca Aceto and Anna Ingolfsdottir.

Aim of the project

Algebraic process theories, also known as “process algebras”, are prototype specification languages for reactive systems—that is, for devices that compute by reacting to stimuli from their environment. The main strength of such theories lies in the equational (calculational) style of reasoning they support. For each process theory, several natural questions immediately arise pertaining to the (non-)existence of (finite or recursive) sets of laws that allow one to prove by “substituting equals for equals” all of the valid equalities between process descriptions (closed or open terms) over fragments of the process theory at hand. Currently, answering such questions is only possible via delicate, error-prone and lengthy proofs.

The aim of the project is to contribute further advances to the study of the meta-theory of algebraic theories of processes. The main goals of the project are

to establish a generic framework for answering questions pertaining to the existence of equational axiomatizations of behavioural semantics over process algebras affording certain desirable properties, such as being finite or recursive, and
to apply the proposed general theory to solve some of the main open problems in the study of the equational logic of processes.

Research environment

The research within the project will be carried out in close collaboration with our long-term co-workers Wan Fokkink (VU Amsterdam), Bas Luttik (TU Eindhoven), MohammadReza Mousavi (TU Eindhoven) and Michel Reniers (TU Eindhoven).

The successful candidates will benefit from, and contribute to, the research environment at the Icelandic Centre of Excellence in Theoretical Computer Science (ICE-TCS). ICE-TCS has currently 14 permanent members, seven postdoctoral researchers and one Ph.D. student. For more information about ICE-TCS, its members and its activities, see http://www.icetcs.ru.is/.

Qualification requirements

Applicants for the PhD studentships should have a good MSc degree in Computer Science, Mathematics or closely related fields, and have a strong background in discrete mathematics and formal systems. Some previous knowledge of topics from at least one of concurrency theory, process calculi and structural operational semantics is not a prerequisite, but would be desirable.

Remuneration

PhD position: 265,000 ISK (roughly 1,550 euros) per month before taxes, for three years, starting as early as possible and no later than October 2010.

Application details

By Friday, 26 February 2010, interested applicants should send their CV, including a list of publications where applicable, in PDF to the addresses below, together with a transcript of their academic record, a statement outlining their suitability for the project and the names of two referees.

Luca Aceto
email: luca@ru.is

Anna Ingolfsdottir
email: annai@ru.is

We will start reviewing applications as soon as they arrive, and will continue to accept applications until the positions are filled. However, we strongly encourage interested applicants to send in their applications as soon as possible.

About the School of Computer Science at Reykjavik University

The School of Computer Science at RU (http://www.reykjavikuniversity.is/computer-science/) has approximately 440 students at the undergraduate, masters and doctorate levels. The School is home to several strong research groups and the main research areas are algorithmics, artificial intelligence, combinatorics, concurrency theory, databases, human-computer interaction, natural language processing, software engineering, theoretical computer science and virtual environments.

The School of Computer Science at Reykjavik University has ties with several leading foreign universities, facilitating collaboration, as well as faculty and student exchanges. In particular, the School has a joint M.Sc. degree in Computer Science with the University of Camerino, Italy, and a joint Ph.D. degree programme with KTH, Stockholm, Sweden.

Information about Ph.D. studies at the School of Computer Science is available at

http://www.reykjavikuniversity.is/departments/school-of-computer-science/ph.d-studies/

Concurrency Column for the February 2010 Issue of the BEATCS

2010-01-17T21:54:00.000Z

I have just posted the paper for the concurrency column that will appear in the February 2010 Issue of the BEATCS. This installment of the concurrency column is devoted to a very informative survey, contributed by François Laroussinie, of recent work on the modelling and specification of open systems using games and alternating-time temporal logics. In particular, the paper focuses on fundamental semantic questions for those specification formalisms, such as the kind of properties that can be stated in various types of logics for games, and on the computational complexity of their model-checking problems. Enjoy it!

My New Workplace

2010-01-08T23:47:00.000Z

The School of Computer Science has moved into its premises in the new building of Reykjavik University. The building is still a construction site, and will remain so for a few more months at least. You can see some photos here. There is no doubt that the building looks good. However, I am not so sure that it will offer the best working conditions for academic work. For instance, as a consequence of the downsizing of the building because of the economic crisis in Iceland, we have no offices and we are all sitting in an open space. (I'll try to post a photo of the TCS area when I get a chance to take one.)

I am not passing judgement yet on the effect that this will have on my work. The next few weeks will allow me to form an opinion on this issue. I will try to keep an open mind and to make the most of what I have available. However, it is hard to escape the nagging thought that I had a quieter working environment when I was a Ph.D. student.

Stay tuned for more information.

Job Announcement: Dean of the School of Computer Science at Reykjavík University

2009-12-30T22:16:00.000Z

The School of Computer Science at Reykjavík University, my own stamping ground, is seeking a new dean. Our present dean, Ari K. Jónsson, will take over the rectorship of the university on January 23, 2010, and we are looking for excellent candidates to take over the deanship of the school. (The dean has direct responsibility for academic, administrative and fiscal operations of the School of Computer Science. The dean is part of the executive committee of the university and reports directly to the rector.)

The School of Computer Science hosts several active research groups and its main research areas are artificial intelligence, combinatorics, databases, human-computer interaction, natural language processing, software engineering, theoretical computer science and virtual environments.

The job announcement is here. Is any of you out there interested in applying for the job?

A Question on the Structure of Fields, Centres and Committees

2009-11-13T09:22:00.000Z

Can anyone briefly explain to me, or point me to on-line information about, the raison d'être and operating characteristics of structures like the fields and centres at Cornell and MIT, or the interdisciplinary committees found at the University of Chicago?

I am asking wearing my hat of the chairman of the research council of my university, where we are mulling about the possibility of having similar structures. Thanks in advance for any information you might be able to provide!

Tony Hoare on Industrial vs. Pure Research

2009-11-05T10:30:00.000Z

I have just read a very cogent retrospective piece that Tony Hoare has written for the October 2009 issue of CACM to mark the 40th anniversary of the publication of his seminal paper An axiomatic basis for computer programming. (This is the first article he wrote as an academic. Not a bad way to start, is it?) It is a read that I thoroughly recommend and that I'll make available to the students who are now taking my course on the semantics of programming languages. I am posting an excerpt from that viewpoint article on industrial vs. pure research in computer science since it may be of interest to readers of this blog. I pass the word to Tony.

"Pure academic research and applied industrial research are complementary, and should be pursued concurrently and in collaboration. The goal of industrial research is (and should always be) to pluck the 'low-hanging fruit'; that is, to solve the easiest parts of the most prevalent problems, in the particular circumstances of here and now. But the goal of the pure research scientist is exactly the opposite: it is to construct the most general theories, covering the widest possible range of phenomena, and to seek certainty of knowledge that will endure for future generations. It is to avoid the compromises so essential to engineering, and to seek ideals like accuracy of measurement, purity of materials, and correctness of programs, far beyond the current perceived needs of industry or popularity in the market-place. For this reason, it is only scientific research that can prepare mankind for the unknown unknowns of the forever uncertain future.

So I believe there is now a better scope than ever for pure research in computer science. The research must be motivated by curiosity about the fundamental principles of computer programming, and the desire to answer the basic questions common to all branches of science: what does this program do; how does it work; why does it work; and what is the evidence for believing the answers to all these questions? We know in principle how to answer them. It is the specifications that describe what a program does; it is assertions and other internal interface contracts between component modules that explain how it works; it is programming language semantics that explains why it works; and it is mathematical and logical proof, nowadays constructed and checked by computer, that ensures mutual consistency of specifications, interfaces, programs, and their implementations. There are grounds for hope that progress in basic research will be much faster than in the early days. I have already described the vastly broader theories that have been proposed to understand the concepts of modern programming. I have welcomed the enormous increase in the power of automated tools for proof. The remaining opportunity and obligation for the scientist is to conduct convincing experiments, to check whether the tools, and the theories on which they are based, are adequate to cover the vast range of programs, design patterns, languages, and applications of today's computers. Such experiments will often be the rational reengineering of existing realistic applications. Experience gained in the experiments is expected to lead to revisions and improvements in the tools, and in the theories on which the tools were based. Scientific rivalry between experimenters and between tool builders can thereby lead to an exponential growth in the capabilities of the tools and their fitness to purpose. The knowledge and understanding gained in worldwide long-term research will guide the evolution of sophisticated design automation tools for software, to match the design automation tools routinely available to engineers of other disciplines."

Amir Pnueli Dies

2009-11-03T09:11:00.000Z

I just learned via a posting on the TYPES mailing list the sad news that Amir Pnueli, one of the inspirational and leading figures in several areas related to the formal specification and verification of computing systems, passed away yesterday at age 68. An email message circulated yesterday by his family states that "Amir has suffered a serious brain hemorrhage which he could not recover from. He passed away today [2 November] at noon."

In 1996, Pnueli received the Turing Award for seminal work introducing temporal logic into computing science and for outstanding contributions to program and systems verification.

His scientific legacy will be felt for many years to come.

Benchmarking Metrics: What and Why?

2009-10-23T15:56:00.001Z

In his post entitled "Top 10 theory schools?", Jonathan Katz gives a list of what he considers to be the top 10 theory departments in the US. (Read the post and the comments for an update on the discussion.) One of the comments reads as follows:

I would agree about:

MIT (Silvio, Shafi, Ron, Michel, …)
Cornell (Rafael, Eva, Jon, Bobby,…)
Berkeley (Luca, Christos, Umesh,…)
CMU (Venkat, Manuel, Avrim, Ryan,…)
Princeton (Boaz, Sanjeev, Moses, Bernard,..)

The others are a bit flakier:

GA Tech (Santosh, Chris, Vijay, Sasha, …)
UT Austin (Adam, David, Brent)
UCSD (Mihir, 1/4 Russell, Daniele, maybe Hovav)
U Washington (Anna, Paul, Anup)

I would say at least he following schools are VERY comparable to above:

Stamford (Dan, Serge, Tim, Amin,…)
NYU (Subhash, Assaf, Yevgeniy, Richard, …)
Harvard (Salil, Michael(s), Leslie)
Columbia (Mihalis, Rocco, Tal)

I would say there are top 5, and then top 10 following them.

So this commentator measures the quality of a theory group using the perceived research quality of the very best researchers at a given institution. Another possible metric would be the size of the group of active researchers with high international visibility. Yet others could be the number of peer-reviewed publications in top-class journals and conferences, or the average such number per staff member.

What criteria are most useful and why (bearing in mind that, at the end of the day, we are always making subjective judgements)? I am interested in this topic since the School of Computer Science I am working at is presently undertaking a benchmarking exercise. The aim of the exercise is to find three to four departments in the Nordic countries with which we aim at comparing ourselves in the very short term, within five years and within 10-15 years. One of the interesting aspects of this exercise is that our school is substantially smaller than most of the departments elsewhere. So, what do you think would be good metrics for the benchmarking exercise? Standing of the top scientists within the school? Average number of peer-reviewed publications and citations? Or what?

EATCS Award 2010: Call for Nominations

2009-10-22T11:37:00.000Z

The Call for Nominations for the EATCS Award 2010 has been published (see this pdf). Nominations and supporting data should be sent to the chairman of the EATCS Awards Committee, Emo Welzl. The next award is to be presented during ICALP'2010 in Bordeaux. The deadline for nominations is: December 15, 2009. So get your act together quickly and nominate one of the many "obvious suspects" for the award!

Note that nominations are now kept alive for three years. Since I sent in an unsuccessful nomination last year, I don't need to do anything this time around and will just be a very interested observer :-)

I wish the award committee the best of luck with their work.

Five Years of Logical Methods in Computer Science

2009-10-16T09:32:00.000Z

I have received this letter via email. I post it here since I strongly support journals like LMCS and I encourage my readers to submit good papers to it. Happy birthday LMCS! May your reputation grow with the years.

Dear Colleague:

We would like to bring the community up to date on the journal

Logical Methods in Computer Science
www.lmcs-online.org

We started this fully refereed, open access, free electronic journal in January 2005, intending to create a high-level platform for publications in all theoretical and practical areas in computer science involving logical methods, taken in a broad sense. We are now on Issue 3 of Volume 5 (there are four issues a year). So far, we have received more than 350 submissions of which we have published 162. In addition to individual submissions, our journal publishes special issues, e.g., of selected papers of high-level international conferences such as LICS, IJCAR, CAV, CSL, and RTA.

We are continuing actively to develop the journal. For example, we accept survey articles, and are developing `live' surveys, which can be continually updated as knowledge progresses. In another direction, we are considering allowing authors to provide additional material of an expository nature, such as slides and videos, to enable them to interest a wider spectrum of readers in their contribution.

The journal is an overlay of CoRR, the computer science repository of arXiv. There are no fees for authors nor for readers. Every paper is refereed by two or more referees, and high standards are applied. The editorial board consists of about sixty top specialists in all areas of logic in computer science.

The journal is covered by Mathematical Reviews, the ISI Web of Knowledge, and the DBLP Database.

We welcome your comments and suggestions, and we seek your contributions! For more information please consult our web pages:

www.lmcs-online.org

Yours,

Editor-in-Chief: Dana S. Scott <dana.scott@cs.cmu.edu>
Managing Editors: Benjamin C. Pierce <bcpierce@cis.upenn.edu>
Gordon D. Plotkin <gdp@inf.ed.ac.uk>
Moshe Y. Vardi <vardi@cs.rice.edu>
Executive Editors: Jiri Adamek <adamek@iti.cs.tu-bs.de>
Stefan Milius <s.milius@tu-bs.de>

IFIP 1.8 workshop on FORMAL METHODS FOR EMBEDDED SYSTEMS

2009-10-12T09:14:00.000Z

I have received the following announcement from Bas Luttik. I am happy to post it here since the event will be of interest to concurrency theorists and people working on formal methods at large, many of whom will be in Eindhoven for FM week. (Not to mention the fact that I am the outgoing chair of IFIP WG 1.8.)

==============================

========================================
CALL FOR PARTICIPATION
======================================================================
IFIP 1.8 workshop on FORMAL METHODS FOR EMBEDDED SYSTEMS

http://www.cse.unsw.edu.au/~rvg/FMES/

Eindhoven, The Netherlands, November 5, 2009
======================================================================

This IFIP 1.8 workshop is organised as part of the Formal Methods Week,
which takes place in Eindhoven from November 2 until November 6, 2009.
The goal of the workshop is to summarise research from different areas
of formal methods targeted to embedded systems, and to promote the use
of formal methods in different applications and in the engineering
discipline for embedded systems.

PROGRAMME:
----------
8:30 Registration and coffee
8:50 Opening

9:00 Bert van Beek -
The Compositional Interchange Format: concepts, formal basis,
and applications
9:45 Holger Hermanns -
Synchronous vs. Asynchronous Performance Models of Industrial
Networks on Chip Designs

10:30 Coffee break

11:00 Catuscia Palamidessi -
Synchronization in the pi-calculus
11:45 Joost-Pieter Katoen -
Analysis and Semantics of Extended AADL Models

12:30 Lunch
14:00 The End

For abstracts of the talks and further details about the workshop we
refer to http://www.cse.unsw.edu.au/~rvg/FMES/.

REGISTRATION
------------
The registration fee for the workshop is 45 euros and covers coffee/tea
and lunch. You also need to register for FMweek, which costs an
additional 35 euros (administration costs). Please register via the
FMweek website: http://www.win.tue.nl/fmweek

WORKSHOP ORGANISERS:
---------------------
Rob van Glabbeek (National ICT Australia)
Ursula Goltz (Technical University Braunschweig, Germany)
Bas Luttik (Technische Universiteit Eindhoven, The Netherlands)
Uwe Nestmann (Technical University Berlin, Germany)

Presburger Award

2009-10-08T18:44:00.001Z

In an old post I announced that the EATCS was about to initiate a young researcher award. I am happy to see that the call for nominations for the first Presburger Award has now been advertised. See here for the details. The award is meant for scientists in TCS who are 35 or younger.

The award is named after Mojzesz Presburger who accomplished his ground-breaking work on decidability of the theory of addition (which today is called Presburger arithmetic) as a student in 1929.

The award includes an amount of 1000 € and an invitation to ICALP 2010 for a lecture.

I hope you will take the time to nominate young scientists for the award. Who would be your favourite candidates?

Treatment of Alan Turing was “appalling”

2009-09-12T23:00:00.002Z

Arnar Birgisson, a former MSc student of mine who is now a PhD student at Chalmers, pointed out to me that last Thursday Gordon Brown issued a statement "recognising the “appalling” way he [Alan Turing] was treated for being gay." The piece of news may be found here.

It is understandable that Gordon Brown's statement focuses on Turing's work on breaking the German Enigma codes. However, I find it suprising that Turing's role in the development of computer science does not deserve any mention at all in the apology.

The statement ends as follows:

"So on behalf of the British government, and all those who live freely thanks to Alan’s work I am very proud to say: we’re sorry, you deserved so much better."

So long, and thanks for breaking the Enigma code, devising the Turing machine and the universal Turing machine, building some of the earliest programmable computers and all the rest.....

Nominations for the Gödel Prize 2010

2009-09-10T13:52:00.002Z

The Call for Nominations for the 2010 Gödel Prize has been posted (see this pdf file). The 2010 Award Committee consists of Cynthia Dwork (Microsoft Research), Johan Håstad (KTH Stockholm), Jean-Pierre Jouannaud (INRIA and Tsinghua University; chair), Mogens Nielsen (University of Aarhus), Mike Paterson (University of Warwick) and Eli Upfal (Brown University). The deadline for nominations is 31 January, 2010.

I hope that the volume B community will nominate some excellent papers to give the very strong volume A papers a run for their money :-) What papers would you nominate? Post a comment with your favourite candidates. Perhaps you can garner some support for them, leading to an actual nomination for the prize.

I will try to post some suggestions myself when my list of things to do shrinks to an acceptable level. (Fat chance, alas.)

Tom Henzinger: The First President of IST Austria

2009-09-08T13:11:00.004Z

Last Sunday night I came back to Iceland after a thoroughly enjoyable stay in Bologna for CONCUR 2009, SOS 2009 and the 16th EXPRESS workshop. This was a welcome opportunity to see many friends and colleagues, letting alone visiting my home country and a pretty city like Bologna.

I hope to find some time to report on the conference, not least to pay tribute to the great work done by the local organizers and their team (with special thanks to Christian, Cinzia, Ferdinanda, Jacopo and Jorge). With the start of the teaching period approaching fast and a pile of chores to catch up on, here I'll just limit myself to mentioning a piece of news that I learned at the conference while discussing with Krishnendu Chatterjee. From 1 September, Tom Henzinger is the first President of the Institute of Science and Technology (IST) Austria in Klosterbeuburg. You can read the official press release here.

The aim of the institute, which is richly funded by the Austrian government, is "to become a world-class research center offering, by 2016, an international, state-of-the-art environment for approx. 500 scientists and doctoral students." This commitment to excellence and to basic research is witnessed already by the first few hires IST has made and things can only improve under Tom's presidentship.

I wish Tom and IST the best of luck. It is great to see Austria invest on basic research with the creation of such an institute, which is already bringing to Europe top-class scientists like Herbert Edelsbrunner (the only computer scientist to have won the National Science Foundation's Alan T. Waterman Award) and researchers of exceptional promise like Krishnendu. Moreover, it is really awesome to see one of us be chosen as the leader of such an institute.

In Bologna I also guessed correctly that Tom is the scientist with the largest number of papers during the first 20 years of CONCUR (21 papers overall). I have every reason to believe that Tom Henzinger will continue to contribute to research in concurrency theory even as president of IST.

CAV Award 2009

2009-07-12T22:06:00.002Z

Does any of my readers know who received the 2009 CAV Award? The conference ended on July 2, but the web page has not been updated with that information.

Post a comment if you know who the recipient of the award was.

A Look at my Crystal Ball

2009-06-30T21:32:00.002Z

Let me make an attempt at predicting the winner(s) of the LICS Test-of-Time Award for 2009.

According to the rules of the award, the prize will go to a paper that was presented at LICS 1989 in lovely Asilomar. I was there as a second-year Ph.D. student and I presented a paper myself, but it was not award material.

The conference programme was really good and the award committee must have had a difficult choice. I do not know who will receive the award in mid-August, but let make a personal prediction: the award will be shared by the following two papers:

What papers do you think will receive the award? It will be interesting to look back at the predictions and see who was right.

Arthur Benjamin's Proposal for Changing Maths Education

2009-06-30T07:50:00.004Z

See this video, pointed out to me by my recently graduated M.Sc. student Arnar Birgisson. It is well worth spending three minutes looking at.

I guess that many readers of this blog will like the message in this position video :-)

ICE-TCS Theory Day 2009

2009-06-23T16:15:00.002Z

Last Friday, ICE-TCS hosted its fifth annual theory day. This is an event we organize each year to advertise TCS to the local scientists and students, usually in connection with visits by guests of the centre from outside Iceland. (The list of previous guest speakers includes Thomas Erlebach, Wan Fokkink, Ryan Hayward, Jan Kratochvil, Kim G. Larsen, MohammadReza Mousavi, Mogens Nielsen and Moshe Vardi.)

The programme for this year's event is here. We had a keynote address delivered by Zoltan Esik, who presented work on regular words and linear orders, which may be found in, e.g., this paper of his. The session devoted to algorithms saw two excellent talks by the Halldórsson brothers on algorithms for detecting genomic copy variations and on scheduling wireless networks. (The latter talk was based on a paper that will be presented at ICALP 2009.) The scientific programme was brought to a close by two talks by PhD students, who are the future of TCS. Paul van Tilburg (Eindhoven University of Technology, NL) described some of the results he has achieved in his research work so far, which aims at connecting the time-honoured theory of automata with the theory of processes. Matteo Cimini (a PhD student I am supervising with Anna Ingolfsdottir) explained the Curry-Howard isomorphism, which is one of the pearls of TCS, to all of us in a clear way.

The event was followed by wine, pizza and a social gathering. The only happening that marred our celebration of TCS is a 6% salary cut that was announced by our rector during the session in the programme devoted to algorithms.

"May you live in interesting times" says an old Chinese curse. These are definitely interesting times here in Iceland, alas. However, despite the lack of resources, ICE-TCS will try to keep waving the flag of TCS on the island as far as it can. If you happen to be in Iceland and you wish to drop by and give a talk in our seminar series, drop us a line.

Concurrency column for the June 2009 issue of the BEATCS

2009-06-11T22:08:00.002Z

Last month I submitted the concurrency column for the June 2009 issue of the BEATCS to the editor in chief. The piece is entitled Deriving labelled transition systems --- a structural approach and has been contributed by Julian Rathke and Pawel Sobocinski.

The paper reports on recent results obtained by the authors in their ongoing research effort whose aim is to contribute to the development of a general theory for the systematic derivation of a labelled transition semantics for a process calculus from a simpler, non-structural, description of the reduction semantics.

I think that we can expect to hear further developments on this line of work soon, but the authors already have a good story to tell and the paper they contributed to the BEATCS witnesses this fact.

Thanks to Julian and Pawel for their efforts in putting this good paper together!

Announcing LIPIcs, a new series of electronic conference proceedings in computer science

2009-06-06T10:35:00.002Z

I just saw the appended message on the concurrency mailing list. I think that it will be of interest to readers of this blog. Much is afoot in the area of open-access conference and workshop proceedings and I guess that several events will consider publishing their proceedings in this series.

----

Dear colleagues,

Following an initiative of the conferences STACS (http://stacs-conf.org) and FSTTCS (http://www.fsttcs.org/), to opt for non-commercial, electronic proceedings, the German conference center Schloss Dagstuhl Leibniz Center for Informatics (LCI) has decided to establish a new series of conference proceedings called Leibniz International Proceedings in Informatics (LIPIcs,http://www.dagstuhl.de/en/publications/lipics/). The objective of this series is to publish the proceedings of high-quality conferences in all fields of computer science. An Editorial Board is being instituted to oversee the selection of the conferences to be included in this series.

Details about joining this serie and about the editorial process can be found on-line, http://www.dagstuhl.de/fileadmin/redaktion/DROPS/LIPIcs/lipics_announce.pdf. The main features are as follows:
The proceedings in the LIPIcs series will be published electronically and will be accessible freely and universally on the internet, keeping the copyrights with the authors, and under an open access license guaranteeing free dissemination. To face the cost of electronic publication, a one-time fee will be required from the conference organizers. This fee will be kept to a minimum, intended to cover the costs of LCI, thanks in particular to a sharing of the workload between LCI and the conference organizers.

The LCI and the LIPIcs Editorial Board wish to attract the best conferences in computer science, and they hope you can encourage steering and program committees to join it!

Pascal Weil
LaBRI - CNRS
351 cours de la Libération
33405 Talence Cedex - France

pascal.weil@labri.fr
http://www.labri.fr/~weil

EPTCS, a new open access proceedings series

2009-04-30T13:39:00.002Z

I have received the following message from Rob van Glabbeek, which I am very happy to post on this blog. I encourage readers of this blog to spread the announcement at their own institutions and to post it on their blogs, if they have any. I like to think that this new series of open access proceedings will offer the TCS community a good service. Of course, only time will tell whether this will happen, but I feel that the time is ripe for such initiatives in the TCS community. Spread the news!

With this posting, we are launching

   Electronic Proceedings in Theoretic Computer Science (EPTCS)

a new international refereed open access venue for the rapid
electronic publication of the proceedings of workshops and
conferences, and of festschrifts, etc, in the general area of
theoretical computer science, broadly construed.

We do not charge authors or event organisers for electronic
publication in EPTCS in any way. If hard-copies of proceedings are
desired, event organisers have the choice of organising the printing
themselves or taking advantage of a standard contract we will make
with a printing house. Copyright on all papers is retained by the
author, and full-text electronic access to all papers is freely
available, without any need for registration or subscription.

Permanent archival of EPTCS publications is ensured by organising
EPTCS as an overlay of the Computing Research Repository (CoRR): see
arXiv.org. The content of EPTCS will be indexed by DBLP.

Only original papers will be considered for publication in EPTCS:
manuscripts are accepted for review by an EPTCS conference or workshop
with the understanding that the same work has not been published, nor
is presently submitted, elsewhere. However, full versions of extended
abstracts published in EPTCS, or substantial revisions, may later be
published elsewhere.

The submission and refereeing process is handled entirely by the
organisation of the conference, workshop or festschrift to which the
paper is submitted. Our editorial board carefully selects which
workshops and conferences can be trusted to select scientific papers
of quality only, and only those events will be granted a contract to
fill a volume of EPTCS.

Our editorial board consists of:

Luca Aceto  Rob van Glabbeek Gordon Plotkin  
Rajeev Alur  Lane A. Hemaspaandra Vladimiro Sassone 
Krzysztof R. Apt Matthew Hennessy Robert H. Sloan  
Lars Arge  Bartek Klin  Wolfgang Thomas  
Ran Canetti   Evangelos Kranakis Irek Ulidowski  
Luca Cardelli  Shay Kutten  Dorothea Wagner  
Rocco De Nicola  Nancy Lynch  Martin Wirsing  
Jose' Luiz Fiadeiro Aart Middeldorp  Moti Yung  
Wan Fokkink  Benjamin Pierce     

Further information can be found on our website:

     http://eptcs.org/.

In the hope this initiative will benefit the theoretical computer
science community,

Rob van Glabbeek
(Editor in Chief)