complexity of ML typing

• To: types@theory.lcs.mit.edu
• Subject: complexity of ML typing
• From: jcm@ra.stanford.edu (John Mitchell)
• Date: Fri, 27 May 88 11:09:19 PDT

My 1988 POPL paper with Bob Harper makes a gross error
regarding the complexity of ML type inference. In summarizing
the "known" results about ML typing, we said that type inference
was linear time. We now know that it is not even polynomial. 
Sorry about the error.

John

• Prev: Re: Logical Relations
• Next: terminology
• Index(es):
  • Main
  • Thread