Document Type

Report

Date

2-1993

Embargo Period

5-7-2012

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

Source

local

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.