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.