Nesting and Defoliation of Index Expressions for Information Retrieval

In this article, a formalisation of index expressions is presented. Index expressions are more expressive than keywords while maintaining a comprehensible complexity. Index expressions are well-known in Information Retrieval (IR), where they are used for characterising document contents, formulation of user interests, and matching mechanisms. In addition, index expressions have found both practical and theoretical applicability in 2-level hypermedia systems for IR. In these applications, properties of (the structure of) index expressions are heavily relied upon. However, the presupposed mathematical formalisation of index expressions and their properties still lacks. Our formalism is based on the structural notation of index expressions. It is complete in the sense that several notions of subexpressions and defoliation of index expressions are also formalised. Defoliation, which plays an important role in defining properties of index expressions, is provided as a recursively defined operator. Finally, two other representational formalisms for index expressions are compared to ours. Received 9 July 1998 / Revised 20 April 1999 / Accepted in revised form 28 May 1999