Undersubstitution

Undersubstitution is a term used in some areas of logic, computer science, and formal linguistics to describe a substitution process in which not all intended variables or symbols are replaced. It denotes partial substitution, where the substitution mapping is applied only to a subset of occurrences, leaving others unchanged. This contrasts with full substitution, where every occurrence is replaced by its target.

In formal logic and term rewriting, undersubstitution can occur during partial evaluation or staged computation, where a substitution is applied as far as possible given constraints, with remaining variables preserved for later specialization. For example, given a term f(x, y) and a substitution {x -> a}, the result f(a, y) is obtained by undersubstituting x but not y. Partial substitutions must respect variable binding to avoid capture, and may be composed with further substitutions later.

In linguistics and semantics, some authors use the idea of undersubstitution to refer to representations that remain underspecified after a derivation, where certain elements are left as placeholders or metavariables until further interpretation. The term is not universally standardized; some scholars prefer "partial substitution" or "incomplete substitution." See also substitution, unification, partial evaluation, and underspecification.