Title

A Generalization of the Trie Data Structure

Author(s)/Creator(s)

Richard H. Connelly
F. Lockwood Morris, Syracuse UniversityFollow

Document Type

Report

Date

2-1993

Keywords

Structure

Language

English

Disciplines

Computer Sciences

Description/Abstract

Tries, a form of string-indexed look-up structure, are generalized to permit indexing by terms built according to an arbitrary signature. The construction is parametric with respect to the type of data to be stored as values; this is essential, because the recursion which defines tries appeals from one value type to others. "Trie" (for any fixed signature) is then a functor, and the corresponding look-up function is a natural isomorphism. The trie functor is in principle definable by the "initial fixed point" semantics of Smyth and Plotkin. We simplify the construction, however, by introducing the "category-cpo", a class of category within which calculations can retain some domain-theoretic flavor. Our construction of tries extends easily to many-sorted signatures.

Additional Information

School of Computer and Information Science, Syracuse University, SU-CIS,93-23

Authors later published: Connelly, R. H., & Morris, F. L. (1995). A generalization of the trie data structure. Mathematical Structures in Computer Science, 5(03), 381-418. doi: doi:10.1017/S0960129500000803

Recommended Citation

Connelly, Richard H. and Morris, F. Lockwood, "A Generalization of the Trie Data Structure" (1993). Electrical Engineering and Computer Science - Technical Reports. 162.
https://surface.syr.edu/eecs_techreports/162

Source

local