2009/05/26 by Daniel de Carvalho, de Carvalho, Daniel
Computer Science · #Computational Complexity (cs.CC) #F.3.2 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #cs.CC #cs.LO
paper · pdf · doi:10.48550/arxiv.0905.4251
36 pages
arxiv created 2009/05/26 · arxiv updated 2009/12/01
The multiset based relational model of linear logic induces a semantics of the type free lambda-calculus, which corresponds to a non-idempotent intersection type system, System R. We prove that, in System R, the size of the type derivations and the size of the types are closely related to the execution time of lambda-terms in a particular environment machine, Krivine's machine.