From the Bulletin of EATCS No. 96, 08/2008#

A Dialogue on Theoretical Computer Science with Professor Arto Salomaa#

by Cris Calude

Professor Arto Salomaa is one of the most important theoretical computer scientists.

Professor Salomaa does not need any introduction to the EATCS community: he served as its President (1979–1985) and for many years he is producing the “Formal Language Theory” column for this Bulletin. His many articles and books not only influenced, but also shaped, areas of theoretical computer science.

Professor Salomaa was awarded many prizes, awards, and distinctions, clearly more than one can enumerate in this short introduction: among them, seven honorary doctorates, membership in various learned Academies, Professor of the Year in Finland in 1993, elected one of the twelve Academicians of the Academy of Finland, and winner of the 2004 EATCS Award.

Cristian Calude: Let me start this dialogue by citing a paragraph in your recent email: One issue there was a list of people who did not get the Fields Medal. Did it ever occur to you that Gödel did not get it, although he was fully eligible in 1936? It didn’t, maybe because I see Gödel beyond the recognition mortals get. Why do you think Gödel did not get it? Could it be because mathematical logic is not mainstream mathematics? Or because Gödel’s results are negative?

Arto Salomaa: Certainly mathematical logic was not in the mainstream, especially if you think of those who decide about the Medal. It is often much easier to recognize somebody who solves a problem that you yourself tried hard to solve without success than to give credit to a person whose work now seems obscure but is much later quoted as the greatest mathematician of the century. The rules for the Fields Medal (age limit) exclude persons whose contributions become visible only after some time. Also John von Neumann missed the Medal the same time as Gödel.

CC: Yuri Matiyasevich also didn’t get the Fields Medal for his work on Hilbert’s Tenth Problem (also a negative result) completed when he was 24 or 25.

AS: I don’t think negativity is an issue here. Besides, it is often difficult to tell whether or not a result is negative. What about the result of Andrew Wiles? The Theorem is true but there are no solutions for the Diophantine equation. When you give out a prize, an evaluation of some kind is needed. The latter is always difficult. History is full of examples where the posterity does not agree with the result of the evaluation. Mozart, Beethoven and Schubert are not honorary citizens (Ehrenbürger) of Vienna, whereas many much lesser composers are. Kubrik and Hitchcock did never get the Oscar for the best director. And so forth.

Let me continue a little bit about evaluations. I have been in many committees evaluating departments, etc. It is only very natural that people getting bad evaluations protest: usually the booklet of counterarguments is much thicker than the original committee report.

Computer scientists have to approach wealthy patrons, whoever they are, in their applications for projects. I have always emphasized to my students and colleagues the importance of a carefully written application for a successful evaluation. Horace approached the original patron Maecenas (whose name stands for “patron" in many languages) with the famous words Maecenas atavis edite regibus (Maecenas, born of monarch ancestors). Apparently, you have to use a different approach nowadays to sell your work. It seems that right now you should use the words bio and/or nano.

To conclude, I am very happy that I don’t have to write applications any more and choose research topics by their eventual applicability.

CC: What attracted you to mathematics in the first instance?

AS: My family constituted a very good starting point, my father was the professor of philosophy at the university of Turku. As a small boy I used to think of questions such as the dependence of the parity of the sum on the parities of the summands. (Of course I did not use these terms.) Children were very much left alone during the war because all adults were somehow involved in war activities. Opposing gangs were formed, and I used to be good in breaking codes. There were also other kinds of mathematical problems around. I came up with the rule to find out the number of games when everybody meets everybody else in a league of football teams. My friends did not believe that there could be such a general rule and came to me with a counterexample. They had chosen 14 Finnish teams and made a list of all games. The list contained only 90 games. But a careful examination showed that the game between two Turku teams, TPS and TuTo, was missing. Maybe this suggests that the referees of scientific papers should be careful before making very negative claims.

It was not at all clear that I would start studying mathematics at the university. I went to a classical lyceum and was also very interested in Latin. However, I wanted to become a researcher, and Latin seemed to me as a thoroughly investigated and bounded area, whereas mathematics is growing all the time. This turned out to be very true: my coming research areas did not exist or were very small when I started my university studies in 1952.

Actually my father wanted me to become a lawyer since I was “arguing all the time". I wanted to have a broad start and, in addition to mathematics, I studied philosophy and history.

CC: Please tell us more about your graduate studies in Turku, Berkeley and Helsinki. Who influenced you during those years?

AS: It is very hard to imagine the attitudes in the academic circles in Finland still in the 50’s. I was strongly advised against going to Berkeley because “American universities are mostly football and other sports". My friend, a physicist, was recommended to get a doctorate also in Finland, although he had one from Oxford. Publications were almost without exception in Finnish annals and journals. This is true also of my first publications.

There were two professors, Kustaa Inkeri and Lauri Pimiä, in mathematics when I started my studies in Turku. Inkeri was a well-known number-theorist. He was also an excellent lecturer who demanded perfectionism in mathematical writing. Pimiä had bad eyes but an unbelievable geometric intuition. I think he would have made excellent contributions to computational geometry.

In Berkeley I noticed at once how shallow my background was. But I did a lot of reading and there were many good courses given by great people. Alfred Tarski gave a course on the foundations of geometry, the material appeared later as a book. He was dressed up elegantly and chain-smoked Winston cigarettes. Almost everybody smoked those days, including myself. Tarski and Leon Henkin conducted a seminar in logic with visitors such as Roger Lyndon and Robert Mc- Naughton. Henkin was brilliantly clear in every sentence he said, also in conversations. Tarski hosted parties in his home up on the Berkeley Hill. I also met Alonzo Church there, he later in the 70’s visited Turku. G. Polya wanted to discuss with me a few times. He had intricate questions about the Finnish language.

The course that influenced me most was John Myhill’s seminar during the spring 1957, where the topics were chosen from the newly appeared red-cover Princeton book Automata Studies. Myhill also gave lectures himself. He was very impressive but also out of this world, and occasionally taken to a sanatorium.

My own work was about self-reproducing automata. In the construction I gave detailed instructions for all specific configurations. The necessary components were randomly scattered around on the plane, a welding operation was introduced, and so forth. There were even plans for a publication but it never came into being.

Berkeley was a wonderful place also because famous people gave public lectures there: many Nobel Prize winners, Martin Luther King, . . . People were studying very hard, reading rooms were full until 11 PM. My stay was funded by the so-called ASLA grant. The grants originated from the fact that Finland was the only country who continued paying its FirstWorldWar debts to the U.S. Then at some stage it was decided that the payments will be converted into grants.

I always liked classical music. San Francisco is a wonderful place for concerts, and also opera for a short season. Very cheap tickets were available for students to standing places. Karajan, Bernstein, Szell, Rubinstein, Gould, Menuhin, Björling, Schwartzkopf, Tebaldi were all there. I also went to concerts by Louis Armstrong and Elvis Presley with some of the logicians.

But it was not my intention to stay in America. My father, mother, sister and brother were in Finland, as well as my wife-to-be, and I was not sure how long she was going to wait for me. Because of the reasons discussed already above, I preferred to get my Ph.D. in Finland. In many discussions and in library search I had come up with a nice topic on many-valued logic, more specifically the composition theory of many-valued truth-functions. I had some preliminary results already when I returned. Automata theory would have been much too esoteric to qualify as a thesis topic in mathematics in Finland. Of course no such thing as computer science existed.

This answer became quite long. As regards Helsinki, I never had any actual studies there but took there an intermediate degree, because of formal reasons.

CC: You graduated 24 PhD students; this gives you a huge experience in supervision. What should a new PhD student know before starting his graduate studies?

AS: It is hard to imagine anybody having a better group of Ph.D. students. I have learned enormously when working with them. I have had a few students during my visits abroad. I have also had some foreign students in Finland, especially during the time of the Turku Centre for Computer Science, TUCS. But the majority of the students has been Finnish. Many of them are really well-known scientists, some of them have already retired. Most of my students have become university professors but there are also other careers: Nokia, army cryptography, software development . . .

What should a Ph.D student know at the beginning? It depends very much on the topic. Perhaps one can say that some areas of theoretical computer science require rather little previous knowledge, and you can still get good results if you work hard. One of my students did not know anything about formal languages when she started but after three years her paper was accepted to ICALP.

CC: How do you choose a problem to work on? Do you work on a single problem at a time or, in parallel, on more problems?

AS: It depends on the problem. Sometimes you want to settle something really furiously, and cannot get rid of the problem. In general it is better to have several problems to work on. If you get stuck on one of them, you can work on the next one. Maybe after a while something new opens up about the first problem.

CC: Please tell us about the famous MSW (H. Maurer, A. Salomaa, D.Wood) team?

AS: My cooperation with Hermann and Derick started in 1975 and continued very active until early 80’s but an MSW paper was published still in 1991. Between us we were called MSW1, MSW2 and MSW3, and we were also wearing T-shirts with those names. Why the cooperation kind of faded out around 1984 was explained by saying that we got more involved with other MSW: Hermann with Mupid, Arto with Sauna and Derick with Wife.

But during the high period we really worked hard and were enthusiastic. Close to 40 MSW papers were published in main journals, including several in J.ACM. 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. I 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.

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

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.

Apart from MSW and G. Rozenberg, I have been lucky to have many scientific collaborators who have been great to work with. Of the senior people Karel Culik, Ferenc Gécseg, Werner Kuich, Gheorghe P˘aun, Sheng Yu, yourself and the late Alexandru Mateescu come to mind.

Coming back to MSW, I would like to emphasize the wonderful social atmosphere around the group. I quote here a part of a song during ICALP-77 in Turku. On Finnish Sauna (Melody: Oh Susanna). Adapted by MSW1 and MSW3 for MSW2, Turku, July 1977

We have come from all over 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 all over the world / with towels on our 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.

Then Hermann says he’ll go to Graz / we really don’t know why.
His problems they will soon be solved / ’cause sauna heat is high.
Oh Finnish Sauna / he cannot wait for ye
he’s come from Karlsruhe / with a towel on his knee.

When opening the conference / friend Arto 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.

CC: Please tell about your collaboration with G. Rozenberg.

AS: I met Grzegorz the first time in May 1971. He had been in Holland about one and half years, and was running a country-wide seminar in Utrecht, where also foreign speakers were invited. I got an invitation (by ordinary mail, not by phone) from G. Rozenberg. I was not familiar with the name previously. He waited for me at the airport and arranged our meeting through loudspeakers. He looked much younger than what I had anticipated. He drove a small Volkswagen. We got immediately into a very hectic discussion about parallel rewriting and L systems. After about one hour I started to wonder why we had not yet arrived in my hotel in Utrecht. It turned out that we were still on some side streets of Amsterdam.

L systems and biologically motivated stuff in general turned out to be an area where our scientific cooperation has been most vivid. The most important outcome is the book Mathematical Theory of L Systems, and L systems play an important role also in the Handbook of Formal languages, as well as Cornerstones of Undecidability.

I would like to tell about the Handbook. What I say illustrates very well Grzegorz’s friendliness, efficiency and professionalism. In March 1994, Grzegorz suggested to me: “Let us make a handbook on formal languages." We started planning it immediately. It was lots of work but also lots of fun and good jokes. Everything worked out very smoothly. In less than three years, a copy of the Handbook (three volumes, more than 2000 pages, 3.6 kilos altogether, more than 50 authors) was in the library of Turku University. Are there similar examples of such speedy editing of such an extensive handbook-type scientific work?

Already very early our relationship grew much closer than just scientific collaboration. Grzegorz often says that he has no biological brothers but two brothers of choice, Andrzej Ehrenfeucht and me. Also nowadays we keep close contact, and I often ask his advice in difficult situations and for hard decisions. My brother has an immense supply of jokes and anecdotes, always suitable to the occasion. Often a somewhat sad situation entirely changes by his comments.

One year I missed the meeting of the editors of the EATCS Texts and Monographs Series. My right shoulder had been operated, and outer rotations of the arm were strictly forbidden. Grzegorz called me from the meeting telling that it had been decided that Arto Salomaa will be asked to write a book about the geometry of outer rotations.

Grzegorz also lives in the world of magic. He surely is on a true professional level in close-up magic, mainly cards. His name as a magician is Bolgani. Actually this was his name in my family already before he started to use it as a magician. Let me tell about my own impressions during one of his typical shows. Bolgani often presents a sequence of illusions within the framework of a story.

Bolgani explains that in Chinese the names of the suits hung tao (heart) and hei tao (spade) are similar, and therefore some confusions may rise. But now we try to be careful. He then shows the audience some hearts and puts them on the table, as well as some spades and puts them also on the table, far from the hearts. “So this pile is hung tao?" The audience agrees. “And this is hei tao?" Again consensus.

Bolgani then entertains the audience and talks about various matters. About owls. About sauna. That laughter, and for him nowadays the grandson Mundo, is the best medicine. That one should never assume anything. That the only place where success comes before work is dictionary. Then Bolgani goes back to the cards. “So this is hung tao and this hei tao?" General agreement.

But when he shows the cards, it is the other way round. “Too bad, let us see what happens if we put everybody in the same pile." He puts first the pile of hearts on the table and the spades on their top. Again some entertainment. “Now let us see if they interchanged again." Bolgani picks up the cards and shows them. “This is absolutely crazy. They are all zhao hua (club, grass flower)!"

CC: May I ask you about your current projects?

AS: I cannot speak of any projects. As you know, I am retired and have no possibilities in Finland to apply for funding for projects. But I surely continue my own research. Recently I have been interested in some basic questions about automata and formal languages: decompositions of languages, counting the number of (scattered) subword occurrences in a word, state complexity of finite automata. I also have various editorial jobs: some collective volumes, EATCS Monograph and Text Series, various journals.

CC: You have authored or co-authored 46 influential books, translated in many languages. Formal Languages (1973) made the list of the 100 most cited texts in mathematics in 1991. In retrospect, which one gave you most pleasure and satisfaction?

AS: I would rather speak of 11 than of 46 books. Writing a book is quite different from editing it. However, the Handbook of Formal Languages, already referred to earlier in this interview, caused very much work, also because I wrote several chapters myself.

You always like a book you are currently working on, so it is difficult to state any preferences. In retrospect, perhaps my first book Theory of Automata gave me most satisfaction. This in spite of the fact that the publisher, Pergamon Press, did an awful job in printing and screwed up the marketing.

CC: With only twelve Academicians, the Academy of Finland seems the smallest Academy in the world, certainly smaller than the 40-member Académie Française. Tell us more about it. You have been a member of the Finnish Academy of Science and Letters for many years. From outside it seems a bit strange to have two Academies...

AS: This is really confusing. Finland has two “normal" academies (of sciences and letters). The Swedish-speaking one was established already in the 1830’s, the Finnish-speaking one exactly 100 years ago, in 1908. The latter one was established because it was difficult for Finnish-speaking researchers to become members of the former. As you know, Swedish is still an official language in Finland. The members of these two academies are not called academicians.

The government institute corresponding to, say, NSF is called the Academy of Finland. It distributes funding for research projects and has also positions for junior and senior researchers. I was a long time an academy professor, associated with the Academy of Finland. It can also convey the honorary title of an academician as a recognition of research achievements. By law the number of such academicians is restricted to twelve. I am nowadays used to be the oldest, but in this group I am the second youngest.

CC: What areas of theoretical computer science will probably be taught in 2108?

AS: I don’t want to predict. Let me quote some well-known predictions made less than sixty years ago. Optimistic: computers of the future will weigh only five tons. Pessimistic: there is a true market for at most five computers in the world. However, I would like to add that mathematics will be there and so will the problems and areas that are really interesting mathematically.

CC: You are serving in the editorial board of many journals. What is the future of academic journals, paid subscriptions, open source, mixture?

AS: This is a very broad question, and I cannot say much. Clearly the tendency is towards electronic publications. Really many journals are not any more available in our university library as paper copies. However, I have the feeling most people still want to see their work as printed in a journal. It then seems more finalized. The first electronic journal in our field, Journal of Universal Computer Science, is ideal in this respect. Contributions are available also as thick yearly volumes.

Whoever publishes, be it electronically or otherwise, needs some compensation. Somebody has to organize the refereeing etc. It is impossible to avoid payments.

CC: Finland is an economical and scientific miracle. Can you briefly explain this phenomenon?

AS: If I give only one reason it is that Finland was able to defend itself, in the Winter War, against the attack of a vastly superior military power and thus avoid foreign occupation. There are very few instances of small countries in history who could do that. This gave real motivation and impetus for war reparations and building up the country. Talented people wanted to stay here instead of moving abroad, legally or illegally. Just compare Finland with the Baltic countries who, in a definite sense, lost fifty years.

This is my answer. Somebody else might give a different answer. But I was five years old when the Winter War started, and still remember the day very well.

CC: Your webpage lists two “official” pastimes interests: grandchildren and sauna. Please tell us about your grandchildren.

AS: They are much bigger now than in the picture on the webpage, two are already adults. They have given me much happiness. I have a big picture of myself with Grzegorz, with the subscript Happiness is being a grandfather. The grandchildren live 300 kilometers from Turku but the distance was never long for me.

I have always liked children, and many children call me Äijä, grandfather. I like to talk with children. They don’t pretend to be anything and are honest. “Äijä eats like a pig", was a statement about my table manners. No recognition could be better than the one my grandson, then six years, gave on a trip where we had to cross several borders: “It is so easy for us to travel because Äijä knows all languages!"

CC: Your passion for sauna is well known. For example, Salosauna was presented by Abel and Salamander in Badplätze, Oase, 2008, 291–297. At least two articles about sauna have appeared in this Bulletin: “What computer scientists should know about sauna" (1981) and “Myhill, Turku and Sauna Poetry: Recollections arising from the EATCS Award” (2004). You have introduced me to Finnish sauna in 1991 (during my visit to Turku, still vivid in my memory), and, being so impressed, I had a dream that one day we will have one (this dream came true in 2001). What is Salosauna and why it is not only unique, but also the best?

AS: Indeed, a couple of German sauna books have recently published my views about sauna. Finland, a country of 5.2 million people, has 2 million saunas. Only recently the number of cars exceeded the number of saunas. I could have answered your previous question, about Finland’s success, by referring to sauna!

Every true sauna lover thinks his sauna is the best. Salosauna was built of thick logs already in the 19th century. I made there some reparations, trying not to destroy the original atmosphere. The decisive criterion in comparing saunas is the quality of sauna heat, löyly. The most common mistake, especially in foreign saunas, is that the stove is much too small. No luxury in the surroundings can compensate the stove being a tiny miserable metal box. I always wonder why sauna builders become stingy when the heart of sauna is concerned. I want to add that, during the three ICALP’s in Finland, Turku 1977 and 2004, Tampere 1988, an excellent sauna session has been included in the conference program.

Let me end by quoting a few lines by Hermann Maurer.

Salosauna, once again
heightens joy and heightens pain.
Underlines what maybe counts
what this life in truth amounts.
Through this sauna’s windowpane
past some sunshine, wind and rain,
our hearts and eyes and ears
cut through all the passing years:
see the friendships that stay strong,
newborn faces, happy song.
Memories taste sad and sweet
as they rise in sauna’s heat.

CC: Many thanks.

We are grateful to Cris Calude and the EATCS for making this dialogue available for the Academia Europaea Information Server.

Imprint Privacy policy « This page (revision-5) was last changed on Monday, 17. July 2017, 14:40 by Kaiser Dana
  • operated by