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