Termbäume, Positionen

• Signatur Σ: Menge von Funktionssymbolen mit Stelligkeit, Bsp. {(s, 1),(z, 0),(p, 2)},
• Term(Σ) ist die kleinste Menge M mit ...

• Pos(t): Menge der Positionen in t∈Term(Σ): ...

• t(p) Symbol an Position p in t
• t$\mid_{p}^{}$ Teilterm an Position p in t (alternative Notation: t[p])

Beispiele:

• Term t = p(z, s(s(z))),
• Positionen Pos(t) = {ε, 0, 1, 10, 100},
• Symbol t(1) = s,         Teilterm t[1] = s(s(z)),