polski
Computer Science Foundations
Organizers:
Marek Zaionc
Usual time and place: Wednesday, 12:15-14:00, room 0086
site-www: tcs.uj.edu.pl/csfs?lang=0
event-date: 09.11.2011
Speaker: Marek Wróbel
Title of the talk: Complexity of Type Inference by Jerzy Tyszkiewicz
Abstract:
The type inference problem may be stated as follows: given a term of untyped lambda calculus, decide whether it may be typed to a term of a first-order-typed lambda calculus. If it is possible, then find all possible typings for it (or at least one possible typing). We show that the type inference problem is PTIME-complete.
The type inference problem may be stated as follows: given a term of untyped lambda calculus, decide whether it may be typed to a term of a first-order-typed lambda calculus. If it is possible, then find all possible typings for it (or at least one possible typing). We show that the type inference problem is PTIME-complete.