It is a great pleasure for me to post some answers by my old mate Rance Cleaveland to the questions raised at the CONCUR workshop. Thanks to Rance for sharing his experience with us!
What an interesting workshop; I deeply regret not being able to attend.
At Luca's gentle suggestion ;-) I thought I would have a go at questions he posed at the end of his post.
What is the role/importance of real-time in modelling? Does industry want dense-time or discrete-time models?
In my experience with Reactis, my company's testing and verification tool, Reactis customers absolutely need real-time support. This is due to their applications, which are in automotive and aerospace and develop embedded control software. The most widely used commercial modeling languages (Simulink, Stateflow, SCADE) also include real-time as an intrinsic part of their semantics.
Ironically, given the sound and fury in the academic community, the industrial people I have interacted with for the most part do not care whether time is discrete or continuous. Sometimes, I have encountered customers who want to do hybrid-systems style modeling, and for these people continuity is important.
How does one involve small- and medium-size companies in collaborations with concurrency theoreticians/practitioners? Does "company size" matter?
Regarding SMEs (small- and medium-size enterprises ... a common acronym among US policymakers): I think the best way to involve them is via projects funded by third parties (governments, or a large partner). SMEs generally don't have the overheads to support "blue-sky" research, and their investment-return horizons are necessarily of shorter duration. At both Reactive Systems and Fraunhofer, our concurrency-oriented SME collaborations have either involved collaborations on government research grants or project work on behalf of larger customer. In the latter cases, it was important that we work in commercial notations (e.g. Simulink) rather than research-oriented ones.
Large companies do have resources to put into more basic research, but there is another phenomenon to be aware of: researchers in these companies often view outside researchers as competitors for their internal research funds. So collaborations with these organizations are highly dependent on the personal connections between company and non-company researchers. So-called "business unit" personnel are often the easiest to deal with, but in this case there needs to be a clear, typically short-term, pay-off to them for the collaboration.
Is there any need for stochastic and probabilistic modelling in applications? More pointedly, have you met an example that you could not model because your tool does not support stochastic or probabilistic phenomena?
We support simple probabilistic modeling in Reactis in the form of probability distributions over system inputs that we sample when creating tests. This feature, however, is almost never used by our customers. The reasons for this mostly boil down to a lack of training these engineers receive in stochastic modeling and control, which in turn is tied into the lack of good (or maybe standard) theory for stochastic differential equations.
More precisely, the engineers in automotive and aero that I've dealt with are usually mechanical or electrical engineers with backgrounds in control theory. The feedback control they use relies on plant models (i.e. "environments") being given as differential equations, which are deterministic. The plant models they devise for testing their control-system designs often have parameters that they tweak in order to test how their ideas work under different conditions.
These engineers talk in the abstract about how useful it would be to develop analytical frameworks for probabilistic plants, but tractable theories of probability spaces of differential equations are unknown, as far as I can tell.
How can we, as a community, foster the building of industrial-strength tools based on sound theories?
To have an industial following, tools have to work with languages that industry uses. For most research tools this is a problem, because the input languages are typically invented by the tool developers.
I see two possibilities. One is to work on commercial languages such as Simulink. These languages are often a catastrophe from a mathematical perspective, but they also usually contain subsets that can be nicely formalized for the purposes of giving tool support. If tools have a nice "intermediate notation" into which these cores can be translated, then this offers a pathway for potential industrial customers to experiment with the tools.
The second approach is to become involved in standardization efforts for modeling languages. UML 2.0 has benefited to some extent from concurrency theory, but there are many aspects of that language that remain informal and imprecise.
What has concurrency theory offered industry so far? What are the next steps that the concurrency community should take in order to increase the impact of its research in an industrial setting? And what are future promising application areas for concurrency research?
I think the best way to answer first question is to "trace backward" from commercial tools / modeling languages that have some basis in concurrency. Such tools would include those based on Statecharts (Stateflow, STATEMATE, BetterState); others based on Message Sequence Charts (Rational Rose, other UML tools); the French synchronous-language tools (SCADE, Esterel); tools that include model checkers (the EDA = "electronic design automation" industry); tools that use model-checking-base ideas for other analyses (Reactis, DesignVerifier).
Unfortunately the process-algebra community has had relatively little impact on commercial tool development. This is not due to shortcomings in the theory, in my opinion, but in the inattention that compositionality continues to receive in the (non-research) modeling community. In my experience, event-based modeling is also relatively uncommon, at least in auto and aero: sampling of "state variables" is the preferred modeling paradigm.
I personally would like to see work on semantically robust combinations of specification formulas (e.g. MSCs + state machines, or temporal logic + process algebra) and related tools; theoretically well-founded approaches to verifying systems that use floating-point numbers; and compositional, graphical modeling languages (lots of work done already, but still no commercial interest).
Friday, September 14, 2007
Moshe Vardi's Answers
Moshe Vardi has kindly sent me some brief answers to the questions I posted yesterday. I post them here in order to foster further discussion, and thank Moshe for his contribution.
important, but I personally saw, so far, no application that required
dense-time reasoning. (Perhaps timing analysis of circuits requires dense
time?)
often the work of a single graduate student. Industry can put several PhD-level people on a single project.
conceived, is model checking and the development of synchronous languages. At the same time, many research direction in concurrency theory, such as process calculi and bisimulation theory have had fairly minimal impact. The theory community is often attracted to research based on its theoretical appeal, which does not always correlate with its industrial applicability. This does not mean that industrial applicability should be the guiding principle of research. Nevertheless, it would be worthwhile to pause once in a few years and examine the potential applicability of
theoretical research.
- What is the role/importance of real-time in modelling? Does industry want dense-time or discrete-time models?
important, but I personally saw, so far, no application that required
dense-time reasoning. (Perhaps timing analysis of circuits requires dense
time?)
- How does one involve small- and medium-size companies in collaborations with concurrency theoreticians/practitioners? Does "company size" matter?
- Is there any need for stochastic and probabilistic modelling in applications? More pointedly, have you met an example that you could not model because your tool does not support stochastic or probabilistic phenomena?
- How can we, as a community, foster the building of industrial-strength tools based on sound theories?
often the work of a single graduate student. Industry can put several PhD-level people on a single project.
- What has concurrency theory offered industry so far? What are the next steps that the concurrency community should take in order to increase the impact of its research in an industrial setting? And what are future promising application areas for concurrency research?
conceived, is model checking and the development of synchronous languages. At the same time, many research direction in concurrency theory, such as process calculi and bisimulation theory have had fairly minimal impact. The theory community is often attracted to research based on its theoretical appeal, which does not always correlate with its industrial applicability. This does not mean that industrial applicability should be the guiding principle of research. Nevertheless, it would be worthwhile to pause once in a few years and examine the potential applicability of
theoretical research.
Thursday, September 13, 2007
Report on the WG1.8 Workshop at CONCUR 2007---Part 1
Preface
As you may know, Jos Baeten, Wan Fokkink, Anna Ingolfsdottir, Uwe Nestmann and I organized a Workshop on Applying Concurrency Research in Industry, co-located with CONCUR 2007 in Lisbon, on behalf of WG1.8. The workshop was held on the afternoon of Friday, 7 September, and ran concurrently with the last two sessions of the main conference. Despite the competition with CONCUR, we had about 25 participants at the workshop, including several members of the working group. I think that this was a rather decent level of attendance for a "strategic event".
In this post, for the benefit of the WG members and of the community as a whole, I'll try to summarize the main discussion points that were raised during the presentations at the workshop and the ensuing panel discussion. I will also try to recall some of the questions that the audience asked the panel members. I hope that some of blog readers will want to contribute their opinion on these points and give their own answers to those questions themselves.
The organizers of the workshop will use all of the contributions that they'll receive in putting together an article for the concurrency column of the BEATCS.
Report on the Invited Talks
Note: I encourage the speakers to correct anything they said that I may have misinterpreted or misrepresented. I take full responsibility for any error I might have made in relaying the gist of the invited talks, and I'll be happy to post corrections and further comments. This is meant to be a live repository.
The workshop began with four invited presentations delivered by Hubert Garavel, Vincent Danos, Kim G. Larsen and Jan Friso Groote.
Hubert gave an overview of his twenty-year work on the CADP tool set, which is the oldest concurrency-theoretic tool still in activity. A thread underlying his work in what he called "applied concurrency theory" is that one must push the main results of our research area to industry and that this is only possible with the development of strong tool support for our methods. Hubert said that one of his design principles has been to restrict the tool's functionality for efficiency reasons, and that elegant semantics and efficient execution are two separate (at times conflicting) issues.
I have a note to the effect that, during Hubert's presentation, somebody (possibly Hubert himself) said that a lot of code doing bisimulation minimization has been lost over the years. We simply have not been consistent enough in preserving some of our earlier tooling efforts for the present generations of developers. Jan Friso said that current bisimulation minimization algorithms do not scale up to the size of the systems that are currently being analyzed, and asked whether it would be appropriate to rekindle research and implementation efforts on efficient and scalable bisimulation algorithms.
Earlier that day, Vincent had delivered an inspiring tutorial on his work in doing rule-based analysis of biological signalling. Listening to his tutorial, I was left with the impression that he is really having an impact in the life sciences, and that experimental biologists might very well use his tools based on concurrency-theoretic ideas. At the workshop, Vincent presented another way in which concurrency-theoretic ideas can help experimental biologists in their work. Experimental biology has a huge knowledge representation problem. (Vincent mentioned that there are two papers published in that area each minute!) In his opinion, experimental biologists can/should
Kim's talk was based on his experience with the ten-year development of the Uppaal tool, and reported on the knowledge transfer activity, which is part of his involvement in CISS. Apart from surveying the development of Uppaal and its recent offsprings, Kim's talk sent out the following general messages to the audience.
Some Questions to the Speakers
Here are some questions that were addressed to the speakers during the panel discussion, in no particular order. I encourage readers of this report to post their own answers and further questions as comments to the post. Later on, I will post the answers from the panel members as I recall them.
Addendum 14/9/2007: After I wrote this post, it occurred to me that the workshop discussion may have given the impression that industrial impact can solely be achieved by means of tools and joint case studies. Moshe Vardi's work on specification languages like ForSpec on the other hand indicates that the development of theoretically sound and clean specification languages that are actually used by industry is another area in which in the community can (and I believe should) have an impact.
I hope I can quote Moshe as saying
"In fact, I believe that much of my industrial impact has been achieved through the development of clean and useful theory."
As you may know, Jos Baeten, Wan Fokkink, Anna Ingolfsdottir, Uwe Nestmann and I organized a Workshop on Applying Concurrency Research in Industry, co-located with CONCUR 2007 in Lisbon, on behalf of WG1.8. The workshop was held on the afternoon of Friday, 7 September, and ran concurrently with the last two sessions of the main conference. Despite the competition with CONCUR, we had about 25 participants at the workshop, including several members of the working group. I think that this was a rather decent level of attendance for a "strategic event".
In this post, for the benefit of the WG members and of the community as a whole, I'll try to summarize the main discussion points that were raised during the presentations at the workshop and the ensuing panel discussion. I will also try to recall some of the questions that the audience asked the panel members. I hope that some of blog readers will want to contribute their opinion on these points and give their own answers to those questions themselves.
The organizers of the workshop will use all of the contributions that they'll receive in putting together an article for the concurrency column of the BEATCS.
Report on the Invited Talks
Note: I encourage the speakers to correct anything they said that I may have misinterpreted or misrepresented. I take full responsibility for any error I might have made in relaying the gist of the invited talks, and I'll be happy to post corrections and further comments. This is meant to be a live repository.
The workshop began with four invited presentations delivered by Hubert Garavel, Vincent Danos, Kim G. Larsen and Jan Friso Groote.
Hubert gave an overview of his twenty-year work on the CADP tool set, which is the oldest concurrency-theoretic tool still in activity. A thread underlying his work in what he called "applied concurrency theory" is that one must push the main results of our research area to industry and that this is only possible with the development of strong tool support for our methods. Hubert said that one of his design principles has been to restrict the tool's functionality for efficiency reasons, and that elegant semantics and efficient execution are two separate (at times conflicting) issues.
I have a note to the effect that, during Hubert's presentation, somebody (possibly Hubert himself) said that a lot of code doing bisimulation minimization has been lost over the years. We simply have not been consistent enough in preserving some of our earlier tooling efforts for the present generations of developers. Jan Friso said that current bisimulation minimization algorithms do not scale up to the size of the systems that are currently being analyzed, and asked whether it would be appropriate to rekindle research and implementation efforts on efficient and scalable bisimulation algorithms.
Earlier that day, Vincent had delivered an inspiring tutorial on his work in doing rule-based analysis of biological signalling. Listening to his tutorial, I was left with the impression that he is really having an impact in the life sciences, and that experimental biologists might very well use his tools based on concurrency-theoretic ideas. At the workshop, Vincent presented another way in which concurrency-theoretic ideas can help experimental biologists in their work. Experimental biology has a huge knowledge representation problem. (Vincent mentioned that there are two papers published in that area each minute!) In his opinion, experimental biologists can/should
- use concurrency-inspired languages to express biological understanding and
- display this information in a wiki-type system.
Kim's talk was based on his experience with the ten-year development of the Uppaal tool, and reported on the knowledge transfer activity, which is part of his involvement in CISS. Apart from surveying the development of Uppaal and its recent offsprings, Kim's talk sent out the following general messages to the audience.
- Tools are a necessary condition for the successful transfer of concurrency-theoretic ideas in industry. Tool development is labour intensive, and one needs the sustained effort of many people over many years to produce good software tools.
- Academic courses offered to students and to industry practitioners play a key role.
- Concurrency researchers should try and target different communities of potential users. One never knows where successful applications are going to stem from.
- A good beginning is useful! Being able to start with a success story may lead to further successes and a long-term collaborations. However, Kim warned against assuming that a good beginning is a guarantee of a good ending, and recounted the story of the Aalborg collaboration with Bang and Olufsen, who disappeared from sight after Klaus Havelund, Arne Skou and Kim found and fixed a bud in one of their protocols. See here.
- The success of CISS shows that several companies are very interested in applying concurrency-theoretic ideas and tools because this reduces time to market and increases the quality of their products.
- The impact of one's work on the application of concurrency-theoretic research in industry is not always directly proportial to the amount of effort one puts into the work itself. Kim gave the example of the synthesis of control software controlling the temperature and humidity in an actual pig stable in Denmark. This software was synthesized using Uppaal Cora in a short time and is actually running to the satisfaction of its customers :-)
- Finally, Kim called for an expansion of the use of concurrency theory. We should link our work to testing, optimization etc. and embed it into standard software engineering methodologies, which are familiar to practitioners.
Some Questions to the Speakers
Here are some questions that were addressed to the speakers during the panel discussion, in no particular order. I encourage readers of this report to post their own answers and further questions as comments to the post. Later on, I will post the answers from the panel members as I recall them.
- What is the role/importance of real-time in modelling? Does industry want dense-time or discrete-time models?
- How does one involve small- medium-size companies in collaborations with concurrency theoreticians/practitioners?
- Is there any need for stochastic and probabilistic modelling in applications? More pointedly, have you met an example that you could not model because your tool does not support stochastic or probabilistic phenomena?
- How can we, as a community, foster the building of industrial-strength tools based on sound theories?
- What has concurrency theory offered industry so far? What are the next steps that the concurrency community should take in order to increase the impact of its research in an industrial setting?
Addendum 14/9/2007: After I wrote this post, it occurred to me that the workshop discussion may have given the impression that industrial impact can solely be achieved by means of tools and joint case studies. Moshe Vardi's work on specification languages like ForSpec on the other hand indicates that the development of theoretically sound and clean specification languages that are actually used by industry is another area in which in the community can (and I believe should) have an impact.
I hope I can quote Moshe as saying
"In fact, I believe that much of my industrial impact has been achieved through the development of clean and useful theory."
Tuesday, August 28, 2007
CALCO Report, Part 3
This is the third, and final, installment of the coverage of CALCO 2007 on this blog. Thanks again to Mohammad for providing reports on the first three days of the event.
The first talk on Thursday was an invited address by Barbara König. Barbara's talk gave an excellent introduction to the general ideas and results on an active area of research in concurrency theory, namely the problem of deriving labelled transition system semantics and bisimulation congruences from reduction semantics and rewrite rules. This is a line of research that has been motivated by the theory of bisimulation congruences for process calculi, most notably the pi-calculus, and where categorical techniques play a fundamental role. See, for instance, the work by Leifer and Milner, and that by Sassone and Sobocinski.
Thursday also featured some talks on modal and epistemic logics, two talks on Chu spaces, and several categorical talks, which were alas well beyond my understanding of category theory.
The invited talk on Friday was delivered by Luis Caires, one of the prime movers behind the development of spatial logics. Luis' talk introduced a logical approach to the semantics of types for concurrency and to their soundness proofs based on spatial logics. I found the ideas presented in Luis' talk very intriguing, and I am going to read his paper in the proceedings when I have some time on my hands.
The conference concluded with a session on process algebra, where both Mohammad and I gave talks. (It is not for me to comment on how successful we were :-)) In case anybody is interested, the slides for my talk are here.
I enjoyed my trip to lovely Bergen, and thank the organizers for a very well-organized event. I hope to be able to visit Bergen again in the future. You can see some photos from Bergen here. Eventually, photos from CALCO will be available here.
Let me conclude with a couple of quotes from talks given at the conference and a poem I saw engraved in Vaagsallmenningen in Bergen.
"If you spell out this definition set theoretically, it looks quite horrible, but is not so difficult." (Clemens Kupke)
"The real voyage of discovery consists not in seeking new landscapes, but in having new eyes." (Marcel Proust, cited by Radu Mardare)
"Hele sit liv,
Anicet,
skal et menneske
laere at leve.
Hele sit liv,
Anicet,
skal han og
laere at doe."
(This roughly means "All his life, Anicet, a man must learn how to live. All his life, Anicet, he must also learn how to die.")
The first talk on Thursday was an invited address by Barbara König. Barbara's talk gave an excellent introduction to the general ideas and results on an active area of research in concurrency theory, namely the problem of deriving labelled transition system semantics and bisimulation congruences from reduction semantics and rewrite rules. This is a line of research that has been motivated by the theory of bisimulation congruences for process calculi, most notably the pi-calculus, and where categorical techniques play a fundamental role. See, for instance, the work by Leifer and Milner, and that by Sassone and Sobocinski.
Thursday also featured some talks on modal and epistemic logics, two talks on Chu spaces, and several categorical talks, which were alas well beyond my understanding of category theory.
The invited talk on Friday was delivered by Luis Caires, one of the prime movers behind the development of spatial logics. Luis' talk introduced a logical approach to the semantics of types for concurrency and to their soundness proofs based on spatial logics. I found the ideas presented in Luis' talk very intriguing, and I am going to read his paper in the proceedings when I have some time on my hands.
The conference concluded with a session on process algebra, where both Mohammad and I gave talks. (It is not for me to comment on how successful we were :-)) In case anybody is interested, the slides for my talk are here.
I enjoyed my trip to lovely Bergen, and thank the organizers for a very well-organized event. I hope to be able to visit Bergen again in the future. You can see some photos from Bergen here. Eventually, photos from CALCO will be available here.
Let me conclude with a couple of quotes from talks given at the conference and a poem I saw engraved in Vaagsallmenningen in Bergen.
"If you spell out this definition set theoretically, it looks quite horrible, but is not so difficult." (Clemens Kupke)
"The real voyage of discovery consists not in seeking new landscapes, but in having new eyes." (Marcel Proust, cited by Radu Mardare)
"Hele sit liv,
Anicet,
skal et menneske
laere at leve.
Hele sit liv,
Anicet,
skal han og
laere at doe."
(This roughly means "All his life, Anicet, a man must learn how to live. All his life, Anicet, he must also learn how to die.")
Friday, August 24, 2007
CALCO Report Part 2
Here is the second report from CALCO authored by Mohammad. Enjoy!
Live Report from CALCO - Part 2 Without further ado, here is my second report from CALCO. I will only give a short report of the two interesting keynote talks presented yesterday and today.
Live Report from CALCO - Part 2 Without further ado, here is my second report from CALCO. I will only give a short report of the two interesting keynote talks presented yesterday and today.
- Tuesday: Tuesday was the first day of CALCO 2007 main conference. There were some 40-50 participants (depending on when the snapshot is taken). Till Mossakowki opened the conference by mentioning that, despite initial doubts, CALCO 2007 was indeed a success and it attracted some 57 submissions from 3 continents and 14 countries.
Stephen Bloom gave the keynote speech of Tuesday on algebraic and regular words and trees formalized as continuous $\Sigma$-algebras. He mentioned a recent result of his together with Zoltan Esik (I&C, 197(1-2):55--89, 2005) in which they present a complete axiomatization for regular words modulo isomorphism. He quoted the following interesting statement from his teacher who taught him about ordinals.
"Ordinals are the numbers you use to count apples."
- Wednesday: Glynn Winskel delivered his keynote address on symmetry and concurrency. He motivated the choice of the topic by a few examples from Petri Nets and HD Automata and Strand Spaces to the effect that the lack of a notion of symmetry blocks universal treatment of some constructions (such as unfolding). He started off by introducing event structures (surprise, surprise!) and presented their application as types (in stable domain theory) and processes (in the semantics of process algebras and Petri Nets). Subsequently (total, rigid, and open) maps on event structures were presented as ways of relating them and in particular open maps are underscored as a notion of bisimulation among event structures. Semantics of nondeterministic dataflow programs was presented as a challenge to which event structure with some sort of maps to input and output even structures, called stable spans, provide a solution. Glynn mentioned that this is the same as the idea of pro-functors, but admittedly I could not appreciate the value of this fact! After some discussion on insufficiency of stable maps, he defined an abstract notion of symmetry using (a pair of) open maps on event structures. He ran a bit out of time and could not get into concrete applications of this notion of symmetry but the moral of the story, if I understand it correctly, is that by taking symmetry into account you get more general and universal constructions (maps) that are not too fine to distinguish between symmetric objects.
To conclude my reports on CALCO, I feel obliged to thank the local organizer for the excellent organization. Luca arrived here on Wednesday afternoon and I guess we will all have the chance to read about the rest from him.
Monday, August 20, 2007
Live Report from CALCO 2007 - Part 1
This is a guest post provided by MohammadReza Mousavi. Thanks to Mohammad!
Luca kindly invited me to write a guest post in his blog on CALCO 2007: the 2nd Conference on Algebra and Coalgebra in Computer Science. It is hosted by the University of Bergen in the picturesque city of Bergen (a UNESCO world heritage sight).
I am currently sitting in CALCO-jnr, a workshop of CALCO dedicated to young researchers (mainly Ph.D. students). The CALCO-jnr workshop is being attended by some 35 participants and I find the talks quite interesting and for such a workshop, which is usually meant for work-in-progress type of presentations, of reasonably high quality.
I must admit that the more categorical talks go well beyond my knowledge of this field and thus, I just write a few sentences about the few talks that I could (partially) follow.
- Ichiro Hasuo (a bright young researcher from Kyoto University, currently on leave to do a Ph.D. with Bart Jacobs) presented a very interesting talk on the application of Microcosm principle in Concurrency Theory. The Microcosm principle states that there is an analogy between the structure of the outer world and that of its elements (and in particular, that of the inside world of a human being; see this for an application in mathematics). Ichiro (together with Bart Jacobs and Ana Sokolova) take this idea into Computer Science and use it to prove properties such as congruence of behavioral equivalences (specified by the final model of the co-algebra under consideration) and commutativity and associativity of the operators under consideration. If I understand it correctly, they define a natural transformation that maps the composition operator at the level of co-algebras (e.g., LTSs) to the semantics of the composition of the objects in the carrier of the co-algebra (e.g., sets of pairs of processes indexed with labels). A concrete and tangible application is the way the semantics of parallel composition is defined by the synchronization scheme. Their approach resembles the bi-algebraic approach to operational semantics (e.g., this). A more detailed account of their results is available from here.
- Alexandra Silva presented some thoughts on representing bi-infinite streams, i.e., sequence of the form "... a_{-1} a_{0} a_{1} ..." using other worked-out co-algebraic frameworks for infinite binary trees and infinite streams. I remember a very interesting and accessible talk of Jan Rutten in FMCO 2003 presenting the very interesting co-algebraic treatment of streams which resembles the algebraic analysis techniques we learned in high school. Jan will give a talk on a related topic tomorrow, so you may get to read more about it soon.
- Liam O'Reilly talked about CSP-CASL-Prover which is based on a framework combining CSP as the process language and CASL for algebraic specification (of data types) and thus combines process specification and data specification. Their framework is built upon other tools, namely CSP Prover, which allow for reasoning about CSP processes with CASL data types in Isabelle. Coming from Eindhoven, I wonder whether this type of work can be seen as a rival to mCRL2 toolset and if so, which one will be favored in the long run.
- Francisco Duran talked about the Maude tool environment. He introduced several tools built around Maude, including Interactive Theorem Prover, Termination Tool, and the Real-Time Maude Tool. Interestingly, a number of these tools have a web interface. There is a recent book on Maude, which can be bought from here.
- In the second talk, Dorel Lucanu introduced CIRC which is a tool for proving behavioral equivalences among (possibly infinite) processes specified in Maude.
So much for my first day of CALCO in Bergen; we will be off to a medieval castle for the reception this evening. Stay tuned for the second report!
Greetings from Bergen.
Friday, August 17, 2007
Being An Active Scientist at Age Eighty
Last Wednesday morning I took an hour to go and listen to a talk by Sigurdur Helgason at the University of Iceland. Sigurdur Helgason is one of Iceland's foremost scientists and a mathematician of great distinction, or so I am told. Suffice it to say that the American Mathematical Society have agreed to publish his collected works by some time next year---a honour that is bestowed only to true giants in mathematics.
I had the pleasure to meet Sigurdur Helgason in June 2004, when Anna and I visited Boston and MIT for Kári Ragnarsson's PhD graduation. He struck me as a very lively, curious and laid-back guy, who still enjoyed life, teaching his courses and thinking about maths despite being well over 70.
Sigurdur Helgason's talk kicked off a conference in honour of his 80th birthday. I had no chance of appreciating the technical content of the talk, but it was remarkable to see a 80-year-old man deliver such a well-planned presentation, reporting on some results he seemed to have achieved over the last four years or so. That was a truly awesome thing to witness.
What I found unbecoming was that there were no questions from the audience after the talk. Maybe the tradition in his area of maths is different from the one in TCS, but I would have expected at least the session chair to ask a token question to that great man.
Fortunately, being 80 and famous, he did not seem to be bothered!
I had the pleasure to meet Sigurdur Helgason in June 2004, when Anna and I visited Boston and MIT for Kári Ragnarsson's PhD graduation. He struck me as a very lively, curious and laid-back guy, who still enjoyed life, teaching his courses and thinking about maths despite being well over 70.
Sigurdur Helgason's talk kicked off a conference in honour of his 80th birthday. I had no chance of appreciating the technical content of the talk, but it was remarkable to see a 80-year-old man deliver such a well-planned presentation, reporting on some results he seemed to have achieved over the last four years or so. That was a truly awesome thing to witness.
What I found unbecoming was that there were no questions from the audience after the talk. Maybe the tradition in his area of maths is different from the one in TCS, but I would have expected at least the session chair to ask a token question to that great man.
Fortunately, being 80 and famous, he did not seem to be bothered!
Monday, August 13, 2007
Third ICE-TCS Theory Day
Last Friday, ICE-TCS hosted its third theory day. The programme for the event may be found here.
This year's theory day featured an inaugural professorial address delivered by Magnús M. Halldórsson, who joined my department at Reykjavík University on August 1. The addition of Magnús to our academic staff will substantially strengthen our research profile.
At the theory day, Magnús gave a talk in which he presented approximation algorithms for optimization problems when the objective function is unknown. The aim of the work he discussed during his presentation is to obtain algorithms that are guaranteed to perform reasonably well for all objective functions in the given class. He focussed on cost functions that are monotonic and concave (or, more generally, sub-additive), and presented approximation algorithms whose approximation ratio is 4 for concave functions and 6 for sub-additive ones.
Thomas Erlebach from the University of Leicester continued the "approximation theme" with a talk on network discovery problems. The work Thomas presented in his talk aims at discovering information about an unknown network (modelled as a connected undirected graph) or on verifying the correctness of network information. Thomas discussed two query models. In the former, a query at a node returns all the shortest path trees rooted at that node. In the latter, the result of a query at a node is the collection of shortest-path distances from that node. For the former type of queries, Thomas presented, for instance, a randomized O(sqroot{n log n})-competitive algorithm. For the latter query model, there is a deterministic Omega(sqroot{n}) lower bound and a randomized O(log n) lower bound. Much more can be found in the paper
Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matus Mihalak, L. Shankar Ram:
Network Discovery and Verification
IEEE Journal on Selected Areas in Communications, Vol. 24, No. 12, December 2006, pp. 2168-2181. Special issue on Sampling the Internet: Techniques and Applications.
The afternoon session was devoted to a one-hour talk by Tommi Sottinen, our new recruit in financial mathematics, and to two 25-minute talks by Silvio Capobianco and MohammadReza Mousavi. Tommi gave an accessible introduction to the mathematics underlying financial mathematics and the Black-Scholes model. Silvio reported on recent joint work with Patrizia Mentrasti and Tommaso Toffoli, and showed us how to convert certain types of cellular automata to lattice gases. Mohammad wound up a nice scientific day by giving an accessible introduction to some recent work of his aiming at a unified framework for functional and performance analysis of processes. He proposed an approach enabling a provably sound transformation from some existing stochastic process algebras, e.g., PEPA and MTIPP, to a generic form in the mCRL2 language.
This workshop marks the beginning of a very busy year for ICE-TCS, a year leading up to ICALP 2008 in Reykjavík. I hope to see you in Reykjavík for that conference!
This year's theory day featured an inaugural professorial address delivered by Magnús M. Halldórsson, who joined my department at Reykjavík University on August 1. The addition of Magnús to our academic staff will substantially strengthen our research profile.
At the theory day, Magnús gave a talk in which he presented approximation algorithms for optimization problems when the objective function is unknown. The aim of the work he discussed during his presentation is to obtain algorithms that are guaranteed to perform reasonably well for all objective functions in the given class. He focussed on cost functions that are monotonic and concave (or, more generally, sub-additive), and presented approximation algorithms whose approximation ratio is 4 for concave functions and 6 for sub-additive ones.
Thomas Erlebach from the University of Leicester continued the "approximation theme" with a talk on network discovery problems. The work Thomas presented in his talk aims at discovering information about an unknown network (modelled as a connected undirected graph) or on verifying the correctness of network information. Thomas discussed two query models. In the former, a query at a node returns all the shortest path trees rooted at that node. In the latter, the result of a query at a node is the collection of shortest-path distances from that node. For the former type of queries, Thomas presented, for instance, a randomized O(sqroot{n log n})-competitive algorithm. For the latter query model, there is a deterministic Omega(sqroot{n}) lower bound and a randomized O(log n) lower bound. Much more can be found in the paper
Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matus Mihalak, L. Shankar Ram:
Network Discovery and Verification
IEEE Journal on Selected Areas in Communications, Vol. 24, No. 12, December 2006, pp. 2168-2181. Special issue on Sampling the Internet: Techniques and Applications.
The afternoon session was devoted to a one-hour talk by Tommi Sottinen, our new recruit in financial mathematics, and to two 25-minute talks by Silvio Capobianco and MohammadReza Mousavi. Tommi gave an accessible introduction to the mathematics underlying financial mathematics and the Black-Scholes model. Silvio reported on recent joint work with Patrizia Mentrasti and Tommaso Toffoli, and showed us how to convert certain types of cellular automata to lattice gases. Mohammad wound up a nice scientific day by giving an accessible introduction to some recent work of his aiming at a unified framework for functional and performance analysis of processes. He proposed an approach enabling a provably sound transformation from some existing stochastic process algebras, e.g., PEPA and MTIPP, to a generic form in the mCRL2 language.
This workshop marks the beginning of a very busy year for ICE-TCS, a year leading up to ICALP 2008 in Reykjavík. I hope to see you in Reykjavík for that conference!
Friday, August 10, 2007
Atle Selberg (1917-2007)
The AMS news page reports that the Norwegian mathematician Atle Selberg passed away on August 6. As the AMS news item states, Selberg is perhaps best known for his work on the zeros of the Riemann zeta function, for which he was awarded a Fields Medal in 1950, and for his "elementary" proof of the prime number theorem. His honors include the 1986 Wolf Prize in Mathematics.
Selberg was also involved in one of the most famous controversies regarding allocation of credit for a result. His controversy with Paul Erdös regarding the genesis of the "elementary" proof of the prime number theorem features in every account of Erdös' life and work. See, e.g., this book and this obituary.
Addendum: I just saw that Luca Trevisan also has a (better) post on Selberg's death. Luca points to an obituary on the IAS web pages.
Selberg was also involved in one of the most famous controversies regarding allocation of credit for a result. His controversy with Paul Erdös regarding the genesis of the "elementary" proof of the prime number theorem features in every account of Erdös' life and work. See, e.g., this book and this obituary.
Addendum: I just saw that Luca Trevisan also has a (better) post on Selberg's death. Luca points to an obituary on the IAS web pages.
Wednesday, August 08, 2007
LICS Test-of-Time Award 2007
The LICS Test-of-Time Award recognizes a small number of influential papers which appeared in the LICS proceedings from 20 years prior that have best met the “test of time”.
I have just read that the Awards Committee for 2007, consisting of Yuri Gurevich (Chair), Rajeev Alur, and Glynn Winskel, selected the papers
as winners of the 2007 LICS Test-of-Time Award (for papers from LICS 1987). Congratulations to the authors for this recognition of their work! For once, I could have successfully bet on those two papers winning the award for 2007 :-)
I have just read that the Awards Committee for 2007, consisting of Yuri Gurevich (Chair), Rajeev Alur, and Glynn Winskel, selected the papers
as winners of the 2007 LICS Test-of-Time Award (for papers from LICS 1987). Congratulations to the authors for this recognition of their work! For once, I could have successfully bet on those two papers winning the award for 2007 :-)
Tuesday, August 07, 2007
Programming the Universe
I recently finished reading the book Programming the Universe by Seth Lloyd, Professor of Mechanical Engineering at MIT. The book is a very pleasant, thought-provoking read, and its message is honey to the ears of us computer scientists. To see why, it suffices only to read the first few lines in Chapter 1 of the book.
Basically, Seth Lloyd's message is that information is just as important as classic physical quantities like energy in understanding the universe, and that viewing the universe as a quantum computer can actually help us understand it better. He even proposes a theory of quantum gravity based on this view---a theory that, unlike others, may even be testable experimentally.
You might like to have a look at a scientist's cut from the material Lloyd penned down for the book here. There you will also find some interesting quotes from referee reports Lloyd received for some of his papers, and the following estimate on the number of operations performed by the universe since the big bang.
I wonder if Scott Aaronson has reviewed this book on his blog. It would be interesting to hear his opinion.
This book is the story of the universe and the bit. The universe is the biggest thing there is and the bit is the smallest possible chunk of information. The universe is made of bits. Every molecule, atom, and elementary particle registers bits of information. Every interaction between those pieces of the universe processes that information by altering those bits. That is, the universe computes, and because the universe is governed by the laws of quantum mechanics, it computes in an intrinsically quantum-mechanical fashion; its bits are quantum bits. The history of the universe is, in effect, a huge and ongoing quantum computation. The universe is a quantum computer.
Basically, Seth Lloyd's message is that information is just as important as classic physical quantities like energy in understanding the universe, and that viewing the universe as a quantum computer can actually help us understand it better. He even proposes a theory of quantum gravity based on this view---a theory that, unlike others, may even be testable experimentally.
You might like to have a look at a scientist's cut from the material Lloyd penned down for the book here. There you will also find some interesting quotes from referee reports Lloyd received for some of his papers, and the following estimate on the number of operations performed by the universe since the big bang.
The universe can have performed 10120 ops on 1090 bits (10120 bits including gravitational degrees of freedom).
I wonder if Scott Aaronson has reviewed this book on his blog. It would be interesting to hear his opinion.
Monday, August 06, 2007
Vardi on Process Equivalences
Last Saturday, Moshe Vardi posted the paper Branching vs. Linear Time: Semantical Perspective (invited ATVA'07 paper with Sumit Nain). This is a nicely written and balanced paper distilling Moshe's thoughts on the choice of semantics for concurrent processes. I have no doubt that it will generate some healthy discussion in the concurrency theory community. I strongly encourage my two readers to have a look at it.
Oversimplifying the message in the paper by Moshe and Sumit, in their opinion the plethora of process semantics is due to "semantic underspecification". To overcome this underspecification, they propose to develop process semantics based on the following principles.
As the authors state in the paper "In conclusion, this paper puts forward an, admittedly provocative, thesis, which is that process-equivalence theory allowed itself to wander in the “wilderness” for lack of accepted guiding principles. The obvious definition of contextual equivalence was not scrupulously adhered to, and the underspecificity of the formalisms proposed led to too many interpretations of equivalence.While one may not realistic expect a single paper to overwrite about 30 years of research, a more modest hope would be for a renewed discussion on the basic principles of process-equivalence theory."
What do you think?
Oversimplifying the message in the paper by Moshe and Sumit, in their opinion the plethora of process semantics is due to "semantic underspecification". To overcome this underspecification, they propose to develop process semantics based on the following principles.
- Principle of Contextual Equivalence: Two processes are equivalent if they behave the
same in all contexts, which are processes with “holes”. - Principle of Comprehensive Modeling: A process description should model all relevant
aspects of process behaviour. - Principle of Observable I/O: The observable behaviour of a tested process is precisely
its input/output behaviour.
As the authors state in the paper "In conclusion, this paper puts forward an, admittedly provocative, thesis, which is that process-equivalence theory allowed itself to wander in the “wilderness” for lack of accepted guiding principles. The obvious definition of contextual equivalence was not scrupulously adhered to, and the underspecificity of the formalisms proposed led to too many interpretations of equivalence.While one may not realistic expect a single paper to overwrite about 30 years of research, a more modest hope would be for a renewed discussion on the basic principles of process-equivalence theory."
What do you think?
Thursday, August 02, 2007
Rivest Wins Marconi Prize
MIT's Department of Electrical Engineering and Computer Science continues its rich harvest of awards. My RSS feeds monitor has informed me that Ron Rivest has been awarded the Marconi prize. See here for the MIT news item. Rivest has been named the 2007 Marconi Fellow and prize-winner for his pioneering work in the field of cryptography, computer and network security.
The Parking Algorithm
Furio Honsell is one of Italy's best known theoretical computer scientists. His research covers many areas within volume B TCS, and he was one of the proposers of the ‘Anti-Foundation Axiom’ for non-well-founded set theory. Furio was the first computer scientist to become rector of an Italian university, Università di Udine to be precise, and is now serving his second mandate as rector.
Unlike most of us, Furio is also known to the general Italian public for his participation in the TV show Che tempo che fa, where he discusses topics related to computer science and mathematics in a way that makes them accessible to a general audience. My mother, for instance, is fascinated by his witty and very clear discussions of topics that normally would not be aired on a TV show.
What has this all to do with "The Parking Algorithm"? A few days ago, walking back to my deck chair after a swim in the Adriatic sea, I saw a man read a volume by Furio entitled "L'Algoritmo del Parcheggio" ("The Parking Algorithm"), published by Mondadori, which is a major Italian publishing house. I was amazed. I stopped and asked this man whether I could write down the bibliographic details for the book, which I simply had to buy!
Furio is definitely doing a lot for promoting an appreciation for computer science and mathematics amongst the general educated public in Italy, and he must be doing it right if people read his book on the beach! I know that this is one of my, possibly boring, mantras, but we badly need more people who, like him, are not afraid to devote some of their time to writing books and articles for the general public, and who have the charisma to appear on TV and captivate viewers like my mother or that man who ended up buying his book and reading it under the sun-shade. (I also admire his time-management skills. Being a rector does not leave him a lot of time for research or book writing.)
For the record, I did buy Furio's book, but I'll have to wait for my mother to finish reading it before having a close look at it. I'll review Furio's book at some point in the future, but don't hold your breath.
Unlike most of us, Furio is also known to the general Italian public for his participation in the TV show Che tempo che fa, where he discusses topics related to computer science and mathematics in a way that makes them accessible to a general audience. My mother, for instance, is fascinated by his witty and very clear discussions of topics that normally would not be aired on a TV show.
What has this all to do with "The Parking Algorithm"? A few days ago, walking back to my deck chair after a swim in the Adriatic sea, I saw a man read a volume by Furio entitled "L'Algoritmo del Parcheggio" ("The Parking Algorithm"), published by Mondadori, which is a major Italian publishing house. I was amazed. I stopped and asked this man whether I could write down the bibliographic details for the book, which I simply had to buy!
Furio is definitely doing a lot for promoting an appreciation for computer science and mathematics amongst the general educated public in Italy, and he must be doing it right if people read his book on the beach! I know that this is one of my, possibly boring, mantras, but we badly need more people who, like him, are not afraid to devote some of their time to writing books and articles for the general public, and who have the charisma to appear on TV and captivate viewers like my mother or that man who ended up buying his book and reading it under the sun-shade. (I also admire his time-management skills. Being a rector does not leave him a lot of time for research or book writing.)
For the record, I did buy Furio's book, but I'll have to wait for my mother to finish reading it before having a close look at it. I'll review Furio's book at some point in the future, but don't hold your breath.
Wednesday, August 01, 2007
"Reactive Systems" Is Out: Buy Your Copy Now!
A few days ago, I checked the web page at Amazon.co.uk for my latest book Reactive Systems: Modelling, Specification and Verification, which I have already shamelessly advertised in previous postings. I was surprised to read that only four copies were left in stock (and only one is in stock right now, so hurry!), especially because the official publication date for the book is 9 August 2007.
My copy of the book landed in my mailbox yesterday, as partial compensation for the departure of the hard disk in my laptop, the only computer I own :-( It was quite an experience to browse through the results of a few years of work while wondering whether I really had any part in writing the text filling those pages. This is how I often feel whenever I look at some work of mine. Was it really I who contributed to write/do that work? Something to ponder while waiting for a new hard disk, even though I know that it was really a different person from the one typing these characters who did it.
Anyway, I hope some of you will like the book, whoever wrote it.
My copy of the book landed in my mailbox yesterday, as partial compensation for the departure of the hard disk in my laptop, the only computer I own :-( It was quite an experience to browse through the results of a few years of work while wondering whether I really had any part in writing the text filling those pages. This is how I often feel whenever I look at some work of mine. Was it really I who contributed to write/do that work? Something to ponder while waiting for a new hard disk, even though I know that it was really a different person from the one typing these characters who did it.
Anyway, I hope some of you will like the book, whoever wrote it.
Tuesday, July 31, 2007
Edsger W. Dijkstra Prize for 2007
The winner of the Edsger W. Dijkstra Prize for 2007 is the paper "Consensus in the presence of partial synchrony'' by Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer, which appeared in the Journal of the ACM, Vol. 35, No. 2, April, 1988. pages 288--323. (A preliminary version appeared in PODC 1984.) This is the second time that Nancy Lynch winds up this prize since she had received it before in 2001 for her classic paper
Michael J. Fischer , Nancy A. Lynch and Michael S. Paterson. "Impossibility of Distributed Consensus with One Faulty Process", Journal of the ACM, April 1985, 32(2):374-382.
One can say that, despite how faulty researchers may be in evaluating the quality of scientific work, there is definite consensus on Nancy's huge impact on research in the principles of distributed computing! Congratulations to the winners.
It is sad that Larry Stockmeyer is not here with us to enjoy yet another achievement in his distinguished career. He passed away in 2004. Look here for some commemorations that took place at that time.
Michael J. Fischer , Nancy A. Lynch and Michael S. Paterson. "Impossibility of Distributed Consensus with One Faulty Process", Journal of the ACM, April 1985, 32(2):374-382.
One can say that, despite how faulty researchers may be in evaluating the quality of scientific work, there is definite consensus on Nancy's huge impact on research in the principles of distributed computing! Congratulations to the winners.
It is sad that Larry Stockmeyer is not here with us to enjoy yet another achievement in his distinguished career. He passed away in 2004. Look here for some commemorations that took place at that time.
Tuesday, July 24, 2007
Special Issue of JLAP Devoted to FOSSACS 2006
This to let you know that a special issue of JLAP devoted to selected papers from FOSSACS 2006 is now available on line. Anna and I edited the issue. I hope that you'll enjoy reading the papers in that volume.
Many thanks to all the colleagues who contributed to the success of the conference, and to the expert referees who devoted some of their time to a careful evaluation of the submitted papers. It has been a pleasure to work with all of you.
Many thanks to all the colleagues who contributed to the success of the conference, and to the expert referees who devoted some of their time to a careful evaluation of the submitted papers. It has been a pleasure to work with all of you.
Software from Reykjavík University Wins the 2007 GGP Competition
These are good days for AI (and CS) research at Reykjavík University, and I trust that you'll forgive me for self-promoting the achievements of my department. The finals of the 2007 General Game-Playing competition at the AAAI conference have been won by "our" own CADIAPlayer, developed by Yngvi Björnsson and his MSc student Hilmar Finsson within CADIA, our centre for AI research. (As you can see, Yngvi is very hot these days!) The aim of the GGP competitions is to help develop systems that can accept a formal description of an arbitrary game and, without further human interaction, can play the game effectively.
According to Yngvi, the competition was very exciting, especially the final, which was played against ClunePlayer from the University of California, Los Angeles. (ClunePlayer was the second place finisher last year, and the world-champion from two years ago).
Congratulations to Hilmar and Yngvi for a great success!
According to Yngvi, the competition was very exciting, especially the final, which was played against ClunePlayer from the University of California, Los Angeles. (ClunePlayer was the second place finisher last year, and the world-champion from two years ago).
Congratulations to Hilmar and Yngvi for a great success!
Friday, July 20, 2007
Checker is a Draw
I am very happy to see that the news of the week in Science reports on a triumph of AI and (theoretical) computer science. A team from the games group at the University of Alberta, Canada, has announced that checkers is now solved: perfect play by both sides leads to a draw. Determining the outcome of the game brings AI search techniques to bear at a totally new level of complexity. The game of checkers has roughly 500 billion billion possible positions (5 x 1020)! These are state spaces of "model-checking size" :-)
Unfortunately, the full text of the Science article is only available to subscribers. The abstract is here. See also the web page of Chinook, the world checkers champion.
I am also very happy to report that one of the members of the team that solved checkers, Yngvi Björnsson, is a colleague of mine at Reykjavík University. This success will bring some media exposure for our department. (I know that process algebra cannot be expected to do so, alas :-))
Addendum: Bill Gasarch also has a, more detailed, post on this piece of news. Do read the comments to his post, which are, as usual, interesting.
Unfortunately, the full text of the Science article is only available to subscribers. The abstract is here. See also the web page of Chinook, the world checkers champion.
I am also very happy to report that one of the members of the team that solved checkers, Yngvi Björnsson, is a colleague of mine at Reykjavík University. This success will bring some media exposure for our department. (I know that process algebra cannot be expected to do so, alas :-))
Addendum: Bill Gasarch also has a, more detailed, post on this piece of news. Do read the comments to his post, which are, as usual, interesting.
Saturday, July 14, 2007
Corrado Priami on Italian Prime Time TV
Last Thursday I ended up watching part of SuperQuark, a well-done science programme that has been running on Italian TV (RAI 1 to be precise) for some time now. To my pleasant surprise, the programme had a feature on the Centre for Computational and Systems Biology---a joint undertaking between the University of Trento and Microsoft Research. (You can watch the video, in Italian, here.)
The feature included excerpts of an interview with Corrado Priami, the president of the centre, and Luca Cardelli made some visual guest appearances.
It was a great pleasure to see a centre involving computer science in a crucial way make an appearance on prime-time TV. I can only compliment Corrado for having achieved so much in his career so far. I still remember sharing some work-space with him at the HP research lab in Pisa in late 1991-early 1992. He was fresh from his MSc degree then, and working on very different things.
Showcasing the impact of computer science on other sciences on prime-time TV can only be good for our field. Who is going to be next?
The feature included excerpts of an interview with Corrado Priami, the president of the centre, and Luca Cardelli made some visual guest appearances.
It was a great pleasure to see a centre involving computer science in a crucial way make an appearance on prime-time TV. I can only compliment Corrado for having achieved so much in his career so far. I still remember sharing some work-space with him at the HP research lab in Pisa in late 1991-early 1992. He was fresh from his MSc degree then, and working on very different things.
Showcasing the impact of computer science on other sciences on prime-time TV can only be good for our field. Who is going to be next?
Monday, June 25, 2007
Accepted Papers for CONCUR 2007
The list of accepted papers for CONCUR 2007 is finally out. You can browse through the list here. The programme looks exciting, and I am looking forward to attending the conference.
The list of invited talks and tutorials is here. It will be a great honour to deliver an invited talk at that conference. (An honour that I cannot help but feel should have been bestowed on many other colleagues of mine.) I will eventually post the slides for my talk on this blog. Check this space if, for some reason, you are interested in the talk I plan to give.
The list of invited talks and tutorials is here. It will be a great honour to deliver an invited talk at that conference. (An honour that I cannot help but feel should have been bestowed on many other colleagues of mine.) I will eventually post the slides for my talk on this blog. Check this space if, for some reason, you are interested in the talk I plan to give.
Friday, June 22, 2007
What is a Free Name in a Process Algebra?
This is the question addressed by a short paper by Flemming Nielson, Hanne Riis Nielson and Henrik Pilegaard that appears in Information Processing Letters 103 (2007), pp. 188-194. In the paper, the authors show that the standard definition of free name is not preserved under the structural congruence, which is one of the sanity properties one would expect to have.
The traditional definition of the set of free names of a process term stipulates that the set of free names of a parameterized constant A(x1,...,xn) is {x1,...,xn}. Moreover, a term of the form A(y1,...,yn) is structurally congruent to P[y1,...yn/x1,...,xn] if the body of A(x1,...,xn) is the term P.
Consider now, for instance, the constant A(x) with body 0. The A(x) has x as its only free name. But this term is structurally congruent to 0, whose set of free names is empty! This is an example showing that the traditional definition of free names is not preserved by structural congruence, and we certainly want a process constant to be congruent to its body.
Why didn't anybody notice this before? As the authors write in their paper "Unfortunately the notion of free names is usually considered so simple that a formal definition is dispensed with and this occasionally shows up as problems in proofs."
In that paper, the authors develop a fixed point approach to the set of free names, argue that the set of free names can be computed efficiently and show that it is invariant under structural congruence.
I strongly recommend reading the paper.
The traditional definition of the set of free names of a process term stipulates that the set of free names of a parameterized constant A(x1,...,xn) is {x1,...,xn}. Moreover, a term of the form A(y1,...,yn) is structurally congruent to P[y1,...yn/x1,...,xn] if the body of A(x1,...,xn) is the term P.
Consider now, for instance, the constant A(x) with body 0. The A(x) has x as its only free name. But this term is structurally congruent to 0, whose set of free names is empty! This is an example showing that the traditional definition of free names is not preserved by structural congruence, and we certainly want a process constant to be congruent to its body.
Why didn't anybody notice this before? As the authors write in their paper "Unfortunately the notion of free names is usually considered so simple that a formal definition is dispensed with and this occasionally shows up as problems in proofs."
In that paper, the authors develop a fixed point approach to the set of free names, argue that the set of free names can be computed efficiently and show that it is invariant under structural congruence.
I strongly recommend reading the paper.
Thursday, June 21, 2007
Book Promotion
I apologize for the self-promotion and marketing :-)
In case any of you are looking for some summer reading, I recommend, not surprisingly, the book advertised in this flyer. If you purchase the book using the flyer, you'll have a 20% discount. Get your university library to order a few copies!
Here is what the endorsers of the book have to say about it. (Edited excerpts from the endorsements appear on the back cover for the book.)
In case any of you are looking for some summer reading, I recommend, not surprisingly, the book advertised in this flyer. If you purchase the book using the flyer, you'll have a 20% discount. Get your university library to order a few copies!
Here is what the endorsers of the book have to say about it. (Edited excerpts from the endorsements appear on the back cover for the book.)
Wednesday, June 20, 2007
ICALP 2008: Call for Workshops and Web Site
The call for workshops for ICALP 2008 has been posted on a large collection of mailing lists today. Consider proposing a workshop and making a trip to Iceland for the event! The deadline for workshop proposals is October 31, 2007. You'll be notified of acceptance/rejection of your proposals by 21 November 2007 at the latest.
The web site for the conference is located here. It is still preliminary, but all of the pieces of information that are relevant at this stage are already in place. For a sneak preview of the call for papers, look here.
Watch this space for further information on the development of the conference organization.
The web site for the conference is located here. It is still preliminary, but all of the pieces of information that are relevant at this stage are already in place. For a sneak preview of the call for papers, look here.
Watch this space for further information on the development of the conference organization.
Tuesday, June 19, 2007
Avi Wigderson's Louis Clark Vanuxem Lectures
I recently stumbled across the slides for "A world view through the computational lens", three talks given at Princeton University by Avi Wigderson. These talks, which were delivered in the Louis Clark Vanuxem series, form an excellent companion to the talk that Papadimitriou recently gave at FCRC. See this post.
The plan for Wigderson's series of lectures is as follows.
There is a lot of inspiration to be drawn from those slides. Is TCS really the "new math"? Only time will tell, but this really a good refrain to listen to anyway :-)
The plan for Wigderson's series of lectures is as follows.
There is a lot of inspiration to be drawn from those slides. Is TCS really the "new math"? Only time will tell, but this really a good refrain to listen to anyway :-)
Friday, June 15, 2007
Computing Community Consortium Workshop at FCRC
The Computing Community Consortium (CCC) was recently created by the Computing Research Association (CRA) and is funded under a cooperative agreement from the National Science Foundation (NSF). The purpose of the CCC is to catalyze the computing research community to debate longer range, more audacious research challenges; to build consensus around research visions; to articulate those research visions; to evolve the most promising visions toward clearly defined initiatives; and to work with funding organizations to move the challenges and visions toward funding initiatives.
This week the CCC is organizing a workshop at the 2007 Federated Computing Research Conference. The slides for the contributed talks given so far are available here. (Lazowska's slides are still missing at the time of writing since his talk will be delivered today. I am looking forward to seeing them!) They are all interesting at first sight. In particular, I want to encourage readers of this blog to look at the wonderful slides for Christos Papadimitriou's talk on the Algorithmic Lens. The slides give Christos Papadimitriou's view of the impact that computer science is having on other sciences, and can offer all of us plenty of food for thought as well as material for enticing students to CS.
In case you do not have time to look at the slides, the executive summary of the talk, presented on the last slide reads:
Addendum: Ed Lazowska's slides are now on line.
This week the CCC is organizing a workshop at the 2007 Federated Computing Research Conference. The slides for the contributed talks given so far are available here. (Lazowska's slides are still missing at the time of writing since his talk will be delivered today. I am looking forward to seeing them!) They are all interesting at first sight. In particular, I want to encourage readers of this blog to look at the wonderful slides for Christos Papadimitriou's talk on the Algorithmic Lens. The slides give Christos Papadimitriou's view of the impact that computer science is having on other sciences, and can offer all of us plenty of food for thought as well as material for enticing students to CS.
In case you do not have time to look at the slides, the executive summary of the talk, presented on the last slide reads:
- The algorithmic world view is changing the sciences: mathematical, natural, life, social
- CS is placing itself at the center of the scientific discourse and exchange of ideas
- And this is only the beginning…
Addendum: Ed Lazowska's slides are now on line.
Monday, June 11, 2007
Rejecting Excellent Papers
Is it good for a journal, no matter how prestigious, to reject excellent scientific contributions on the grounds that it gets substantially more first-rate submissions than it is able to accept? In TCS, I am aware that JACM has such a policy, and I wonder whether it is backfiring badly. (My, possibly wrong, impression is that several authors decide not to submit top-notch papers to that journal because of that policy. I myself have always some trouble in deciding whether a paper is among the best papers of the year in its area since this seems to involve some crystal-ball gazing.)
A recent, remarkable instance of this kind of rejection is mentioned in a letter in the latest issue of the Notices of the AMS. (See here, on page 2 of the file. The letter is co-signed by Vaughan Pratt, one of my favourite theoretical computer scientists.) Apparently, the editorial board of the Journal of the AMS, which is the flagship journal of the American Math Society, has declined to publish a 14-page paper reporting on Friedrich Wehrung's solution to Dilworth's Congruence Lattice Problem for its lack of “interaction with other areas of mathematics”. The problem had been open for about fifty years, and drove the development of lattice theory during that time. See this web page for more information.
I am sure that the author will rapidly publish the paper in a top-notch journal, given that it had glowing referee reports. What I am not sure of is how many, apparently superb papers, a journal can decline to publish before authors stop submitting to it.
I guess that, as usual, the great judge will be Time.
Addendum 12 June 2007: A look at Friedrich Wehrung's publications page indicates that the aforementioned paper of his is going to appear in Advances in Mathematics.
A recent, remarkable instance of this kind of rejection is mentioned in a letter in the latest issue of the Notices of the AMS. (See here, on page 2 of the file. The letter is co-signed by Vaughan Pratt, one of my favourite theoretical computer scientists.) Apparently, the editorial board of the Journal of the AMS, which is the flagship journal of the American Math Society, has declined to publish a 14-page paper reporting on Friedrich Wehrung's solution to Dilworth's Congruence Lattice Problem for its lack of “interaction with other areas of mathematics”. The problem had been open for about fifty years, and drove the development of lattice theory during that time. See this web page for more information.
I am sure that the author will rapidly publish the paper in a top-notch journal, given that it had glowing referee reports. What I am not sure of is how many, apparently superb papers, a journal can decline to publish before authors stop submitting to it.
I guess that, as usual, the great judge will be Time.
Addendum 12 June 2007: A look at Friedrich Wehrung's publications page indicates that the aforementioned paper of his is going to appear in Advances in Mathematics.
Friday, June 08, 2007
June/July Notices of the AMS
The latest installment of the Notices of the AMS is out with a new look and some interesting-looking articles. I am certainly going to look at the article on The Mathematical Work of Jon Kleinberg by Gert-Martin Greuel, John Hopcroft, Margaret H. Wright, and at the contribution on the highly-successful math department at UCLA. The contribution by Graetzer on Two Problems That Shaped a Century of Lattice Theory looks worth a browse, even though the math is surely way beyond my knowledge of lattice theory.
Enjoy.
Enjoy.
Thursday, June 07, 2007
Invited Speakers at ICALP 2008
This is my second news item on the organization of ICALP 2008 (7-11 July 2008, Reykjavik, Iceland). On behalf of the organizing committee, I am pleased to give you the preliminary list of confirmed invited speakers. These are:
Anna, Magnus and I are very glad to be able to offer participants at ICALP 2008 this outstanding set of invited talks.
Preliminary call for workshops and call for papers will be posted on this blog and on mailing lists very soon. Watch this space if you want to be the first to know!
- Ran Canetti (IBM T.J. Watson Research Center and MIT, USA),
- Bruno Courcelle (Labri, Universitè Bordeaux, France),
- Javier Esparza (Technische Universität München, Germany),
- Muthu Muthukrishnan (Google, USA) and
- Peter Winkler (Dartmouth, USA).
Anna, Magnus and I are very glad to be able to offer participants at ICALP 2008 this outstanding set of invited talks.
Preliminary call for workshops and call for papers will be posted on this blog and on mailing lists very soon. Watch this space if you want to be the first to know!
Tuesday, June 05, 2007
AITO Dahl-Nygaard Prize Winners for 2007
I just saw that the Dahl-Nygaard Prizes for 2007 will be given to Luca Cardelli, Microsoft Research Cambridge (Senior prize) for his overall contribution to both theory and practice for object-oriented languages, and to Jonathan Aldrich, Carnegie Mellon University Pittsburgh (Junior prize) for his recent contribution to expressing and verifying software architecture in object-oriented languages.
I am very pleased to see Luca Cardelli honoured in this way, and I trust that this won't be the last award he will receive for his outstanding research achievements. Luca is a one-man research team, and he is equally at ease in theoretical as well as in implementation work. The text accompanying the notification singles out his famous book "A Theory of Objects", published with Martin Abadi in 1996, the Ambient Calculus (developed with Andy Gordon) and his work in Computational Systems Biology.
Congratulations to Luca!
I am very pleased to see Luca Cardelli honoured in this way, and I trust that this won't be the last award he will receive for his outstanding research achievements. Luca is a one-man research team, and he is equally at ease in theoretical as well as in implementation work. The text accompanying the notification singles out his famous book "A Theory of Objects", published with Martin Abadi in 1996, the Ambient Calculus (developed with Andy Gordon) and his work in Computational Systems Biology.
Congratulations to Luca!
Ranking
My gmail RSS monitor has alerted me that the June issue of CACM includes the article Automatic and versatile publications ranking for research institutions and scholars by Jie Ren and Richard N. Taylor. In that article, the authors briefly discuss the role of rankings of institutions and individuals in modern academic life, present the main criteria used in existing rankings, and introduce their own fully automatic ranking system, which is available here.
I have not played with the authors' system yet, but the tables they present to substantiate its quality make for some interesting reading. The top five computer science departments in the US, according to their ranking, are as follows.
In Software Engineering, as an Italian abroad I am glad to see the Politecnico di Milano in 8th place and the University of Bologna in 41st. Amongst individual researchers in SE, Paola Inverardi is ranked 17th. Perhaps interestingly, the SE rankings given in the article differ significantly from those obtained by others in a previous ranking exercise.
This is what the authors have to say.
What does this indicate? Automatic rankings will be very useful in the future, but it will be all the more important to specify clearly how such rankings are obtained. In particular, when evaluating the results of such ranking exercises, I'd really like to know what publication outlets were considered, what weight they were given, and what weight was given to multi-authored papers. I do not see why the author of a multi-authored paper should necessarily receive a fraction of the points awarded to the paper. Is writing a paper with a co-author less work than doing it alone?
I have not played with the authors' system yet, but the tables they present to substantiate its quality make for some interesting reading. The top five computer science departments in the US, according to their ranking, are as follows.
- MIT
- University of Maryland, College Park
- CMU
- Georgia Institute of Technology
- Stanford
In Software Engineering, as an Italian abroad I am glad to see the Politecnico di Milano in 8th place and the University of Bologna in 41st. Amongst individual researchers in SE, Paola Inverardi is ranked 17th. Perhaps interestingly, the SE rankings given in the article differ significantly from those obtained by others in a previous ranking exercise.
This is what the authors have to say.
Our ranking is significantly different from the JSS ranking. The second column in Table 2 shows that only two of the top 15 institutions from the JSS ranking are among the top 15 of our ranking. The second column in Table 3 shows that only two of the top 15 scholars from the JSS ranking are among the top 15 of our ranking.Two policy disparities probably contribute to the difference. First, we included two conferences in our ranking that the JSS ranking did not consider. Secondly, our ranking and the JSS ranking selected different journals and these journals contributed scores differently. The JSS ranking heavily relies on papers published in itself and the journal Information and Software Technology. It also includes a magazine, IEEE Software. The JSS ranking receives almost no influence from ACM Transactions on Software Engineering and Methodology. This study illustrates that the framework can produce dramatically different results when used with different policies, even for the same field.
What does this indicate? Automatic rankings will be very useful in the future, but it will be all the more important to specify clearly how such rankings are obtained. In particular, when evaluating the results of such ranking exercises, I'd really like to know what publication outlets were considered, what weight they were given, and what weight was given to multi-authored papers. I do not see why the author of a multi-authored paper should necessarily receive a fraction of the points awarded to the paper. Is writing a paper with a co-author less work than doing it alone?
Monday, June 04, 2007
Invited Paper for CONCUR 2007
I have posted my contribution to the Proceedings of CONCUR 2007. The paper, coauthored with Anna and entitled The Saga of the Axiomatization of Parallel Composition, is a survey of recent work Anna and I have done in collaboration with Wan Fokkink, Bas Luttik and MohammadReza Mousavi. We published some of this work directly in journals, and so it felt appropriate to present it in a conference proceedings. I'll be basing my invited talk at CONCUR on the paper.
Thanks a lot to Anna, Bas, Mohammad and Wan for our pleasant collaborations so far. I hope to do some justice to our joint work in Lisbon. It'll be a bit of a challenge to make the audience interested in the story I have to tell, but it is one I hope to meet decently well. It'll be up to the participants at CONCUR 2007 to tell whether I'll succeed.
Surprisingly, the list of accepted papers for the conference is not yet available from the CONCUR 2007 web site. I am looking forward to viewing the programme for this event.
Thursday, May 31, 2007
The Value of a PhD
I recently stumbled across the blog The Unapologetic Mathematician, and read this post. Its title suggests that it is about commencement exercises, one of those, admittedly rather boring, academic rituals that get perpetuated every year. In reality, the post waxes lyrically about the "value" of a PhD.
As will be clear to those of you who read that piece, the "unapologetic mathematician" can write! For what it is worth, I agree with what he says. Here is an excerpt I really liked.
As will be clear to those of you who read that piece, the "unapologetic mathematician" can write! For what it is worth, I agree with what he says. Here is an excerpt I really liked.
Amen. In a society where money is the only thing that seems to matter, and where any line of study carrying one or more of the tags "business", "financial" or "media" attracts hundreds of students, it is good to see somebody sing the praises of adding a little to the honour of the human spirit.
The doctorate is the gold standard of the academy. You can’t get it by spitting back answers on a sequence of course finals. You can’t get it by retaining the material until a collection of comprehensive exams, or by writing up a survey of relevant literature. You attain a doctorate by extending the boundaries human knowledge.This society generally speaks well of originality, but it tends to mean a rather pale sort. To really, truly think of something nobody else has before — and to be able to justify it — is really far more difficult than most people give credit to. It’s not something you do on weekends, in your spare time while doing other more important things. The Great Work is hard. It means steeping yourself in a subject until you understand in a way only a handful of other people do. It means sacrificing years of your life to the pursuit of something truly new and different. The path is littered with those who started and did not make it through to the end.
And it has no justification but itself. Nobody goes into academics for the money. Nobody does it for the praise of the masses. Compared to most other things any of these new doctors could have done it will be temporally thankless. You live the academic life because you look outside at the amazing world around yourself and you realize that, for you, the highest achievement of the human spirit is to understand it more deeply — to internalize some aspect of it, digest it, and help share that with the rest of humanity. You do it because it is fundamentally worth doing. The life of the mind has a value in and of itself. And so these men and women have chosen this value over all the others they might have.
Tuesday, May 29, 2007
A Journal Without Editors
Here is another bit of trivia related to publication issues. The latest issue of the Elsevier Journal "Topology" has appeared without any mention of an editorial board. (The page that normally lists the editors is blank.) I looked at the home page for the journal, and there is no mention of editors there either. The guide for authors states
"For information regarding current submissions please contact topology@elsevier.com. "As you probably know, the entire editorial board of Topology resigned last year. (The resignation letter is available here.) The board has founded a new journal, Journal of Topology, published by the London Mathematical Society and Oxford University Press. The price of the journal will be roughly one third of the price of the Elsevier journal.
Saturday, May 26, 2007
Second ICE-TCS Annual Report
Magnus M. Halldórsson, Anna Ingólfsdóttir and I have been co-directing ICE-TCS, a small research centre in theoretical computer science, here in Reykjavík for two years. Our second annual report is now available, in case anybody is interested.
ICE-TCS operates on a shoestring budget, but we hope that the local funding agencies will become interested in investing in "centres of excellence" and that they'll consider ICE-TCS to be one of those. (Fat chance :-)) In the unlikely event that this happens, I'll announce available visiting positions on this blog. Watch this space.
ICE-TCS operates on a shoestring budget, but we hope that the local funding agencies will become interested in investing in "centres of excellence" and that they'll consider ICE-TCS to be one of those. (Fat chance :-)) In the unlikely event that this happens, I'll announce available visiting positions on this blog. Watch this space.
Wednesday, May 23, 2007
The Wrecking of British Science
Harry Kroto is one of those larger than life figures whose life we are lucky to cross in our lives every now and again. He was a professor of chemistry at the University of Sussex when I was a PhD student there, and received the Nobel Prize for Chemistry in 1996 for his discovery of the C60 molecule, aka buckminsterfullerene. He was the prime mover behind the Vega Science Trust, a UK educational charity (see www.vega.org.uk). He has been one of the participants of the heroes in science programme here at Reykjavik University, where he played with models of C60 molecules together with local kids.
Why am I droning on about this guy, you may ask? The reason is that I just read this article he wrote for the Guardian. (I strongly recommend that you read it, especially if your heart still feels for the British university system like mine does.) The picture Kroto paints is bleak, but all too familiar, alas. Throughout the western world, the number of students interested in science is declining frighteningly, at a time when our society is so dependent on science. As Kroto writes in that article:
Why am I droning on about this guy, you may ask? The reason is that I just read this article he wrote for the Guardian. (I strongly recommend that you read it, especially if your heart still feels for the British university system like mine does.) The picture Kroto paints is bleak, but all too familiar, alas. Throughout the western world, the number of students interested in science is declining frighteningly, at a time when our society is so dependent on science. As Kroto writes in that article:
Scientific education is by far the best training for all walks of life, because it teaches us how to assess situations critically and react accordingly. It gives us an understanding based on reverence for life-enhancing technologies as well as for life itself. If we do not know how things work, how can we fix things? And how are we going to use these powerful technologies wisely?Even more important than the training for non-existent jobs is the worrying decrease in our society of that willingness to think critically, to work on problems, to be creative, and to challenge ourselves that are one of the main ingredients of our humanity. I sincerely hope that the new Icelandic government that was formed today will work proactively to put science on the agenda in Icelandic schools at all levels. It is a small step, but one has to start somewhere.The situation in universities is exacerbated by present policy, which actively encourages vice-chancellors who know the cost of everything and the value of nothing to eliminate science departments in favour of trendy, cheap courses. These VCs bleat about how important their freedom is to do whatever they wish with taxpayers' money, and steer funds earmarked for the sciences into softer areas that students prefer.
Just as cheap fast food has resulted in unprecedented levels of obesity, so this McDonald's approach to cheap, trendy, seductively soft courses designed for mass consumption in tertiary education has resulted in a plethora of students trained for non-existent jobs.
Sunday, May 20, 2007
Elsevier's Computer Science Review
Wolfgang Thomas recently pointed out to me a new Elsevier journal by the name of Computer Science Review. The aim of this journal is to publish research surveys and expository overviews in computer science and related fields. The reviews are aimed at a general computer science audience.
I was not aware of this new Elsevier journal, and my feeling is that its aim overlaps somewhat with that of the columns in the Bulletin of the EATCS. As one of the column editors, so far I have been extremely impressed by the willingness of the members of the concurrency theory community to contribute to the Bulletin. However, when I read at http://www.elsevier.com/wps
"Submissions are free of charge and recognizing the work involved in preparing a review article, Elsevier will pay authors for their contributions to Computer Science Review. This amount will be Euro 400 per accepted article for the authors; provided the article meets minimum length requirements (at least 20 typeset pages, preferably more). Book reviewers will be paid for comprehensive book review contributions - EUR 15 per typeset page, to a maximum of EUR 100." (The emphasis is mine.)
I cannot help but being worried about the future of the columns. Paying authors for their contributions to a journal is a remarkable development, and can even be seen as unfair competition :-) Sure, we are not talking about large sums of money, but I am not aware myself of any other journal in computer science that pays its contributors. Do you know of any journal that does so?
I wonder whether this move by Elsevier heralds a new era in which commercial publishers will reward authors, editors and referees financially. I am not sure that this would be a positive development myself. (Only once so far I have been "paid" for a journal review, and was very surprised when the cognizant editor offered to pay me. I received a 50-euro book voucher for reviewing a paper that had been awaiting a referee report for about three years and that, for some reason that I cannot understand yet, nobody wanted to evaluate.)
As Moshe Vardi often says, our currency is reputation, not money. Call me an idealist, but I'd like to keep things this way.
Comments on the issue of payment for journal papers, review articles and book reviews are most welcome. I'd really love to hear what you think about this new development.
Friday, May 18, 2007
Concurrency Column for the June 2007 Issue of the BEATCS
I have just posted the concurrency column for the June 2007 issue of the Bulletin of the EATCS.
In this piece, Orna Kupferman, who is one of the prime movers in the study of automata-theoretic constructions and in their application to the verification of reactive systems, presents a survey of several automata-theoretic problems in which the gap between the known upper and lower complexity bounds is exponential, and describes recent efforts to close the gaps.
I am glad to be able to offer this piece to the readership of the concurrency column and of this blog, and I trust that you will enjoy reading it as much as I did.
In this piece, Orna Kupferman, who is one of the prime movers in the study of automata-theoretic constructions and in their application to the verification of reactive systems, presents a survey of several automata-theoretic problems in which the gap between the known upper and lower complexity bounds is exponential, and describes recent efforts to close the gaps.
I am glad to be able to offer this piece to the readership of the concurrency column and of this blog, and I trust that you will enjoy reading it as much as I did.
Monday, May 14, 2007
PCs for ICALP 2008
Over the coming year or so, I'll be using this blog to keep you posted on the developments in the organization of ICALP 2008, which Anna Ingolfsdottir, Magnus Halldorsson and I will be co-organizing at Reykjavik University in the period 7-11 July 2008.
ICALP 2008 will have three tracks, and the PCs for the three tracks have been formed. They are as follows.
For the moment, plan to submit your best papers to ICALP 2008 and use this chance to make a visit to Iceland and to our ICE-TCS research centre!
ICALP 2008 will have three tracks, and the PCs for the three tracks have been formed. They are as follows.
Track A
- Michael Bender (State Univ of New York at Stony Brook, USA)
- Magnus Bordewich (Durham University, UK)
- Peter Bro Miltersen (Aarhus University, Denmark)
- Lenore Cowen (Tufts University, USA)
- Pierluigi Crescenzi (Università di Firenze, Italy)
- Artur Czumaj (University of Warwick, UK)
- Edith Elkind (University of Southampton, UK)
- David Eppstein (University of California at Irvine, USA)
- Leslie Ann Goldberg (University of Liverpool, UK) (chair)
- Martin Grohe (Humboldt-Universität zu Berlin, Germany)
- Giuseppe Italiano (Università di Roma "Tor Vergata", Italy)
- Christos Kaklamanis (University of Patras, Greece)
- Michael Mitzenmacher (Harvard University, USA)
- Ian Munro (University of Waterloo, Canada)
- Ryan O'Donnell (Carnegie Mellon University, USA)
- Dana Ron (Tel-Aviv University, Israel)
- Tim Roughgarden (Stanford University, US)
- Christian Scheideler (Technische Universität München, Germany)
- Christian Sohler (University of Paderborn, Germany)
- Luca Trevisan (University of California at Berkeley, USA)
- Berthold Vocking (RWTH Aachen University, Germany)
- Gerhard Woeginger (Eindhoven University of Technology, the Netherlands)
Track B
- Parosh Abdulla (Uppsala University, Sweden)
- Luca de Alfaro (University of California, Santa Cruz, USA
- Christel Baier (Technische Universität Dresden, Germany)
- Giuseppe Castagna (Université Paris 7, France)
- Rocco de Nicola (Università di Firenze, Italy)
- Javier Esparza (Technische Universität München, Germany)
- Marcelo Fiore (University of Cambridge, UK)
- Erich Grädel (RWTH Aachen, Germany)
- Jason Hickey (California Institute of Technology, USA)
- Martin Hofmann (Ludwig-Maximilians-Universität München, Germany)
- Hendrik Jan Hoogeboom (Leiden University, NL)
- Radha Jagadeesen (DePaul University, USA)
- Madhavan Mukund (Chennai Mathematical Institute, India)
- Luke Ong (Oxford University, UK)
- Dave Schmidt (Kansas State University, USA)
- Philippe Schnoebelen (ENS Cachan, France)
- Igor Walukiewicz (Labri, Universitè Bordeaux, France) (chair)
- Mihalis Yannakakis (Columbia University, USA)
- Wieslaw Zielonka (Université Paris 7, France)
Track C
- Christian Cachin (IBM Research Zurich, CH)
- Jan Camenisch (IBM Research Zurich, CH)
- Ivan Damgård (Aarhus University, Denmark) (chair)
- Stefan Dziembowski ((Università di Roma "La Sapienza", Italy)
- Dennis Hofheinz (CWI Amsterdam, the Netherlands)
- Susan Hohenberger (Johns Hopkins University, USA)
- Yuval Ishai (Technion Haifa, Israel)
- Lars Knudsen (DTU Copenhagen, Denmark)
- Arjen Lenstra (EPFL Lausanne, CH)
- Anna Lysyanskaya (Brown University, USA)
- Rafael Pass (Cornell University, USA)
- David Pointcheval (ENS Paris, France)
- Dominique Unruh (Saarland University, Germany)
- Serge Vaudenay (EPFL Lausanne, CH)
- Bogdan Warinschi (Bristol University, UK)
- Douglas Wikström
- Stefan Wolf (ETH Zurich, CH)
For the moment, plan to submit your best papers to ICALP 2008 and use this chance to make a visit to Iceland and to our ICE-TCS research centre!
Sunday, May 13, 2007
The End of an Era
Last Friday I heard from Wan Fokkink that Jaco van de Pol will become a professor in Twente after the summer (as a successor of Ed Brinksma, who is now the director of the Embedded Systems Institute in Eindhoven). Congratulations to Jaco.
A byproduct of Jaco's move to Twente is that the process algebra group at CWI, which over the years has been headed by Jos Baeten, Frits Vaandrager, Jan Friso Groote, Wan Fokkink, and finally Jaco van de Pol, will be terminated. It is a fact of life that all (good) things must eventually come to an end, but I cannot help but feel that this is truly the end of an era.
The work of the process algebra group at CWI has played a major role in my scientific development, and I have had the pleasure to collaborate on various projects with several of its leaders mentioned above. (Disclaimer: The process algebra group at CWI is not responsible for the outcome of my work :-)) I like to think that the legacy of that group will be felt for many years to come. Indeed, one of the signs of its impact on Dutch computer science is the fact that all of its leaders over the years are now professors and leaders of strong research groups in some of the best Dutch universities.
Even though my work owes a lot to the intellectual inspiration of the process algebra group at CWI, I only visited CWI once in September 2005, and then only for a day to deliver a talk in the well-known PAM series---well, well-known amongst process algebraists. I guess that this indicates how little I travel around, and that one can be influenced by the work carried out at an institution without having ever visited it. (As another example, I owe a great debt to the Edinburgh concurrency school, but I have never visited Edinburgh.)
I vividly recall that, while introducing my talk at CWI, I paraphrased a famous sentence by the Italian writer Alessandro Manzoni and said that I felt that I had finally gone to Amsterdam to wash my process algebra clothes in the Amstel. With the demise of the process algebra group at CWI, it will unfortunately become a lot harder to wash my process algebra clothes in the Amstel.
A byproduct of Jaco's move to Twente is that the process algebra group at CWI, which over the years has been headed by Jos Baeten, Frits Vaandrager, Jan Friso Groote, Wan Fokkink, and finally Jaco van de Pol, will be terminated. It is a fact of life that all (good) things must eventually come to an end, but I cannot help but feel that this is truly the end of an era.
The work of the process algebra group at CWI has played a major role in my scientific development, and I have had the pleasure to collaborate on various projects with several of its leaders mentioned above. (Disclaimer: The process algebra group at CWI is not responsible for the outcome of my work :-)) I like to think that the legacy of that group will be felt for many years to come. Indeed, one of the signs of its impact on Dutch computer science is the fact that all of its leaders over the years are now professors and leaders of strong research groups in some of the best Dutch universities.
Even though my work owes a lot to the intellectual inspiration of the process algebra group at CWI, I only visited CWI once in September 2005, and then only for a day to deliver a talk in the well-known PAM series---well, well-known amongst process algebraists. I guess that this indicates how little I travel around, and that one can be influenced by the work carried out at an institution without having ever visited it. (As another example, I owe a great debt to the Edinburgh concurrency school, but I have never visited Edinburgh.)
I vividly recall that, while introducing my talk at CWI, I paraphrased a famous sentence by the Italian writer Alessandro Manzoni and said that I felt that I had finally gone to Amsterdam to wash my process algebra clothes in the Amstel. With the demise of the process algebra group at CWI, it will unfortunately become a lot harder to wash my process algebra clothes in the Amstel.
Friday, May 11, 2007
What is Time?
When studying process algebras for the description of timed behaviours, one of the early choices that have to be made has to do with the nature of "time". Is time discrete or dense? Is it represented by the natural numbers, by the non-negative rationals, by the non-negative reals or by some other structure?
In order to achieve a higher degree of generality, in the technical report
A. Jeffrey, S. Schneider, and F.W. Vaandrager. A comparison of additivity axioms in timed transition systems. Report CS-R9366, CWI, Amsterdam, 1993
the authors proposed to consider an algebraic definition of time domain. Since I like that definition, and I have it used it myself in a couple of papers, allow me to use this post to publicize it.
Define a monoid (X,+, 0) to be:
All of the structures mentioned above are, of course, time domains, but so is the set {0}. A time domain is non-trivial if D contains at least two elements. Note that every non-trivial time domain does not have a largest element, and is therefore infinite. Note moreover that + is not required to be commutative, so, for instance, suitable sets of ordinals with ordinal addition form a time domain.
I often find it worthwhile to work with time domains specified with the above degree of generality, and to use properties of specific "concrete" time domains only when they are really needed to obtain certain results. However, maybe this is the axiomatic devil in me talking :-)
Why hasn't the above definition become more popular in the literature on timed process algebras?
In order to achieve a higher degree of generality, in the technical report
A. Jeffrey, S. Schneider, and F.W. Vaandrager. A comparison of additivity axioms in timed transition systems. Report CS-R9366, CWI, Amsterdam, 1993
the authors proposed to consider an algebraic definition of time domain. Since I like that definition, and I have it used it myself in a couple of papers, allow me to use this post to publicize it.
Define a monoid (X,+, 0) to be:
- left-cancellative iff (x + y = x + z) implies (y = z), and
- anti-symmetric iff (x + y = 0) implies (x = y = 0).
All of the structures mentioned above are, of course, time domains, but so is the set {0}. A time domain is non-trivial if D contains at least two elements. Note that every non-trivial time domain does not have a largest element, and is therefore infinite. Note moreover that + is not required to be commutative, so, for instance, suitable sets of ordinals with ordinal addition form a time domain.
I often find it worthwhile to work with time domains specified with the above degree of generality, and to use properties of specific "concrete" time domains only when they are really needed to obtain certain results. However, maybe this is the axiomatic devil in me talking :-)
Why hasn't the above definition become more popular in the literature on timed process algebras?
Tuesday, May 08, 2007
Gödel Prize 2007
The Gödel prize 2007, co-sponsored by EATCS and ACM SIGACT, is awarded to Alexander A. Razborov and Steven Rudich for their paper "Natural Proofs", Journal of Computer and System Sciences, Vol. 55, No. 1, 1997, pp. 24-35. (The conference version of the paper was first presented at the Twenty-sixth Annual ACM Symposium on Theory of computing, Montreal, Quebec, Canada. 1994, pp. 204 - 213.)
For discussions of the importance of this result in computational complexity, see here, and here. (Two posts from two of my favourite blogs.) Wikipedia has an entry on natural proofs.
Congratulations to Alexander A. Razborov and Steven Rudich, two outstanding members of the TCS community, for the award.
Addendum: The citation for the award is available here.
Friday, May 04, 2007
Iceland as an International Workplace in Science
Today, I participated in the workshop "Ísland sem alþjóðlegur vinnumarkaður vísindanna" ("Iceland as an international workplace in science") organized by Rannis, the Icelandic fund for research. At the workshop I delivered a presentation entitled How Do you Like Iceland? A View from a Foreign Academic. In case anybody is interested, the slides for my talk are available here. As you can see, I tried to give the Icelandic attendees a cathartic experience and some food for thought.
The latter part of this interesting workshop was attended by a few politicians. I am happy to report that all of them went on record as saying that the amount of funding available for science in Iceland should be increased substantially. Hopefully, these words will turn into deeds after the elections
Thursday, May 03, 2007
Robert H. Sloan on Being an NSF Program Director
Via the Geomblog, a blog that I warmly recommend, I learned about this two-page article by Robert H. Sloan, who was program director for the “Theory of Computing program” at NSF from January 2001 till August 2002. This is a light-hearted piece on why one should serve the community in that role, and what it takes to do a good job at it.
Here is a quote I liked:
Indeed there is, but somehow we all hope that it is somebody else who takes care of running the best and fairest for funding possible.
The Geomblog offers another quote from the piece on the hazardous job of being Dean of Undergraduate Studies.
On the topic of community service, my stint as head of department is going to end in a couple of weeks or so. My department and the School of Science and Engineering have undergone a sudden restructuring, and we have hired Ari K. Jónsson (NASA Ames) to become Dean of the new School of Computer Science. I'll write more on all of the above when the dust settles, and I find some breathing space.
Here is a quote I liked:
Being a program director also gives you the ability to provide two good services to your research community. First, you have some ability to drive the direction of the research community. Second, you get to run the best, fairest competitions for funding possible. There is really quite a difference between the best panel run by somebody who knows the research area, knows who are likely to be good panelists, and is good at managing such things, and a panel run by an outsider who is a fair to middling manager of such things.
Indeed there is, but somehow we all hope that it is somebody else who takes care of running the best and fairest for funding possible.
The Geomblog offers another quote from the piece on the hazardous job of being Dean of Undergraduate Studies.
On the topic of community service, my stint as head of department is going to end in a couple of weeks or so. My department and the School of Science and Engineering have undergone a sudden restructuring, and we have hired Ari K. Jónsson (NASA Ames) to become Dean of the new School of Computer Science. I'll write more on all of the above when the dust settles, and I find some breathing space.
Subscribe to:
Posts (Atom)