Term indexing (Q2751378)

First-order terms are widely used in several disciplines of computer science such as term rewriting systems, symbolic computations, logic and functional programming, deductive databases. Therefore there is a need for fast algorithms to manipulate terms. This problem can be formulated abstractly as follows. Given a set \(L\) of terms (called the set of indexed terms), a binary relation R over terms (called the retrieval condition) and a term \(t\) (called the query term), identify the subset \(M\) of \(L\) consisting of all the terms \(l\) such that \(R(l, t)\) holds. The most common examples of retrieval conditions are unification, matching, subsumption. The paper gives detailed description of the term indexing techniques. It is shown how term indexing can be formulated in terms of string matching. This allows to consider many indexing methods as instances of the generic framework.NEWLINENEWLINEFor the entire collection see [Zbl 0964.00020].