[Colloquium] Talk by James S. Royer from SUNY on 11/3/03

[Margery Ishmael]

------------------------------------------------------------------------ 
---

DEPARTMENT OF COMPUTER SCIENCE - TALK

Monday, November 3, 2003 at 2:30 p.m. in Ryerson 251

------------------------------------------------------------------------ 
----

Speaker: James S. Royer, Syracuse University, Syracuse, New York
http://www.cis.syr.edu/people/royer/royer.html

Title:  Sequentiality and Complexity
			
    In the late 1960s Dana Scott introduced the prototype
    programming language PCF in the course of his study of
    programming language semantics.  Scott noted that all of
    his semantic models of PCF included ``junk.'' That is,
    PCF is an intuitively sequential (one thing definitely
    following another) programming language, but all of
    Scott's models included nonsequential things.
    Constructing a ``no junk'' model for PCF was a major open
    problem for about twenty years.  One reason for its
    prominence was that capturing higher-type sequentiality
    in a semantics seemed important and proved tricky.  When
    solutions to the PCF problem finally appeared, it became
    apparent that PCF itself was too restrictive to embody
    ``higher-type sequentiality.''

    In the late 1990s van Oosten introduced a class of
    ``sequentially computable'' higher-type functionals that
    includes the PCF-computable functionals.  This class now
    goes under the name of the sequentially realizable
    functionals, or simply SR.  This class relates to the
    work of Curien and others on sequentiality and has very
    strong and natural mathematical properties.  SR can be
    explain via simple dialog games or, alternatively, as
    higher-type Turing reductions on functionals.

    More recently John Longley discovered an SR-functional,
    H, which when added to the language PCF, yields a language
    PCF+H that computes exactly SR. Longley hesitated to
    recommend PCF+H as the basis of a practical programming
    language because the only known ways of computing H
    seemed to involve high computational costs.  In this talk
    we confirm Longley's doubts.  We show that if P is
    different from NP, then the computational complexity of H
    is inherently infeasible.

Host: Stuart Kurtz

*Refreshments will follow the talk in Ryerson 255*

People in need of assistance should call 773-834-8977 in advance.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: text/enriched
Size: 2662 bytes
Desc: not available
Url : http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20031027/808e472a/attachment.bin