Seventy Years Derick Wood

J.UCS Special Issue

Derick Wood was born on an early summer day in 1940, now seventy years ago.

In 2008 a subgroup of Derick's many friends (including - in alphabetical order - Jürgen Albert, Anne Brueggemann-Klein, Vladimir Estivill-Castro, Yo-Sub Han, Helmut Juergensen, Rolf Klein, Hans-Peter Kriegel, Klaus-Jörn Lange, Ming Li, David Mathews, Hermann Maurer, Valtteri Niemi, Arto Salomaa, Kai Salomaa, Hans-Werner Six, Eljas Soisalon-Soininen, Thomas Ottmann, Marti Penntonen, Greg Rawlins, Bob Rosebrugh, Esko Ukkonen, Vijay Vishnavi, Sheng Yu) decided to work together on a special issue of J.UCS to honor Derick Wood. The co-editors of the special issue would be Helmut Jürgensen, Arto Salomaa, Sheng Yu and myself: as managing editor of J.UCS I have the pleasure to write this short introduction.

I want to thank all who have helped to make this a very special issue indeed. Needless to say, there was lots of E-Mail traffic between the four co-editors. In want to thank Helmut for not only contributing a paper but also preparing the very nice bibliography that you find at the end of this issue; Arto for his constant help including writing the report on MSW; and Sheng for his patience and assistance. This list would not be complete if I did not mention Dana Kaiser, my editorial assistant, without whom this issue (indeed I believe all of J.UCS) would have been impossible.

You find in what follows three personal notes from Helmut, Arto, and Sheng. I was tempted to also write one, but reading Arto's description of our joint work with Derick convinced me that I could not add much except to make clear that all the positive things Arto has to say about Derick and also me show what a good, modest and great man Arto is: I am sure that Derick agrees with me that Arto was at the heart of things: even in MSW- the abbreviation of our group- S (Salomaa) is the central figure between M (Maurer) and W (Wood). You also find 14 excellent scientific papers as body of this special issue, and the bibliography mentioned. For all who have contributed in one way or another I believe I can say: We are proud to have Derick Wood as our friend, we admire his achievements and his personality and we are grateful for the many interesting, fun and intriguing meetings with this very unusual man.

For the first time we met in the early 1970s. I am not sure when or where exactly; probably when Derick gave a talk at Kiel University. We did meet and talk in Noordwijkerhout in 1976, at a conference on developmental systems.

Our discussion was initiated by my paper on probabilistic L systems. I believe it was during ICALP in Turku in 1977 that Derick and I started to consider some detailed questions about such L systems. At that time I had just moved from Kiel to Darmstadt. Derick invited me for a visit to McMaster in Hamilton for the late winter in 1978. He was Head of the 'Unit for Computer Science', which I misread as 'Unit 4, Computer Science'; despite Derick's efforts, McMaster did not have a Department of Computer Science until he left for Waterloo; and even after that the climate for Computer Science at McMaster was not completely benign. This visit of 1978 was the first of several visits until I moved to Canada in 1983: they lead to a few joint publications on Markov controlled L systems and on Towers of Hanoi. Through Derick I met David Matthews and Karel Culik from Waterloo.

Through Derick I learnt much about the peculiarities of life in Canada. After all, my visit in 1978 was only my second one to North America (the first one had been to London, Ontario, in 1976): On a weekend I spent much of the time travelling, by car, to what I considered Northern Ontario. I mentioned this to Derick upon my return. Where did you go? Oh, Algonquin Park. A big laugh - you did not even leave the south! To help readers less familiar with the Canadian geography: Hamilton or London is at about 43°, Algonquin is at about 46°, Rome, Italy, is at about 42° and Berlin, Germany, is at about 52°.

I also learnt how to make room for research from Derick, so as not to drown in daily duties: a visit to the library once every week to look at new issues of journals and new books; in addition, one full research day every week with which not even administrative emergencies were allowed to interfere. These were extremely useful strategies during my tenures as chair and dean in Darmstadt.

My next visits took me to Hamilton, Waterloo and London. I remember a meeting which Derick, Karel and I had planned in Waterloo in early April. I had returned from a trip to London by car and stayed in a then famous old hotel - the Walper - in the centre of Kitchener. On that day a blizzard shut down all of southern Ontario. Derick never made it from Hamilton; I was unable to get to the university; Karel arrived on skis at my hotel in the evening.

Summer of 1982: Derick had just moved to Waterloo. We spent my sabbatical in Canada, first in London, then in Waterloo. Karel was still in Waterloo; Arto Salomaa was visiting; Jozef Gruska had just been there. I was also working with John Brzozowski and David Matthews. At that time systolic automaton systems had just been invented. Several papers resulted from joint work during that period including some on systolic automata and, in particular, one on the foundations of cryptography with David; our contribution to the present volume is a continuation of that paper. When sifting through my files I also found the draft of a joint paper with David and Derick on 'super-sharks and sub-fish' and notes on joint work with Derick on generalized Towers of Hanoi.

We (the visitors), Karel and Derick and a few other colleagues at Waterloo gave all their typing material to one secretary in the department. She was also given flowers. Mary and Derick married a few years later and I was happy to attend their wedding.

Derick also visited me in Darmstadt and Potsdam - we travelled together on the Rhine in the early 1980s.

In 1999, I organized WIA, the 4th in a workshop series which Derick had initiated, renamed later into CIAA, in Potsdam, Germany. This time we travelled on the Havel river, under Glienecke bridge and past many historical places which had been inaccessible ten years earlier.

In 1982 and again in 1983, when we moved to Canada, we lived in Derick's house for a few weeks. We got to know Sheng there in 1983; he had just arrived in Canada for PhD studies with Karel. Derick left Waterloo to join Western in London in 1992, but moved on to Hong Kong soon thereafter in 1995. Our research paths had turned into different directions already about 1990 and, with us both deeply immersed in administration and teaching, little time was left for discussing research; at least, on some, albeit too few, occasions all of us got together socially.

The true, vivid and highly spirited Derick as we have known him for nearly forty years - we met and talked several years ago for the last time. This collection of essays is intended to provide an opportunity for Derick to meet us, his friends, colleagues and former students again.

The MSW group, Hermann Maurer, Arto Salomaa, Derick Wood was some time ago very active and successful scientifically. One can perhaps say that it has been one of the most successful and happy triples of scientific collaboration. This special issue is a suitable place to go back to the MSW years and recall some highlights, without trying to be exhaustive in any sense.

Between us we were called MSW1, MSW2 and MSW3, and we were also wearing T-shirts with those names. Here we mostly refer to the three persons as M, S and W. May 1975 can be considered as a starting point. Then M and S worked on "L forms", grammar forms for Lindenmayer systems. (Grammar forms, initiated by Seymour Ginsburg, was a hot topic those days.) S and W had worked earlier together, so it was an immediate idea to form a triple. The cooperation kind of faded out around 1984, although there was an MSW paper still in 1991. Why it faded out was explained by saying that we got more involved with other MSW: Hermann with Mupid (of course everybody remembers this important forerunner of networked microcomputers), Arto with Sauna and Derick with Wife. The period between 1975 and 1984 was filled with active, sometimes hectic, cooperation. We really worked hard and were enthusiastic.

Altogether 30 MSW papers were published in main journals, including two in J.ACM. We will return below to the statistics. We also presented the stuff in many conferences, although rather seldom all three of us were present. As a matter of fact, we always worked as follows. Two of us got together in the other's place and wrote the paper. Later the third one checked it. We don't recall a single instance where we would have produced a paper when all three were present. But each of the combinations MS, MW, SW met at least once a year.

When two of us were together, we realized how much more we could produce together than alone. Somehow the members complemented each other. A new idea usually comes from an individual but the partner is essential in the further development. He can often immediately tell whether the idea is nonsense. If you work alone, you can spend days in a blind alley. Another factor that made the MSW work so fruitful and pleasant was that nobody ever counted the amount of work he did. Everybody tried his best and did not worry that the amount of work was evenly distributed.

Those days it was difficult to get travel money. Most of the time the guest stayed in the host's home. This of course meant that working days could be some 14 hours. Many memorable and nice happenings come to mind.

When we were in Finland, the work continued also in sauna. Indeed, we used to speak of "three-sauna problems" instead of "three-pipe problems" of SherlockHolmes. We used to say that the arteries in your brain get really open in sauna. However, beer surely closes them. One of our nice results was obtained when W was on antibiotics because of an ear infection. Then we could not take beer in sauna.

W liked to stay in S's country home. We still call the middle room upstairs "Derick's room". The place is very quiet, no traffic or people nearby. Still during the summer W used to complain about the "terrible noise" during the night. The bees started their activities in apple trees already around 2 a.m. because it was so light. W got up latest at 6 and had a good time with S's mother-in-law although they had no common language.

Another time S noticed an error that affected both our ongoing and already published work. How to proceed? Time to go to sauna! There M started to talk like an oracle. Everything was settled, and the published paper corrected.

Our friend Grzegorz Rozenberg and S firmly believe that "M-quality" is the best there can be in hospitality or organizing various events. S surely experienced this during MS-gatherings: special huge coffee cup, trips to the very good "Altes Fassl" sauna and a delicious Holstein Schnitzel afterwards. M even found, by some magic, S's favorite slippers lost some months earlier in a different location.

W used to have students from exotic countries living in his house. Often they brought from their homes some food and spices. When S was eating, he took quite a generous amount of sauce from a jar bearing an etiquette of some customary American company. Nobody said anything. Heroically S ate his food although even a small amount of the stuff brought hellish fire in his mouth. Later he learned that some hot witch stuff from Trinidad just happened to be, very misleadingly, in that jar. The following night S had nightmares and peculiar dreams. In one of them S and W were sitting in the train from Bolton to Blackpool. (W comes from Lancashire, and S and W often talked about Bolton and Blackpool football teams.) W presented some ideas concerning the problem S and W had been working on. In the morning S remembered the ideas. They were good. The result used to be called "The Bolton-Blackpool Train Theorem".

The work on language interpretations produced beautiful pictures resembling flowers when the mathematics involved was depicted. (Incidentally, many of these results were rediscovered much later by graph theorists who presented them within the framework of graph morphisms.) There were difficult problems concerning density. S proposed going to a florist with a question: I am looking for flowers that grow so densely that it is even theoretically impossible to plant a new flower between two already existing ones. W succeeded in preventing him. Later Emo Welzl solved the problem.

Most of MSW work on grammar forms and L forms is summarized in the last chapter of Volume I of the Handbook of Formal Languages. Other topics studied were normal forms for context-free grammars, pure grammars, L codes and number systems. The work appeared in the following journals.

• Information and Control, Theoretical Computer Science; 5 papers each,
• Journal of Computer and System Sciences, RAIRO/Theoretical Computer Science; 3 papers each,
• ACM Journal, SIAM Journal of Computing, Mathematical Systems Theory, Discrete Applied Mathematics, Acta Informatica, International Journal of Computer Mathematics; 2 papers each,
• Information Processing Letters, Annals of the Finnish Academy of Sciences; 1 paper each.

We conclude with a song presented during ICALP'77. Apart from MSW, the persons mentioned are Aristid Lindenmayer, Grzegorz Rozenberg, Thomas Ottmann and Kai Salomaa.

On Finnish Sauna (Melody: Oh Susanna)
Adapted by MSW1 and MSW3 for MSW2

We have come from over all the world / with towels on our knee
We have gone to Arto and Turku / in Sauna there to be.
Oh Finnish Sauna / o do we wait for ye
we have come from over all the world / with towels on our knee.

In Finland it's the king who reigns / in Tarzan's home it's Jane
L forms, L systems, L people / oh what a lovely game.
Oh Finnish Sauna / o do we wait for ye
we have come from over all the world / with towels on our knee.

Bolgani had a great idea / but also too much rye
His problems they could soon be solved / 'cause sauna heat was high.
Oh Finnish Sauna / he cannot wait for ye
he came from Utrecht and Antwerp / with towel on his knee.

A Wood he cannot swim that well / is rotten and not dry
His problems they could soon be solved / 'cause sauna heat is high.
Oh Finnish Sauna / he cannot wait for ye
he's come from Lower Canada / with towel on his knee.

Now Thomas joined the L form gang / that makes him a great guy
His problems they will soon be solved / 'cause sauna heat is high.
Oh Finnish Sauna / he cannot wait for ye
he's come from Western Germany / with towel on his knee.

And Aristid created K / this was no such good try
Therefore he then proposed an L / in sauna heat so high.
Oh Finnish sauna / he cannot wait for ye
he has come from Utrecht in Holland / with towel on his knee.

There was a young photographer / his name was L.L.Kai
His problems were increased a lot / 'cause sauna heat is high.
Oh Finnish Sauna / he does not wait for ye
whenever he is asked to go / he says "oh no not me".

When opening the conference / friend Tarzan wore a tie
His problems they will soon be solved / cause sauna heat is high.
Oh Finnish Sauna / he cannot wait for ye
he wants to be there all the time / but this can never be.

I have known Derick for almost thirty years. I first met Derick in 1983 when I was a PhD student at the University of Waterloo. I had already heard about him through Arto Salomaa and was considering him as a potential supervisor of my PhD thesis. Although he did not become my supervisor, we were pretty close both academically and socially. He was on my thesis advisory committee and I rented a room in his house for two years. Later he moved to the University of Western Ontario. We became colleagues at the Department of Computer Science there. We had a joint NSERC (Natural Science and Engineering Research Council of Canada) Strategic grant and had a number of joint research work there. We started the CIAA (WIA) conference series when he was still officially at Western but on leave at Hong Kong University of Science and Technology. We kept seeing each other either in Hong Kong or in Canada almost every year after he moved to Hong Kong.

During the period of time when Derick was with the University of Waterloo, his main research area was in algorithms and computational geometry. However, he was also writing his book in theory of computation (entitled Theory of Computation) then. Quite often he talked to me about his book and asked me to provide examples for certain problems in the book. He spent quite much time in writing the book, which was very well written and was popular as a textbook in a number of universities.

When Derick was with the University of Western Ontario, his research interests gradually shifted back to automata and formal language theory. We two jointly applied successfully for an NSERC Strategic Grant for automata implementation, especially the development of the Grail system, which is a computational system for formal language objects. The grant was very important for the development of the Grail project at that time and the Grail+ project later.

Another important collaboration between Derick and me was the creation of the conference series of CIAA (International Conference on Implementation and Application of Automata). It was initially named WIA (Workshop on Implementing Automata) because we thought that the name ''Conference on Implementing Automata'' (CIA) would not be a good idea. Later in 2000, we changed the name to CIAA. The initial suggestion of the conference was raised by Darrell Raymond who was a Postdoc supported by the NSERC strategic grant held by Derick and me. Darrell first discussed with me about the conference. Both of us were very enthusiastic about the idea. We then discussed the idea with Derick. He strongly supported the idea. We successfully organized the first conference in 1996 at Western. Since then, the conference has taken place in many different countries in North America, Europe, Africa, Asia, and Australia. The conference provides a forum for researchers to present their results in automata application and implementation, which is an important new direction in automata and formal language research. Note that automata theory was very much motivated by applications in the 1960's and 1970's. However, automata implementation was rather straightforward then since the sizes of the automata used in applications were relatively small. In recent years, many new applications of automata have appeared in natural language and speech processing, software engineering, parallel processing, etc. Automata used in those applications can be very large.

Similar to the situation in the 1960's and 1970's, automata theory has been again motivated heavily by applications. The implementation of automata has become an important issue due to the large size of automata used in new applications. Derick was the initial steering committee chair of the CIAA (WIA) conference series. He has shown his great foresight in automata research and studies.

Derick was very creative in research in general. He was quick to come up with new ideas. He was very conscious about the meaningfulness of his research topics. His contribution in research was significant and had a great influence. Personally, he was warm hearted, straightforward, and easy-going. I consider him as a teacher and a role model in research, and a good friend in life.