[Alta-Logic] Talk on Tuesday Feb 24

[Gillman Payette]

Speaker: Brian Redmond

Room: ICT 616

Start: 02/24/2009 - 12:00
End: 02/24/2009 - 13:00

Abstract:

In this talk, I will present some recent work with Robin Cockett
and Mike Burrell on a type system for a functional style programming
 language called Pola which is complete with respect to polynomial time
 programming. This means, both that every well-typed Pola program is
 guaranteed to halt in time polynomial with respect to the size of its
 input, and that all such polynomial time functions can be written in Pola.
The system supports a wide range of inductive and (higher-order)
coinductive data types and a form of safe recursion is used to limit the
 power of programming with the inductive types. Examples will be given to
 illustrate both the programming style of Pola and how Pola's type system
 maintains polynomial complexity.


-- 
Gillman Payette
Department of Philosophy
University of Calgary
2500 University Drive NW
Calgary, AB T2N 1N4, Canada
Ph 403.220.6463
Fax 403.289.5698