A family of data-structure and algorithm techniques for organizing terms, subterms, or clauses so that syntactic matches, unification partners, or pattern occurrences can be retrieved quickly during automated reasoning.

Principle

Exploit compact discriminating features of terms (symbols, paths, fingerprints, positions) to avoid brute-force pairwise matching; index structures trade space and update cost for fast query-time candidate retrieval while preserving correctness for syntactic matching or unification.

Demonstration

In a saturation-based first-order prover, a discrimination tree stores indexed terms by their symbol sequence so that, when selecting a literal f(a, X) to resolve, the prover retrieves only clauses containing unifiable terms with head symbol f rather than scanning the whole clause database. Another example is a substitution tree used to enumerate all terms that unify with a query term, returning candidate clause identifiers in sublinear time relative to the database size.

Misapplication

Using an index keyed only by root symbols for queries that require structural subterm matching leads to many false candidates and no time savings; equally, creating extremely specialized indexes without considering update costs can make incremental lemma addition prohibitively expensive in interactive provers.

Consequence

Correctly designed term indexes reduce the number of expensive syntactic unification attempts, drastically lowering prover runtimes and memory churn on large knowledge bases while enabling scalable retrieval services such as premise selection and matching-based simplification.

Reversal

Without term indexing, the system must perform exhaustive pairwise term comparisons or full-scan pattern matching; the inverted contrast is an index designed for model-oriented semantic queries (e.g., indexing valuations) which targets different retrieval goals and may not serve syntactic unification.

Boundary

Applies to syntactic retrieval problems (exact matches, pattern matches, syntactic unification). It does not by itself provide semantic entailment, model checking, or probabilistic similarity search; it excludes purely statistical embedding techniques unless they are explicitly used as approximate index layers.

Semantic Tension

Tension exists between compact, fast-to-update indexes that return many coarse candidates (high recall, low precision) and rich structural indexes that are precise but expensive to maintain; another tension is between indexes optimized for batch construction vs incremental interactive use.

Synthesis

Term indexing is the practice of selecting and organizing discriminative structural features of terms into data structures (discrimination trees, substitution trees, signature hashes, path indexes) so that automated reasoners can rapidly narrow candidate sets for matching and unification, balancing retrieval speed against space and update costs.