In Memory of Sheng Yu (1950-2012)

(photo courtesy Manfred Kudlek)

Yesterday I heard the sad news that Sheng Yu, a Chinese-Canadian computer scientist, and a good friend and colleague, died this weekend in London, Ontario.

I first met Sheng Yu shortly after I arrived in Waterloo as an associate professor in 1990, but I can't remember the circumstances. At the time he was working actively with the late Derick Wood (for whom Sheng gave a memorial talk just last year), who taught at Waterloo at the time, so it probably was through Derick.

We wrote a paper together on regular languages with polynomial densities. Later, Sheng asked me an interesting problem about whether it is possible to find a sparse language L such that L² = Σ^*. I found one example, and Andrew Granville found another. In 1994, we all wrote a paper with Per Enflo, who had found yet another example. Our last joint paper was in 2001, joint with Mike Domaratzki, on covers of formal languages. Although we did not work actively together in the last ten years, we often spoke on the phone.

Sheng got his master's degree in computer science from Waterloo in 1982, under John Beatty, and his Ph. D. in 1986 under Karel Culik II. Then he taught for several years at Kent State before taking a position at the University of Western Ontario.

Sheng's work on state complexity is well-known in our community. His influential 1994 paper with Zhuang and Salomaa is his most-cited non-survey paper (with Google scholar giving 156 citations), and re-introduced state complexity as a research topic to the theoretical computer science community. (It turns out that many of the results in that paper were already discovered by the Soviet computer scientist Maslov in 1970, but Maslov's results were either not known or quickly forgotten in the West.) Since then, state complexity became an active area of research, with dozens of papers published.

When I first met Sheng, I thought his only interests were about automata. I quickly found out I was wrong. He was incredibly broad, publishing papers on object-oriented programming, parallel processing, parallel programming, and teaching a wide variety of courses at UWO, including computer architecture, programming languages, and of course, automata theory.

Sheng Yu also had influence in other ways. He was one of the people responsible for the CIAA conference series, and served on the program committee of dozens of conferences. He also was one of the people responsible for the Grail system, which is widely used to carry out experiments with automata. He supervised dozens of graduate students.

Sheng told me a little bit about his life in China. He got his Ph. D. older than many of his contemporaries because his life was disrupted by the Cultural Revolution. He still had family in China, which he kept in close contact with.

About 5 years ago In 2000, Sheng had a heart attack while playing tennis at UWO. Luckily, he was very near the university hospital, and immediately went there, and the good care he received saved his life. He told me that his family had a history of heart disease and that he had high cholesterol, which he tried to control through diet.

I will miss him as a colleague and friend.