%0 Journal Article 
%F henglein99a
%A Henglein, Fritz
%T Breaking Through the $n^3$ Barrier: Faster Object Type Inference
%J Theory and Practice of Object Systems (TAPOS)
%V 5
%N 1
%P 57-72
%X Abadi and Cardelli present a series of type systems for their object calculi, four of which are first-order. Palsberg has shown how typability in each one of these systems can be decided in time $O(n^3)$ and space $O(n^2)$, where $n$ is the size of an untyped object expression, using an algorithm based on dynamic transitive closure. In this paper we improve each one of the four type inference problems from $O(n^3)$ to the following time complexities: \begin{enumerate} \item no subtyping/no recursive types: $O(n)$; \item no subtyping/with recursive types: $O(n \log^2 n)$; \item with subtyping/no recursive types: $O(n^2)$; \item with subtyping/with recursive types: $O(n^2)$. \end{enumerate} Furthermore, our algorithms improve the space complexity from $O(n^2)$ to $O(n)$ in each case. The key ingredient that lets us ``beat'' the worst-case time and space complexity induced by general dynamic transitive closure or similar algorithmic methods is that object subtyping, in contrast to record subtyping, is \emph{invariant}: an object type is a subtype of a ``shorter'' type with a subset of the method names if and only if the common components have \emph{equal} types
%U http://www.informatik.uni-trier.de/ ley/db/journals/tapos/tapos5.html
%D 1999
%K parametricity
%K  dyntyp