Complexity of Type Inference

• Autorzy: Tyszkiewicz, J.
• Języki publikacji: EN

Abstrakty

EN

This paper contains the English version of my Master's thesis [6] written about 22 years ago under supervision of Jerzy Tiuryn. Its main result is the proof of PTIME-completeness of the type reconstruction problem for simply typed lambda calculus. About the time I had the English paper ready, a much simpler proof [3] by John Mitchell (later published in [4]) was announced. Therefore my thesis remained an unpublished manuscript, but has been referenced to in a number of other papers. The TEX sources went lost in the meantime, so the present paper has been re-typed from scratch, but is almost identical to the original one written many years ago.

Słowa kluczowe

EN

typed lambda calculus; simple types; typability; complexity; PTIME

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 103, nr 1-4
• Strony: 289-301
• Opis fizyczny: Bibliogr. 6 poz.

Twórcy

autor

Tyszkiewicz, J.

• Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland,

Bibliografia

• [1] Dwork, C., Kanellakis, P. C., Mitchell, J. C.: On the Sequential Nature of Unification, Journal of Logic Programming, 1(1), 1984, 35-50.
• [2] Gambin, A., Lasota, S., Szklarczyk, R., Tiuryn, J., Tyszkiewicz, J.: Contextual Alignment of Biological Sequences, Bioinformatics, 18, 2002, 116-127.
• [3] Mitchell, J. C.: Curry Typing P-complete, types list http://permalink.gmane.org/gmane.comp.science.types/472, 1991.
• [4] Mitchell, J. C.: Foundations of Programming Languages, MIT Press, Cambridge, MA, USA, 1996.
• [5] Moczurad,M., Tyszkiewicz, J., Zaionc,M.: Statistical Properties of Simple Types, Mathematical Structures in Computer Science, 10(5), 2000, 575-594.
• [6] Tyszkiewicz, J.: Złożoność obliczeniowa zagadnienia typów w rachunku lambda [Complexity of type inference in finitely typed lambda calculus], in Polish, Master's thesis, University of Warsaw, 1988.