Seymour Ginsburg

Seymour Ginsburg (December 12, 1927 – December 5, 2004) was an American pioneer of automata theory, formal language theory, and

database theory, in particular; and computer science, in general.

His work was influential in distinguishing theoretical Computer Science from the disciplines of Mathematics and Electrical Engineering.

During his career, Ginsburg published over 100 papers and three books on various topics in theoretical Computer Science.

Seymour Ginsburg received his B.S. from City College of New York in 1948, where along with fellow student Martin Davis he attended an honors mathematics class taught by Emil Post.

Ginsburg's professional career began in 1951 when he accepted a position as assistant professor of mathematics at the University of Miami in Coral Gables, Florida.

He earned a Ph.D. in Mathematics from the University of Michigan in 1952, studying under Ben Dushnik.

He turned his attention wholly towards computer science in 1955 when he moved to California to work for the Northrop Corporation.

He followed this with positions at the National Cash Register Corporation, Hughes Aircraft, and System Development Corporation.

At SDC, Ginsburg first concentrated on the theory of abstract machines.

He subsequently formed and led a research project dedicated to formal language theory and the foundations of Computer Science.

Members of the research group included: Sheila Greibach, Michael A. Harrison, Gene Rose, Ed Spanier, and Joe Ullian.

The work that came out of this group distinguished Computer Science theory from other fields, putting Ginsburg at the center of what became the theoretical Computer Science community.

It was during the SDC years that a young Jeff Ullman spent one summer working for Ginsburg, learning both formal language theory and a broad approach to research in computer science theory.

Al Aho credited Ullman's summer with Ginsburg as being highly influential on Aho's career in Computer Science.

In an interview, Aho recalled that there was little Computer Science at Princeton University while he was studying for his PhD.

However, after Ullman returned from his summer with Ginsburg, Aho stated that Ullman "essentially taught Hopcroft, and me, formal language theory".

In 1958, he proved that "don't-care" circuit minimization does not necessarily yield a minimal result.

His work in automata theory led the switching theory community into a more theoretical direction.

Ginsburg turned his attention to formal language theory in the 1960s.

This work culminated in the publication of a book on the mathematics of machines in 1962.

Ginsburg joined the faculty of University of Southern California in 1966 where he helped to establish the Computer Science department in 1968.

He studied context-free grammars and published a well-known comprehensive overview of context-free languages in 1966.

Ginsburg was the first to observe the connection between context-free languages and "ALGOL-like" languages.

This brought the field of formal language theory to bear on programming language research.

He continued his work on formal language theory and automata through the 1970s.

He was awarded a Guggenheim Fellowship in 1974 and spent the year touring the world, lecturing on the areas of theoretical Computer Science which he had helped to create.

Ginsburg was named the first Fletcher Jones Professor of Computer Science at USC in 1978, a chair he held until his retirement in 1999.

At USC in the 1980s, Ginsburg created a research group dedicated to database theory.

He organized the first PODS (Symposium on Principles of Database Systems) in Marina del Rey in 1982 and was a moving force at the conference into the 1990s.

He was honored with a surprise session at the 1992 PODS on the occasion of his 64th birthday.

A festschrift edited by Jeff Ullman was created in his honor for the occasion.

Ginsburg's career ended suddenly in 1999 when he was diagnosed with the onset of Alzheimer's disease.

He retired from active teaching and became Professor Emeritus of Computer Science at USC.

He spent his last years in declining health until dying on December 5, 2004.

Ginsburg was remembered fondly in a memorial published in the ACM SIGMOD Record in 2005.

Beyond his contributions to Computer Science theory, he was remembered for the clarity of focus he brought to research and the seriousness with which he took his role as an advisor to PhD students.

He was also remembered for his generous support of younger researchers.

Those who benefitted from Ginsburg's mentorship, who were not also his PhD students, included: Jonathan Goldstine, Sheila Greibach, Michael A. Harrison, Richard Hull, and Jeff Ullman.

Ginsburg's early work concentrated on automata theory.