{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:08:47Z","timestamp":1775912927528,"version":"3.50.1"},"reference-count":16,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2009,3,4]],"date-time":"2009-03-04T00:00:00Z","timestamp":1236124800000},"content-version":"unspecified","delay-in-days":4933,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[1995,9]]},"abstract":"<jats:p>Tries, a form of string-indexed look-up structure, are generalized, in a manner first discovered by Wadsworth, 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 that defines tries appeals from one value type to others. \u2018Trie\u2019 (for any fixed signature) is then a functor, and the corresponding look-up function is a natural isomorphism.<\/jats:p><jats:p>The trie functor is in principle definable by the \u2018initial fixed point\u2019 semantics of Smyth and Plotkin. We simplify the construction, however, by introducing the \u2018category-cpo\u2019, a class of category within which calculations can retain some domain-theoretic flavor. Our construction of tries extends easily to many-sorted signatures.<\/jats:p>","DOI":"10.1017\/s0960129500000803","type":"journal-article","created":{"date-parts":[[2009,3,4]],"date-time":"2009-03-04T04:01:13Z","timestamp":1236139273000},"page":"381-418","source":"Crossref","is-referenced-by-count":21,"title":["A generalization of the trie data structure"],"prefix":"10.1017","volume":"5","author":[{"given":"Richard H.","family":"Connelly","sequence":"first","affiliation":[]},{"given":"F. Lockwood","family":"Morris","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2009,3,4]]},"reference":[{"key":"S0960129500000803_ref009","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90068-D"},{"key":"S0960129500000803_ref007","doi-asserted-by":"publisher","DOI":"10.1145\/169701.169692"},{"key":"S0960129500000803_ref001","unstructured":"Beierle C. (1985) Algebraic Implementations in an Integrated Software Development and Verification System, dissertation, University of Kaiserlautern."},{"key":"S0960129500000803_ref004","unstructured":"Connelly R. H. and Morris F. L. (1993) A Generalization of the Trie Data Structure. Syracuse University School of Computer and Information Science report SU-CIS-93\u201323."},{"key":"S0960129500000803_ref015","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-51305-1_24"},{"key":"S0960129500000803_ref014","doi-asserted-by":"publisher","DOI":"10.1137\/0211062"},{"key":"S0960129500000803_ref003","unstructured":"Connelly R. H. (1990) A Comparison of Semantic Domains for Interleaving, dissertation, Syracuse University."},{"key":"S0960129500000803_ref005","doi-asserted-by":"publisher","DOI":"10.1145\/367390.367400"},{"key":"S0960129500000803_ref006","doi-asserted-by":"publisher","DOI":"10.1145\/321992.321997"},{"key":"S0960129500000803_ref002","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0018343"},{"key":"S0960129500000803_ref008","volume-title":"The Art of Computer Programming, Vol. 3: Sorting and Searching","author":"Knuth","year":"1973"},{"key":"S0960129500000803_ref010","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-9839-7"},{"key":"S0960129500000803_ref011","article-title":"Cartesian Closure \u2013 Higher Types in Categories","volume":"240","author":"Poign\u00e9","year":"1985","journal-title":"Springer-Verlag Lecture Notes in Computer Science"},{"key":"S0960129500000803_ref012","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-06841-4_57"},{"key":"S0960129500000803_ref013","volume-title":"Semantics as a Design Tool","author":"Reynolds","year":"1988"},{"key":"S0960129500000803_ref016","first-page":"87","volume":"8","author":"Wadsworth","year":"1979","journal-title":"Bulletin of the EATCS"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129500000803","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T17:03:31Z","timestamp":1557767011000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129500000803\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,9]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1995,9]]}},"alternative-id":["S0960129500000803"],"URL":"https:\/\/doi.org\/10.1017\/s0960129500000803","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,9]]}}}