Abstract | ||
---|---|---|
The prove that the problem of type reconstruction in the polymorphic λ-calculus of rank 2 is polynomial-time equivalent to the problem of type reconstruction in ML, and is therefore DEXPTIME-complete. We also prove that for every k > 2, the problem of type reconstruction in the polymorphic λ-calculus of rank k, extended with suitably chosen constants with types of rank 1, is undecidable. |
Year | DOI | Venue |
---|---|---|
1992 | 10.1016/0890-5401(92)90020-G | Inf. Comput. |
Keywords | DocType | Volume |
type reconstruction,finite rank fragment,second order,lambda calculus | Journal | 98 |
Issue | ISSN | Citations |
2 | 0890-5401 | 18 |
PageRank | References | Authors |
1.56 | 19 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
A. J. Kfoury | 1 | 461 | 47.34 |
Jerzy Tiuryn | 2 | 229 | 22.79 |