zbMATH — the first resource for mathematics

Efficient type matching. (English) Zbl 1077.68608
Nielsen, Mogens (ed.) et al., Foundations of software science and computation structures. 5th international conference, FOSSACS 2002, held as part of the joint European conferences on theory and practice of software, ETAPS 2002, Grenoble, France, April 8–12, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43366-X). Lect. Notes Comput. Sci. 2303, 187-204 (2002).
Summary: Palsberg and Zhao presented an \(O(n^{2})\) time algorithm for matching two recursive types. In this paper, we present an \(O(n \log n)\) algorithm for the same problem. Our algorithm works by reducing the type matching problem to the well-understood problem of finding a size-stable partition of a graph. Our result may help improve systems, such as Polyspin and Mockingbird, that are designed to facilitate interoperability of software components. We also discuss possible applications of our algorithm to Java. Issues related to subtyping of recursive types are also discussed.
For the entire collection see [Zbl 0989.00051].

68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
68R10 Graph theory (including graph drawing) in computer science
Full Text: Link