Seymour Ginsburg (December 12, 1927 – December 5, 2004) was an American pioneer of
automata
An automaton (; plural: automata or automatons) is a relatively self-operating machine, or control mechanism designed to automatically follow a sequence of operations, or respond to predetermined instructions.Automaton – Definition and More ...
theory,
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of symb ...
theory, and
database
In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases sp ...
theory, in particular; and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, 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
The City College of the City University of New York (also known as the City College of New York, or simply City College or CCNY) is a public university within the City University of New York (CUNY) system in New York City. Founded in 1847, Cit ...
in 1948, where along with fellow student
Martin Davis he attended an honors mathematics class taught by
Emil Post
Emil Leon Post (; February 11, 1897 – April 21, 1954) was an American mathematician and logician. He is best known for his work in the field that eventually became known as computability theory.
Life
Post was born in Augustów, Suwałki Gove ...
. He earned a Ph.D. in
Mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
from the
University of Michigan
, mottoeng = "Arts, Knowledge, Truth"
, former_names = Catholepistemiad, or University of Michigania (1817–1821)
, budget = $10.3 billion (2021)
, endowment = $17 billion (2021)As o ...
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
The University of Miami (UM, UMiami, Miami, U of M, and The U) is a private research university in Coral Gables, Florida. , the university enrolled 19,096 students in 12 colleges and schools across nearly 350 academic majors and programs, incl ...
in
Coral Gables, Florida
Coral Gables, officially City of Coral Gables, is a city in Miami-Dade County, Florida. The city is located southwest of Downtown Miami. As of the 2020 U.S. census, it had a population of 49,248.
Coral Gables is known globally as home to the ...
. He turned his attention wholly towards
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
in 1955 when he moved to California to work for the
Northrop Corporation
Northrop Corporation was an American aircraft manufacturer from its formation in 1939 until its 1994 merger with Grumman to form Northrop Grumman. The company is known for its development of the flying wing design, most successfully the B-2 Spiri ...
. He followed this with positions at the
National Cash Register Corporation
NCR Voyix Corporation, previously known as NCR Corporation and National Cash Register, is an American software, consulting and technology company providing several professional services and electronic products. It manufactured self-service ki ...
,
Hughes Aircraft
The Hughes Aircraft Company was a major American aerospace and defense contractor founded on February 14, 1934 by Howard Hughes
Howard Robard Hughes Jr. (December 24, 1905 – April 5, 1976) was an American business magnate, record-setting p ...
, and
System Development Corporation
System Development Corporation (SDC) was a computer software company based in Santa Monica, California. Founded in 1955, it is considered the first company of its kind.
History
SDC began as the systems engineering group for the SAGE air-defense ...
.
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 Adele Greibach (born 6 October 1939 in New York City) is a researcher in formal languages in computing, automata, compiler theory and computer science. She is an Emeritus Professor of Computer Science at the University of California, Los ...
,
Michael A. Harrison
Michael A. Harrison is a computer scientist, in particular a pioneer in the area of formal languages.
Biography
Michael A. Harrison (born in Philadelphia, Pennsylvania, U.S.) studied electrical engineering and computing for BS and MS at the Case ...
, Gene Rose,
Ed Spanier
Ed, ed or ED may refer to:
Arts and entertainment
* ''Ed'' (film), a 1996 film starring Matt LeBlanc
* Ed (''Fullmetal Alchemist'') or Edward Elric, a character in ''Fullmetal Alchemist'' media
* ''Ed'' (TV series), a TV series that ran fro ...
, and
Joe Ullian
Joe or JOE may refer to:
Arts
Film and television
* ''Joe'' (1970 film), starring Peter Boyle
* ''Joe'' (2013 film), starring Nicolas Cage
* ''Joe'' (TV series), a British TV series airing from 1966 to 1971
* ''Joe'', a 2002 Canadian animated ...
. 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
Jeffrey David Ullman (born November 22, 1942) is an American computer scientist and the Stanford W. Ascherman Professor of Engineering, Emeritus, at Stanford University. His textbooks on compilers (various editions are popularly known as the Pri ...
spent one summer working for Ginsburg, learning both formal language theory and a broad approach to research in computer science theory.
Al Aho
Alfred Vaino Aho (born August 9, 1941) is a Canadian computer scientist best known for his work on programming languages, compilers, and related algorithms, and his textbooks on the art and science of computer programming.
Aho was elected into ...
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
Princeton University is a private university, private research university in Princeton, New Jersey. Founded in 1746 in Elizabeth, New Jersey, Elizabeth as the College of New Jersey, Princeton is the List of Colonial Colleges, fourth-oldest ins ...
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
The University of Southern California (USC, SC, or Southern Cal) is a Private university, private research university in Los Angeles, California, United States. Founded in 1880 by Robert M. Widney, it is the oldest private research university in C ...
in 1966 where he helped to establish the
Computer Science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
department in 1968. He was awarded a
Guggenheim Fellowship
Guggenheim Fellowships are grants that have been awarded annually since by the John Simon Guggenheim Memorial Foundation to those "who have demonstrated exceptional capacity for productive scholarship or exceptional creative ability in the ar ...
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
In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases sp ...
theory. He organized the first PODS (
Symposium on Principles of Database Systems
The ACM Symposium on Principles of Database Systems (PODS) is an international research conference on database theory, and has been held yearly since 1982. It is sponsored by three Association for Computing Machinery
The Association for Comp ...
) in
Marina del Rey
Marina del Rey (Spanish language, Spanish for "Marina of the King") is an unincorporated area, unincorporated seaside community in Los Angeles County, California, with an eponymous harbor that is a major boating and water recreation destination ...
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
Jeffrey David Ullman (born November 22, 1942) is an American computer scientist and the Stanford W. Ascherman Professor of Engineering, Emeritus, at Stanford University. His textbooks on compilers (various editions are popularly known as the Pri ...
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 (AD) is a neurodegeneration, neurodegenerative disease that usually starts slowly and progressively worsens. It is the cause of 60–70% of cases of dementia. The most common early symptom is difficulty in short-term me ...
. 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
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.
The annual ACM SIGMOD Conference, which began in 1975, is considered one of ...
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 Adele Greibach (born 6 October 1939 in New York City) is a researcher in formal languages in computing, automata, compiler theory and computer science. She is an Emeritus Professor of Computer Science at the University of California, Los ...
, Michael A. Harrison
Michael A. Harrison is a computer scientist, in particular a pioneer in the area of formal languages.
Biography
Michael A. Harrison (born in Philadelphia, Pennsylvania, U.S.) studied electrical engineering and computing for BS and MS at the Case ...
, Richard Hull
Field Marshal Sir Richard Amyatt Hull, (7 May 1907 – 17 September 1989) was a senior British Army officer. He was the last Chief of the Imperial General Staff (CIGS), holding the post from 1961 to 1964, and the first Chief of the General Sta ...
, and Jeff Ullman
Jeffrey David Ullman (born November 22, 1942) is an American computer scientist and the Stanford W. Ascherman Professor of Engineering, Emeritus, at Stanford University. His textbooks on compilers (various editions are popularly known as the Pri ...
.
Professional contributions
Ginsburg's early work concentrated on automata theory
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματο ...
. 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 logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of symb ...
in the 1960s. He studied context-free grammar
In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules are of the form
:A\ \to\ \alpha
with A a ''single'' nonterminal symbol, and \alpha a string of terminals and/or nonterminals (\alpha can be empt ...
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
In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG).
Context-free languages have many applications in programming languages, in particular, most arithmetic expressions are generated by ...
s and "ALGOL
ALGOL (; short for "Algorithmic Language") is a family of imperative computer programming languages originally developed in 1958. ALGOL heavily influenced many other languages and was the standard method for algorithm description used by the ...
-like" languages. This brought the field of formal language theory
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of symb ...
to bear on programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
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 Adele Greibach (born 6 October 1939 in New York City) is a researcher in formal languages in computing, automata, compiler theory and computer science. She is an Emeritus Professor of Computer Science at the University of California, Los ...
, and Michael A. Harrison
Michael A. Harrison is a computer scientist, in particular a pioneer in the area of formal languages.
Biography
Michael A. Harrison (born in Philadelphia, Pennsylvania, U.S.) studied electrical engineering and computing for BS and MS at the Case ...
.
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 is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, Abstract Families of Languages, in collaboration with Sheila Greibach
Sheila Adele Greibach (born 6 October 1939 in New York City) is a researcher in formal languages in computing, automata, compiler theory and computer science. She is an Emeritus Professor of Computer Science at the University of California, Los ...
in 1967.
In 1974, Ginsburg, along with Armin B. Cremers
Armin Bernd Cremers (born June 7, 1946) is a German mathematician and computer scientist. He is a professor in the computer science institute at the University of Bonn, Germany. He is most notable for his contributions to several fields of discre ...
, developed the theory of Grammar Forms.
In the 1980s, Ginsburg became an early pioneer in the field of Database
In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases sp ...
Theory. He continued to work in this field until his retirement. His professional contributions spanned subjects as diverse as Functional dependency
In relational database theory, a functional dependency is a constraint between two sets of attributes in a relation from a database. In other words, a functional dependency is a constraint between two attributes in a relation.
Given a relation ' ...
, object histories, spreadsheet histories, Datalog
Datalog is a declarative logic programming language. While it is syntactically a subset of Prolog, Datalog generally uses a bottom-up rather than top-down evaluation model. This difference yields significantly different behavior and properties ...
, and data restructuring.
See also
* List of pioneers in computer science
This is a list of people who made transformative breakthroughs in the creation, development and imagining of what computers could do.
Pioneers
: ''To arrange the list by date or person (ascending or descending), click that column's small "up-do ...
References
External links
*
*
{{DEFAULTSORT:Ginsburg, Seymour
1927 births
2004 deaths
American computer scientists
Theoretical computer scientists
City College of New York alumni
University of Miami faculty
University of Michigan alumni
University of Southern California faculty