The Algebraic Structure of Transitive Closure and its Application to Attributed Type Signatures

This paper identifies a misconception about the algebraic structure underlying the view of transitive closure as a matrix multiplication problem. This is the mathematical basis of the technique that has been used for the efficient compilation of partially ordered sets of objects or types in programming languages for the past ten years. It also shows that the correct structure, a closed semi-ring, can also be extended to objects or type signatures that are augmented with attributes, constraints on the multiple inheritance of those attributes, and/or constraints on what types of values the attributes can take. As a specific example in the realm of linguistic knowledge representation, it is shown that every operation necessary for computing the closure of attributed type signature specifications in the logic of typed feature structures (Carpenter, 1992), the logical underpinning of the linguistic theory, Head-driven Phrase Structure Grammar (Pollard and Sag, 1987; Pollard and Sag, 1984), can be reduced to matrix arithmetic using this construction. Other practical consequences of using the correct structure, such as the algorithmic complexity of multiplication and closure operations, are also discussed.