Seymour Ginsburg
Encyclopedia
Seymour Ginsburg was a 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.
he attended an honors mathematics class taught by Emil Post. He earned a Ph.D. in Mathematics
from the University of Michigan
in 1952, studying under Ben Dushnik.
Ginsburg's professional career began in 1951 when he accepted a position as Assistant Professor of Mathematics at the University of Miami
in Florida. 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
, Mike 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 while he was studying for his PhD. However, after Ullman returned from his summer with Ginsburg, he stated that Ullman "essentially taught Hopcroft
, and me, formal language theory".
Ginsburg joined the faculty of University of Southern California
in 1966 where he helped to establish the Computer Science
department in 1968. 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. He continued his work on formal language theory and automata through the 1970s.
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 Harrison
, Richard Hull, and Jeff Ullman.
. 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. This work culminated in the publication of a book on the mathematics of machines in 1962.
Ginsburg turned his attention to formal language theory in the 1960s. He studied context-free grammar
s and published a well-known comprehensive overview of context-free languages in 1966. Ginsburg was the first to observe the connection between context-free language
s and "ALGOL
-like" languages. This brought the field of formal language theory to bear on programming language
research. Ginsburg's results on context-free grammars and push-down acceptors are considered to be some of the deepest and most beautiful in the area. They remain standard tools for many computer scientists working in the areas of formal languages and automata. Many of his papers at this time were co-authored with other prominent formal language researchers, including Sheila Greibach
, and Michael A. Harrison.
The unification of different views of formal systems was a constant theme in Ginsburg's work. In formal language theory his papers examined the relationships between grammar-based systems, acceptor-based systems, and algebraic characterizations of families of languages. The culmination of this work was the creation of one of the deepest branches of Computer Science
, Abstract Families of Languages, in collaboration with Sheila Greibach
in 1967.
In 1974, Ginsburg, along with Armin Cremers, developed the theory of Grammar Forms.
In the 1980s, Ginsburg became an early pioneer in the field of Database
Theory. He continued to work in this field until his retirement. His professional contributions spanned subjects as diverse as Functional dependency
, object histories, spreadsheet histories, Datalog
, and data restructuring.
Automata
Automata is the plural form of automaton, a self-operating machine. It may also refer to:* "Automata", a short story by E. T. A. Hoffmann* "Automata", a hardboiled science fiction crime series by Penny Arcade...
theory, formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
theory, and
database
Database
A database is an organized collection of data for one or more purposes, usually in digital form. The data are typically organized to model relevant aspects of reality , in a way that supports processes requiring this information...
theory, in particular; and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, 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.
Biography
Seymour Ginsburg received his B.S. from City College of New York in 1948, where along with fellow student Martin DavisMartin Davis
Martin David Davis, is an American mathematician, known for his work on Hilbert's tenth problem . He received his Ph.D. from Princeton University in 1950, where his adviser was Alonzo Church . He is Professor Emeritus at New York University. He is the co-inventor of the Davis-Putnam and the DPLL...
he attended an honors mathematics class taught by Emil Post. He earned a Ph.D. in Mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
from the University of Michigan
UM
Um may refer to:* Um, an exclamation or filled pause in spoken conversation* Um * .um, the Top Level Domain for United States Minor Outlying Islands...
in 1952, studying under Ben Dushnik.
Ginsburg's professional career began in 1951 when he accepted a position as Assistant Professor of Mathematics at the University of Miami
University of Miami
The University of Miami is a private, non-sectarian university founded in 1925 with its main campus in Coral Gables, Florida, a medical campus in Miami city proper at Civic Center, and an oceanographic research facility on Virginia Key., the university currently enrolls 15,629 students in 12...
in Florida. He turned his attention wholly towards Computer Science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
in 1955, when he moved to California to work for the Northrop Corporation
Northrop Corporation
Northrop Corporation was a leading United States aircraft manufacturer from its formation in 1939 until its merger with Grumman to form Northrop Grumman in 1994. The company is known for its development of the flying wing design, although only a few of these have entered service.-History:Jack...
. He followed this with positions at the National Cash Register Corporation, Hughes Aircraft
Hughes Aircraft
Hughes Aircraft Company was a major American aerospace and defense contractor founded in 1932 by Howard Hughes in Culver City, California as a division of Hughes Tool Company...
, and System Development Corporation
System Development Corporation
System Development Corporation , based in Santa Monica, California, was considered the world's first computer software company.SDC started in 1955 as the systems engineering group for the SAGE air defense ground system at the RAND 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
Sheila Greibach
Sheila Adele Greibach is a researcher in formal languages, automata,compiler theory in particular; and computer science in general. She is currently Professor of Computer Science at the University of California, Los Angeles....
, Mike Harrison, Gene Rose
Gene Rose
Roy Eugene "Gene" Rose was an American football end in the National Football League for the New York Giants. He played college football at the University of Tennessee and was drafted in the fourth round of the 1936 NFL Draft....
, 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 while he was studying for his PhD. However, after Ullman returned from his summer with Ginsburg, he stated that Ullman "essentially taught Hopcroft
John Hopcroft
John Edward Hopcroft is an American theoretical computer scientist. His textbooks on theory of computation and data structures are regarded as standards in their fields. He is the IBM Professor of Engineering and Applied Mathematics in Computer Science at Cornell University.He received his...
, and me, formal language theory".
Ginsburg joined the faculty of University of Southern California
University of Southern California
The University of Southern California is a private, not-for-profit, nonsectarian, research university located in Los Angeles, California, United States. USC was founded in 1880, making it California's oldest private research university...
in 1966 where he helped to establish the Computer Science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
department in 1968. He was awarded a Guggenheim Fellowship
Guggenheim Fellowship
Guggenheim Fellowships are American grants that have been awarded annually since 1925 by the John Simon Guggenheim Memorial Foundation to those "who have demonstrated exceptional capacity for productive scholarship or exceptional creative ability in the arts." Each year, the foundation makes...
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. He continued his work on formal language theory and automata through the 1970s.
At USC in the 1980s, Ginsburg created a research group dedicated to Database
Database
A database is an organized collection of data for one or more purposes, usually in digital form. The data are typically organized to model relevant aspects of reality , in a way that supports processes requiring this information...
theory. He organized the first PODS (Symposium on Principles of Database Systems
Symposium on Principles of Database Systems
The ACM Symposium on Principles of Database Systems is the premier international research conference on database theory, and has been held yearly since 1982. It is sponsored by three Association for Computing Machinery SIGs, SIGART, SIGACT, and SIGMOD...
) 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
Alzheimer's disease
Alzheimer's disease also known in medical literature as Alzheimer disease is the most common form of dementia. There is no cure for the disease, which worsens as it progresses, and eventually leads to death...
. 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
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...
SIGMOD
SIGMOD
SIGMOD is the Association for Computing Machinery's Special Interest Group on Management of Data, which specializes in large-scale data management problems and databases....
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
Sheila Greibach
Sheila Adele Greibach is a researcher in formal languages, automata,compiler theory in particular; and computer science in general. She is currently Professor of Computer Science at the University of California, Los Angeles....
, Michael Harrison
Michael Harrison
Michael Harrison is an American composer, influenced by both Western classical and North Indian classical music.Harrison studied composition at the University of Oregon and the Juilliard School in the late 1970s, and began investigating alternative tunings while studying Indian classical music with...
, Richard Hull, and Jeff Ullman.
Professional Contributions
Ginsburg's early work concentrated on automata theoryAutomata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
. 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. This work culminated in the publication of a book on the mathematics of machines in 1962.
Ginsburg turned his attention to formal language theory in the 1960s. He studied context-free grammar
Context-free grammar
In formal language theory, a context-free grammar is a formal grammar in which every production rule is of the formwhere V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals ....
s and published a well-known comprehensive overview of context-free languages in 1966. Ginsburg was the first to observe the connection between context-free language
Context-free language
In formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.-Examples:...
s and "ALGOL
ALGOL
ALGOL is a family of imperative computer programming languages originally developed in the mid 1950s which greatly influenced many other languages and became the de facto way algorithms were described in textbooks and academic works for almost the next 30 years...
-like" languages. This brought the field of formal language theory to bear on programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
research. Ginsburg's results on context-free grammars and push-down acceptors are considered to be some of the deepest and most beautiful in the area. They remain standard tools for many computer scientists working in the areas of formal languages and automata. Many of his papers at this time were co-authored with other prominent formal language researchers, including Sheila Greibach
Sheila Greibach
Sheila Adele Greibach is a researcher in formal languages, automata,compiler theory in particular; and computer science in general. She is currently Professor of Computer Science at the University of California, Los Angeles....
, and Michael A. Harrison.
The unification of different views of formal systems was a constant theme in Ginsburg's work. In formal language theory his papers examined the relationships between grammar-based systems, acceptor-based systems, and algebraic characterizations of families of languages. The culmination of this work was the creation of one of the deepest branches of Computer Science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, Abstract Families of Languages, in collaboration with Sheila Greibach
Sheila Greibach
Sheila Adele Greibach is a researcher in formal languages, automata,compiler theory in particular; and computer science in general. She is currently Professor of Computer Science at the University of California, Los Angeles....
in 1967.
In 1974, Ginsburg, along with Armin Cremers, developed the theory of Grammar Forms.
In the 1980s, Ginsburg became an early pioneer in the field of Database
Database
A database is an organized collection of data for one or more purposes, usually in digital form. The data are typically organized to model relevant aspects of reality , in a way that supports processes requiring this information...
Theory. He continued to work in this field until his retirement. His professional contributions spanned subjects as diverse as Functional dependency
Functional dependency
A functional dependency is a constraint between two sets of attributes in a relation from a database.Given a relation R, a set of attributes X in R is said to functionally determine another attribute Y, also in R, if, and only if, each X value is associated with precisely one Y value...
, object histories, spreadsheet histories, Datalog
Datalog
Datalog is a query and rule language for deductive databases that syntactically is a subset of Prolog. Its origins date back to the beginning of logic programming, but it became prominent as a separate area around 1977 when Hervé Gallaire and Jack Minker organized a workshop on logic and databases...
, and data restructuring.