Home

subterms

Subterms are terms that occur within another term in the contexts of formal languages, logic, and algebra. Given a term built from function symbols (and possibly variables), a subterm of that term is any term that appears inside it as part of its syntactic structure. Every term is a subterm of itself; a proper subterm excludes the term itself.

Formally, if t = f(t1, ..., tn) where f is an n-ary function symbol and the ti are terms,

Example: for t = f(a, g(b, c)), the subterms are t itself, a, g(b, c), b, and c.

Properties and terminology: The subterm relation is reflexive, transitive, and antisymmetric, making it a partial order

Applications: Subterms are central in term rewriting and automated theorem proving, where they help in matching,

See also: superterm.

then
each
ti
is
a
subterm
of
t,
and
every
subterm
of
ti
is
also
a
subterm
of
t.
This
recursive
definition
yields
the
full
set
of
subterms
contained
in
t.
The
subterm
relation
is
typically
applied
to
finite
terms,
which
correspond
to
finite
syntax
trees.
Here
a,
b,
c
are
subterms
as
components
of
the
composite
terms,
and
t
is
a
subterm
of
itself.
on
the
set
of
terms.
For
finite
terms,
the
relation
is
well-founded,
which
supports
termination
arguments
in
rewriting
systems.
The
term
that
contains
another
as
a
subterm
is
called
a
superterm;
the
inverse
relation
is
often
used
in
analyses
of
structure
and
complexity.
substitution,
and
termination
proofs.
They
also
appear
in
symbolic
computation,
unification,
and
program
analysis
to
reason
about
the
components
and
structure
of
expressions.