Second ICE-TCS Symposium

Last Wednesday, 31 May, ICE-TCS organized its second one-day symposium. The aim of these "theory days" is to give the Icelandic computer science community a bird's eye view of the area of Theoretical Computer Science, with emphasis on the research fields of the members of the centre.

The second symposium was graced by the presence of three outstanding keynote speakers from outside Iceland, namely Wan Fokkink, Jan Kratochvil and Moshe Vardi. The presentations by the invited speakers were complemented by 25 minute talks delivered by Ragnar K. Karlsson, Magnús M. Halldórsson, Anders Claesson/Sergey Kitaev (who shared the closing slot) and myself.

The morning session was devoted to "Volume B" talks. Moshe gave the meeting the best of starts with a talk describing the design of the ForSpec Temporal Logic (FTL), the new temporal logic of ForSpec, Intel's new formal property-specification language, which is today part of Synopsis OpenVera hardware verification language. The focus of Moshe's talk was on design rationale, rather than a detailed language description, and during the presentation he offered a very accessible discussion of the field of model checking, of linear and branching time temporal logics, and of the automata-theoretic approach to LTL model checking. Moshe also told the audience that his analysis of the relative merits of LTL and CTL has been referred to as "character assassination" by some of our colleagues :-)

Moshe's talk was immediately followed by the second keynote address, which was delivered by Wan Fokkink. Wan's talk presented joint work with Bard Bloom, Rob van Glabbeek and Paulien de Wind devoted to the systematic derivation of congruence formats for various behavioural equivalences in the linear-time/branching-time spectrum from decomposition results for the modal logics that characterize them.

I closed the morning session with a talk presenting joint work with Taolue Chen, Wan Fokkink and Anna Ingólfsdóttir on the axiomatizability of bisimulation equivalence over the language BCCSP extended with the priority operator.

The afternoon session was devoted to "Volume A" talks. The first talk in that session was delivered by Jan Kratochvil, who presented a survey of work on graph homomorphisms, viz. edge-preserving vertex mappings between two graphs. He showed how the use of graph homomorphisms unifies previously defined and independently studied notions such as graph covers, role assignments, and distance constrained graph labelings. Jan surveyed recent results and open problems related to these notions, with special emphasis on the computational complexity issues. He also mentoned connections to the Constraint Satisfaction Problem and the Dichotomy Conjecture.

Graphs featured also in the two 25 minute talks that followed Jan's address. The first talk was delivered by Ragnar Karlsson, who had defended his MSc thesis the day before. (For the record, Ragnar is the first MSc student to graduate under the suprvision of a member of ICE-TCS, viz. Magnús M. Halldórsson. Congratulations, Ragnar!) Ragnar presented the main results in his MSc thesis related to so-called strip graphs. These graphs are formed by an interval graph together with an equivalence relation on the vertices, and can be used to model the classic Job Interval Selection Problem (JISP) on one machine. In this problem, the input is a set of jobs, each of which is a set of intervals, and the object is to select at most one interval from each job such that no two chosen intervals intersect. This corresponds to being given multiple possible run-times for each job and trying to schedule as many jobs as possible. This problem is known to be NP-complete. However, strip graphs provide a very nice way to model the input of this graph and, by using structural observations of the input, Ragnar was able to find a fairly efficient exponential algorithm to solve this problem.

Magnús M. Halldórsson presented the next 25 minute talk, reporting on joint work with Takeshi Tokuyama and Alexander Wolff. The scientific director of ICE-TCS considered the problem of computing a non-crossing spanning tree of a graph that has been embedded in the plane. This problem is known to be NP-hard. During his talk, Magnús considered the complexity of the problem in terms of an input parameter k: the number of pairs of edges that cross. He gave an algorithm with a dependence on k being k^sqrt{k}, improving on recent work by Knauer et al. who gave a simple algorithm that runs in linear time, for fixed values of k; the dependence on k was 2^k.

The meeting was brought to a fitting close by Anders Claesson and Sergey Kitaev, two of the members of the ICE-TCS combinatorics group, who presented an accessible survey of work within the area of permutation patterns. A (permutation) pattern is a permutation of a totally ordered set. An occurrence of a pattern P in a permutation p is a subsequence of letters of p whose relative order is the same as that of the letters in P. As an example, the permutation 461352 has three occurrences of the pattern 321, namely the subsequences 432, 632 and 652. In 1969 Don Knuth pioneered this work by showing that the stack sortable permutations are exactly the 231-avoiding permutations. Anders and Sergey gave a brief introduction to the field, starting with a presentation of Don Knuth's result.

The symposium was attended by about 25 participants. Unfortunately, not many staff members from the local computer science departments were present at the talks. However, it was pleasing to see that several MSc students in Computer Science and Mathematics showed intellectual curiosity and attended the whole event. This bodes well for the future of research in (Theoretical) Computer Science in Iceland.

I myself believe that we should teach our postgraduate students that attending talks is a fundamental part of their scientific upbringing, and that we should teach this, like everything else, by example. The worst that can happen when attending a talk is that one learns at least about the existence of some research area or result that increases one's knowledge of Computer Science as a whole. And, who knows, maybe that knowledge may even turn out to be useful in our own work tomorrow. In research often help comes from the most unexpected sources.