@article{Palsberg_1995, title={Efficient Inference of Object Types}, volume={2}, url={https://tidsskrift.dk/brics/article/view/19935}, DOI={10.7146/brics.v2i32.19935}, abstractNote={Abadi and Cardelli have recently investigated a calculus of objects<br />[2]. The calculus supports a key feature of object-oriented languages:<br />an object can be emulated by another object that has more refined<br />methods. Abadi and Cardelli presented four first-order type systems<br />for the calculus. The simplest one is based on finite types and no<br />subtyping, and the most powerful one has both recursive types and<br />subtyping. Open until now is the question of type inference, and<br />in the presence of subtyping the absence of minimum typings poses<br />practical problems for type inference [2].<br />In this paper we give an O(n^3) algorithm for each of the four type<br />inference problems and we prove that all the problems are P-complete.<br />We also indicate how to modify the algorithms to handle functions and<br />records.}, number={32}, journal={BRICS Report Series}, author={Palsberg, Jens}, year={1995}, month={Jun.} }