World Library  
Flag as Inappropriate
Email this Article

Dana Scott

Article Id: WHEBN0000161875
Reproduction Date:

Title: Dana Scott  
Author: World Heritage Encyclopedia
Language: English
Subject: List of Turing Award laureates by university affiliation, Let expression, Denotational semantics, Alonzo Church, Michael O. Rabin
Collection: 1932 Births, 20Th-Century Mathematicians, American Computer Scientists, American Logicians, American Mathematicians, American Philosophers, Carnegie Mellon University Faculty, Fellows of Merton College, Oxford, Fellows of the American Mathematical Society, Fellows of the Association for Computing MacHinery, Formal Methods People, Guggenheim Fellows, Lattice Theorists, Living People, Mathematical Logicians, Members of the United States National Academy of Sciences, Modal Logicians, Model Theorists, Princeton University Alumni, Programming Language Researchers, Rolf Schock Prize Laureates, Semanticists, Set Theorists, Tarski Lecturers, Topologists, Turing Award Laureates, University of California, Berkeley Alumni, University of California, Berkeley Faculty, University of Chicago Faculty
Publisher: World Heritage Encyclopedia

Dana Scott

Dana Stewart Scott
Born (1932-10-11) October 11, 1932
Berkeley, California
Fields Computer Science
Institutions University of California, Berkeley
Oxford University
Carnegie Mellon University
Alma mater B.A. (mathematics) 1954, University of California, Berkeley
Ph.D. 1958, Princeton University
Thesis Convergent Sequences of Complete Theories (1958)
Doctoral advisor Alonzo Church
Doctoral students Jack Copeland
Michael Fourman
Kenneth Kunen
Angus Macintyre
Ketan Mulmuley
Marko Petkovšek
Fred S. Roberts
David Turner[1]
Known for automata theory, semantics of programming languages
Notable awards Leroy P. Steele Prize (1972)
ACM Turing Award (1976)
Tarski Lectures (1989)
Harold Pender Award (1990)
Rolf Schock Prizes in Logic and Philosophy (1997)

Dana Stewart Scott (born October 11, 1932) is the emeritus Hillman University Professor of Computer Science, Philosophy, and Mathematical Logic at Carnegie Mellon University; he is now retired and lives in Berkeley, California. His research career involved computer science, mathematics, and philosophy. His work on automata theory earned him the ACM Turing Award in 1976, while his collaborative work with Christopher Strachey in the 1970s laid the foundations of modern approaches to the semantics of programming languages. He has worked also on modal logic, topology, and category theory.


  • Early career 1
  • University of California, Berkeley, 1960–1963 2
    • Modal and tense logic 2.1
  • Stanford, Amsterdam and Princeton, 1963–1972 3
  • Oxford University, 1972–1981 4
    • Semantics of programming languages 4.1
  • Carnegie Mellon University 1981–2003 5
  • See also 6
  • Bibliography 7
    • Works by Scott 7.1
    • Other works 7.2
  • References 8
  • External links 9

Early career

He received his BA in Mathematics from the University of California, Berkeley, in 1954. He wrote his Ph.D. thesis on Convergent Sequences of Complete Theories under the supervision of Alonzo Church while at Princeton, and defended his thesis in 1958. Solomon Feferman (2005) writes of this period:

Scott began his studies in logic at Berkeley in the early 50s while still an undergraduate. His unusual abilities were soon recognized and he quickly moved on to graduate classes and seminars with Tarski and became part of the group that surrounded him, including me and Richard Montague; so it was at that time that we became friends. Scott was clearly in line to do a Ph. D. with Tarski, but they had a falling out for reasons explained in our biography.[2] Upset by that, Scott left for Princeton where he finished with a Ph. D. under Alonzo Church. But it was not long before the relationship between them was mended to the point that Tarski could say to him, "I hope I can call you my student."

After completing his Ph.D. studies, he moved to the University of Chicago, working as an instructor there until 1960. In 1959, he published a joint paper with Michael O. Rabin, a colleague from Princeton, entitled Finite Automata and Their Decision Problem,[3] which introduced the idea of nondeterministic machines to automata theory. This work led to the joint bestowal of the Turing Award on the two, for the introduction of this fundamental concept of computational complexity theory.

University of California, Berkeley, 1960–1963

Scott took up a post as Assistant Professor of Mathematics, back at the University of California, Berkeley, and involved himself with classical issues in mathematical logic, especially set theory and Tarskian model theory.

During this period he started supervising Ph.D. students, such as James Halpern (Contributions to the Study of the Independence of the Axiom of Choice) and Edgar Lopez-Escobar (Infinitely Long Formulas with Countable Quantifier Degrees).

Modal and tense logic

Scott also began working on modal logic in this period, beginning a collaboration with John Lemmon, who moved to Claremont, California, in 1963. Scott was especially interested in Arthur Prior's approach to tense logic and the connection to the treatment of time in natural-language semantics, and began collaborating with Richard Montague (Copeland 2004), whom he had known from his days as an undergraduate at Berkeley. Later, Scott and Montague independently discovered an important generalisation of Kripke semantics for modal and tense logic, called Scott-Montague semantics (Scott 1970).

John Lemmon and Scott began work on a modal-logic textbook that was interrupted by Lemmon's death in 1966. Scott circulated the incomplete monograph amongst colleagues, introducing a number of important techniques in the semantics of model theory, most importantly presenting a refinement of canonical model that became standard, and introducing the technique of constructing models through filtrations, both of which are core concepts in modern Kripke semantics (Blackburn, de Rijke, and Venema, 2001). Scott eventually published the work as An Introduction to Modal Logic (Lemmon & Scott, 1977).

Stanford, Amsterdam and Princeton, 1963–1972

Following an initial observation of Robert Solovay, Scott formulated the concept of Boolean-valued model, as Solovay and Petr Vopěnka did likewise at around the same time. In 1967 Scott published a paper, A Proof of the Independence of the Continuum Hypothesis, in which he used Boolean-valued models to provide an alternate analysis of the independence of the continuum hypothesis to that provided by Paul Cohen. This work led to the award of the Leroy P. Steele Prize in 1972.

Oxford University, 1972–1981

Scott took up a post as Professor of Mathematical Logic on the Philosophy faculty of Oxford University in 1972. He was member of Merton College while at Oxford.

Semantics of programming languages

This period saw Scott working with Christopher Strachey, and the two managed, despite administrative pressures, to do work on providing a mathematical foundation for the semantics of programming languages, the work for which Scott is best known. Together, their work constitutes the Scott-Strachey approach to denotational semantics; it constitutes one of the pieces of work in theoretical computer science and can perhaps be regarded as founding one of the schools of computer science. One of Scott's contributions is his formulation of domain theory, allowing programs involving recursive functions and looping-control constructs to be given denotational semantics. Additionally, he provided a foundation for the understanding of infinitary and continuous information through domain theory and his theory of information systems.

Scott's work of this period led to the bestowal of:

  • The 1990 Harold Pender Award for his application of concepts from logic and algebra to the development of mathematical semantics of programming languages;
  • The 1997 Rolf Schock Prize in logic and philosophy from the Royal Swedish Academy of Sciences for his conceptually oriented logical works, especially the creation of domain theory, which has made it possible to extend Tarski's semantical paradigm to programming languages as well as to construct models of Curry's combinatory logic and Church's calculus of lambda conversion; and
  • The 2001 Bolzano Prize for Merit in the Mathematical Sciences by the Czech Academy of Sciences.
  • The 2007 EATCS Award for his contribution to theoretical computer science.

Carnegie Mellon University 1981–2003

At Carnegie Mellon University, Scott proposed the theory of equilogical spaces as a successor theory to domain theory; among its many advantages, the category of equilogical spaces is a cartesian closed category, whereas the category of domains[4] is not. In 1994, he was inducted as a Fellow of the Association for Computing Machinery. In 2012 he became a fellow of the American Mathematical Society.[5]

See also


Works by Scott

  • With Michael O. Rabin, 1959. Finite Automata and Their Decision Problem.
  • 1967. A proof of the independence of the continuum hypothesis. Mathematical Systems Theory 1:89–111.
  • 1970. 'Advice in modal logic'. In Philosophical Problems in Logic, ed. K. Lambert, pages 143–173.
  • With John Lemmon, 1977. An Introduction to Modal Logic. Oxford: Blackwell.
  • Gierz, G.; Hofmann, K. H.; Keimel, K.; Lawson, J. D.; Mislove, M. W.; Scott, D. S. (2003). Continuous Lattices and Domains. Encyclopedia of Mathematics and its Applications 93. Cambridge University Press.  

Other works


  1. ^ "Dana Stewart Scott".  
  2. ^ Feferman & Feferman 2004.
  3. ^ Scott, Dana;  
  4. ^ Where here Dana Scott counts the category of domains to be the category whose objects are pointed DCPOs, and whose morphisms are the strict, Scott-continuous functions
  5. ^ List of Fellows of the American Mathematical Society, retrieved 2013-07-14.

External links

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.