Definition. Compositionality, computability, and complexity › Input complexity (§ 5) [pagin2021-input-complexity]

September 2021
Peter Pagin

Let $s$ be a normal term.

The term complexity $C t_{R} (s)$ of $s$ relative to $R$ is the length of the shortest derivation from some input term $μ (t)$ to $s$ .

The input complexity $C_{R}^{i} (k)$ is the maximal $C t_{R} (s)$ where $s$ has size $k$ .