Semisubstitution

Semisubstitution is a concept used in symbolic computation, logic, and related fields to describe a partially defined substitution operation. Unlike a full substitution, which replaces every occurrence of certain symbols throughout a term, semisubstitution targets only a chosen subset of variables or symbols, leaving the remaining parts of the term intact. This makes it useful for intermediate representations, partial evaluation, and staged computation.

Formally, let t be a term over a signature with variables Var. A semisubstitution is given by a partial mapping sigma from a subset D of Var to terms over the same signature. The semisubstitution t|sigma is obtained by applying sigma to every occurrence of variables in D within t while leaving variables outside D unchanged. If a variable from D appears in a subterm nested inside a function, the substitution propagates through the term structure in the usual way.

Example: consider the term t = f(x, g(y, z)) and a semisubstitution sigma with x -> a and y -> b. Then t|sigma = f(a, g(b, z)). Variables not in the domain, such as z, remain as z.

Properties and considerations include compatibility with renaming to avoid variable capture, and the fact that semisubstitutions can be composed when their domains are compatible, yielding another semisubstitution under appropriate conditions. Semisubstitution is monotone with respect to term structure and is a useful abstraction in partial evaluation, program analysis, and automated reasoning, where full substitution may be undesirable or impractical.

See also: substitution, partial evaluation, term rewriting, unification, alpha-renaming.