Termstrukturen

Termstrukturen, or term structures, are formal representations of symbolic expressions used in logic, computer science, and related fields. They are typically tree-shaped objects in which internal nodes are function symbols and leaves are constants or variables. The structure mirrors the syntactic form of the expression, with the arity of each function symbol determining how many subterms attach to it.

A standard way to describe term structures is via a signature: a set of function symbols each assigned a nonnegative arity, possibly including constant symbols (arity zero). Terms are built recursively from these symbols and from variables. A term without variables is called a ground term. The collection of all terms over a given signature and a set of variables forms a free term algebra, often used as the syntactic backbone of a formal language.

Semantics attach meaning to terms through interpretations. An interpretation assigns to each constant a domain element and to each n-ary function symbol a concrete function from D^n to D, where D is the domain. Evaluation then maps any term to an element of the domain by applying the interpretation to the term’s structure. This provides a bridge between syntax (the term structure) and semantics (the values they denote).

Term structures are central to many operations in logic and computer science. Term rewriting and equational theories manipulate terms using rules that preserve meaning, while unification seeks substitutions that make different terms identical under a theory. In automated reasoning, the Herbrand universe of ground terms under a signature is a foundational concept. In programming, term structures underpin abstract syntax trees and symbolic computation. Variants include term graphs, which represent terms with shared subterms to save space.