!!In Memoriam Sheng Yu (1950-2012)

A wonderful scientist, most diligent collaborator and close friend of mine,
''Sheng Yu'', passed away on January 23nd, the New Year of the Dragon, just
before his 62nd birthday. His death was very unexpected: only a few days
earlier we were still corresponding about referee reports concerning our joint
work, and Sheng’s letters contained no mention of a possible illness. Sheng
is missed by his wife ''Lizhen'', his family in China, notably his old mother, as
well as by numerous friends and colleagues.
\\ \\
Sheng worked day after night after day and wanted to check all the details
of a proof. He taught the same rigorous approach and work ethic to his
students and postdocs. After a late dinner he still used to go to the university
to continue his work. Nobody can tell how much the resulting deprivation of
sleep contributed to his untimely death.
\\ \\
This writing contains mostly my personal thoughts and memories. However, I am convinced that everybody who got to know Sheng more closely,
be it as a collaborator, teacher or in some other role, has similar experiences
and recollections of his warm and helpful personality.
\\ \\
\\ \\
Sheng’s studies were delayed by the cultural revolution and he was not
very young anymore when he began graduate studies in Waterloo. That’s
where I met him the first time. He was a student in my course on recursive
functions in 1982, obtaining the grade 105%. Karel Culik and the late Derick
Wood were in those days in Waterloo. Sheng was in contact with both
of them, and became a Ph.D. student of Karel Culik. Karel writes about
him:“Sheng was not only my best Ph.D. student and valuable collaborator,
he was also our family friend.”
\\ \\
I lived in the same building with Sheng, so he became acquainted also
with my wife. He wanted to cook for us. I remember him bringing all the
supplies needed on his bicycle. Sheng was very helpful in our move back to
Finland.
\\ \\
After finishing his Ph.D., Sheng spent half a year in 1986 as a postdoc
in Turku. Our earliest joint work, on the equivalence of derivation (Szilard)
languages and on a special public-key cryptosystem, dates back to his visit.
Sheng was also one of the first users of email, if not the very first, at the
university of Turku. Also my family and many friends got to know him.
We enjoyed his cooking many times. His skill and expertise in many areas,
including sauna heating, became apparent to us. Sheng was even interviewed
by the local newspaper Turun Sanomat because he was regularly playing table
tennis in a local club. The interview had a big picture of Sheng and the coach
of the club discussing “the philosophy of table tennis”.
\\ \\
Sheng was teaching at Kent State University for some years at the end
of the 80’s. Then he moved to the University of Western Ontario in London,
where he has stayed afterwards. UWO is a school very familiar to me, already in 1966-68 I was visiting there. My cooperation with Sheng got a new
beginning in the early 90’s. From 1991 to 2011 I have visited Sheng at UWO
every year, with only two exceptions. Sheng also visited Turku frequently
and, apart from scientific collaboration, served as the opponent and external
examiner of several Ph.D. candidates.
\\ \\
Sheng was a wonderful person to work with. Both insightful and diligent,
he was also willing to do most of the writing of papers and the correspondence in submitting them. In discussions he often had a crucial idea from
which the solution could be deduced. Altogether I had 26 papers with Sheng.
Sometimes we had coauthors: Yo-Sub Han, Tao Jiang, Efim Kinber, Alexandru Mateescu, Kai Salomaa and Derick Wood. Of the topics covered, the
following come to mind: undecidability of the inclusion problem for pattern
languages, codes with a finite delay and the P=NP problem, definition and
study of Parikh matrices and the resulting subword histories and subword
conditions, primality types of PCP solutions, commutativity conditions for
languages, prime decomposition of languages versus length codes, state complexity of reversal and of combined operations.
\\ \\
The matters described above represent only a small part of Sheng’s scientific activity. He had 74 coauthors, and the topics covered extend far beyond
the limits of theoretical computer science. His interests were unusually broad,
and his work ranged from object-oriented programming and parallel processing to computer architecture. He was widely quoted, notably because of his
seminal work in state complexity. In fact, Sheng was for several years planning a Handbook of State Complexity, with several coauthors. The book was
already in the program of the publisher Springer-Verlag but Sheng always
had to postpone the project because of other duties.
\\ \\
Sheng’s chapter on regular languages in the ''Handbook of Formal Languages'' is one of the basic references in the field. A special issue of the journal
TCS was published for Sheng’s 60th birthday, as a token of appreciation in
the scientific community.
\\ \\
Many of Sheng’s numerous Ph.D. students have become well-known scientists or have leading positions in industry. Sheng took very good care of each
of them. Our discussions were often interrupted because Sheng met a Ph.D.
student. For such meetings Sheng had a weekly schedule. Sheng helped students in every possible way, including the details of writing papers, as well
as, various intricacies of everyday life.
\\ \\
The courses given by Sheng were by no means restricted to theory. When
one looks at the list of the courses taught by him, the title of a recent book,
''Rainbow of Computer Science'', comes to mind. Although never the Department Head, Sheng had all the time numerous administrative duties. Sheng
was a member or the chair in roughly half of the some 30 departmental committees in 2011. He was always busy with a heavy work load. Because he
was so conscientious, the result was long work days. The best time to reach
him by phone was midnight in his office.
\\ \\
Sheng was an invited speaker, program committee member or chair in
many leading conferences. He was the originator and steering committee
chair of the international CIAA conference series on ''Implementation and
Application of Automata''. Under Sheng’s guidance the CIAA conferences
have become well-established as the premier venue for research on new types
of applications of automata theory. Sheng organized the big DLT (Developments in Language Theory) conference in London in 2010. By his initiative,
the conference ''Fifty Years of Automata Theory'' was organized in London in
2000. Sheng was also an editor of several journals and took on editorial and
refereeing tasks with the same dedication that characterized his own research.
\\ \\
\\ \\
Sheng was amazingly knowledgeable in classical music. We often went to
concerts together, both in London and in Turku. Recently our music discussions concerned mostly Bruckner and Mahler. Apart from music, Sheng had
many other interests. When discussing religion, sports, politics or personal
relations, Sheng always expressed original ideas, sometimes very strongly.
One could write a book about Sheng’s hospitality and willingness to help.
I am not the only person who has experienced this; there are many others, for
instance my good friend Grzegorz Rozenberg. Sheng and Lizhen organized
big dinner parties, often in their home or in the Springbank Park. Sheng was
always looking after me, driving me around, helping me in stairs, carrying
my bag. The ''Sheng number'' indicates how many times Sheng took me to
or from my hotel during my stay in London. In 2009 and 2010 the Sheng
number was 30 and 32, respectively. In 2011 it was only 22 because my stay
was shorter.
\\ \\
Dear Sheng, our roads parted much too early. I would never have believed
that you go before me.
\\ \\
%%center
''Sit tibi terra levis. Ollos iäti muistettu.''\\
Turku, January 2012, ''Arto Salomaa''
%%
\\ \\
Download the [document|[memsheng.pdf]