Stephen Warshall
Encyclopedia
Stephen Warshall was born in New York City
. During his career Warshall carried out research and development in operating systems, compiler design, language design
, and operations research
. Warshall died on December 11, 2006 of cancer
at his home in Gloucester, MA. He is survived by his wife, Sarah Dunlap, and two children, Andrew D. Warshall and Sophia V. Z. Warshall.
. He graduated from A.B. Davis High School in Mount Vernon, New York
and attended Harvard University
, receiving a bachelor's degree
in mathematics
in 1956. He never received an advanced degree since at that time no programs were available in his areas of interest. However, he took graduate courses at several different universities and contributed to the development of computer science
and software engineering
. In the 1971-1972 academic year he lectured on software engineering
at French
universities.
to do research and development for the United States Army
. In 1958 he left ORO to take a position at a company called Technical Operations, where he helped build a research and development laboratory for military software projects. In 1961 he left Technical Operations to found Massachusetts Computer Associates. Later, this company became part of Applied Data Research (ADR). After the merger, Warshall sat on the board of directors of ADR and managed a variety of projects and organizations. He retired from ADR in 1982 and taught a weekly class in Biblical Hebrew at Temple Ahavat Achim in Gloucester, MA.
that the transitive closure
algorithm
, now known as Warshall's algorithm
, is correct. He and a colleague at Technical Operations bet a bottle of rum
on who first could determine whether this algorithm
always works. Warshall came up with his proof
overnight, winning the bet and the rum
, which he shared with the loser of the bet. Because Warshall did not like sitting at a desk, he did much of his creative work in unconventional places such as on a sailboat
in the Indian Ocean
or in a Greek
lemon
orchard
.
New York City
New York is the most populous city in the United States and the center of the New York Metropolitan Area, one of the most populous metropolitan areas in the world. New York exerts a significant impact upon global commerce, finance, media, art, fashion, research, technology, education, and...
. During his career Warshall carried out research and development in operating systems, compiler design, language design
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....
, and operations research
Operations research
Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...
. Warshall died on December 11, 2006 of cancer
Cancer
Cancer , known medically as a malignant neoplasm, is a large group of different diseases, all involving unregulated cell growth. In cancer, cells divide and grow uncontrollably, forming malignant tumors, and invade nearby parts of the body. The cancer may also spread to more distant parts of the...
at his home in Gloucester, MA. He is survived by his wife, Sarah Dunlap, and two children, Andrew D. Warshall and Sophia V. Z. Warshall.
Education
Warshall went to public school in BrooklynBrooklyn
Brooklyn is the most populous of New York City's five boroughs, with nearly 2.6 million residents, and the second-largest in area. Since 1896, Brooklyn has had the same boundaries as Kings County, which is now the most populous county in New York State and the second-most densely populated...
. He graduated from A.B. Davis High School in Mount Vernon, New York
Mount Vernon, New York
Mount Vernon is a city in Westchester County, New York, United States. It lies on the border of the New York City borough of The Bronx.-Overview:...
and attended Harvard University
Harvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
, receiving a bachelor's degree
Bachelor's degree
A bachelor's degree is usually an academic degree awarded for an undergraduate course or major that generally lasts for three or four years, but can range anywhere from two to six years depending on the region of the world...
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...
in 1956. He never received an advanced degree since at that time no programs were available in his areas of interest. However, he took graduate courses at several different universities and contributed to the development 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...
and software engineering
Software engineering
Software Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...
. In the 1971-1972 academic year he lectured on software engineering
Software engineering
Software Engineering is the application of a systematic, disciplined, quantifiable approach to the development, operation, and maintenance of software, and the study of these approaches; that is, the application of engineering to software...
at French
France
The French Republic , The French Republic , The French Republic , (commonly known as France , is a unitary semi-presidential republic in Western Europe with several overseas territories and islands located on other continents and in the Indian, Pacific, and Atlantic oceans. Metropolitan France...
universities.
Employment
After graduating from Harvard, Warshall worked at ORO (Operation Research Office), a program set up by Johns HopkinsJohns Hopkins University
The Johns Hopkins University, commonly referred to as Johns Hopkins, JHU, or simply Hopkins, is a private research university based in Baltimore, Maryland, United States...
to do research and development for the United States Army
United States Army
The United States Army is the main branch of the United States Armed Forces responsible for land-based military operations. It is the largest and oldest established branch of the U.S. military, and is one of seven U.S. uniformed services...
. In 1958 he left ORO to take a position at a company called Technical Operations, where he helped build a research and development laboratory for military software projects. In 1961 he left Technical Operations to found Massachusetts Computer Associates. Later, this company became part of Applied Data Research (ADR). After the merger, Warshall sat on the board of directors of ADR and managed a variety of projects and organizations. He retired from ADR in 1982 and taught a weekly class in Biblical Hebrew at Temple Ahavat Achim in Gloucester, MA.
Warshall's algorithm
There is an interesting anecdote about his proofMathematical proof
In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive or empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single...
that the transitive closure
Transitive closure
In mathematics, the transitive closure of a binary relation R on a set X is the transitive relation R+ on set X such that R+ contains R and R+ is minimal . If the binary relation itself is transitive, then the transitive closure will be that same binary relation; otherwise, the transitive closure...
algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
, now known as Warshall's algorithm
Floyd-Warshall algorithm
In computer science, the Floyd–Warshall algorithm is a graph analysis algorithm for finding shortest paths in a weighted graph and also for finding transitive closure of a relation R...
, is correct. He and a colleague at Technical Operations bet a bottle of rum
Rum
Rum is a distilled alcoholic beverage made from sugarcane by-products such as molasses, or directly from sugarcane juice, by a process of fermentation and distillation. The distillate, a clear liquid, is then usually aged in oak barrels...
on who first could determine whether this algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
always works. Warshall came up with his proof
Mathematical proof
In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive or empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single...
overnight, winning the bet and the rum
Rum
Rum is a distilled alcoholic beverage made from sugarcane by-products such as molasses, or directly from sugarcane juice, by a process of fermentation and distillation. The distillate, a clear liquid, is then usually aged in oak barrels...
, which he shared with the loser of the bet. Because Warshall did not like sitting at a desk, he did much of his creative work in unconventional places such as on a sailboat
Sailboat
A sailboat or sailing boat is a boat propelled partly or entirely by sails. The term covers a variety of boats, larger than small vessels such as sailboards and smaller than sailing ships, but distinctions in the size are not strictly defined and what constitutes a sailing ship, sailboat, or a...
in the Indian Ocean
Indian Ocean
The Indian Ocean is the third largest of the world's oceanic divisions, covering approximately 20% of the water on the Earth's surface. It is bounded on the north by the Indian Subcontinent and Arabian Peninsula ; on the west by eastern Africa; on the east by Indochina, the Sunda Islands, and...
or in a Greek
Greece
Greece , officially the Hellenic Republic , and historically Hellas or the Republic of Greece in English, is a country in southeastern Europe....
lemon
Lemon
The lemon is both a small evergreen tree native to Asia, and the tree's ellipsoidal yellow fruit. The fruit is used for culinary and non-culinary purposes throughout the world – primarily for its juice, though the pulp and rind are also used, mainly in cooking and baking...
orchard
Orchard
An orchard is an intentional planting of trees or shrubs that is maintained for food production. Orchards comprise fruit or nut-producing trees which are grown for commercial production. Orchards are also sometimes a feature of large gardens, where they serve an aesthetic as well as a productive...
.
Further reading
- Stephen Warshall. A theorem on Boolean matrices. Journal of the ACM, 9(1):11-12, January 1962.
- Thomas E. Cheatham, Jr., Stephen Warshall: Translation of retrieval requests couched in a "semiformal" English-like language. Commun. ACM 5(1): 34-39 (1962)
See also
- Warshall's algorithmFloyd-Warshall algorithmIn computer science, the Floyd–Warshall algorithm is a graph analysis algorithm for finding shortest paths in a weighted graph and also for finding transitive closure of a relation R...