A grammatical term algebra $GT{A}_L$ of a language $L$ is a partial algebra $⟨G{T}_L,A{T}_L,{\mathrm{\Sigma }}_L⟩$, where—

1. $G{T}_L$ is the set of grammatical terms for $L$,
2. $A{T}_L$ is a finite set of atomic (grammatical) terms for $L$, and
3. ${\mathrm{\Sigma }}_L$ is a finite set of syntactic operations for $L$. $G{T}_L$ is the closure of $A{T}_L$ under ${\mathrm{\Sigma }}_L$.

A meaning operation $r$ over a domain of meanings $M$ is some function $M^n\to M$.

Where $GT{A}_L$ is a grammatical term algebra and $M$ is a domain of meanings, any $\mu :G{T}_L\to M$ is a semantic function.

Given a grammatical term algebra $GT{A}_L$ and domain $M$ of meanings, a semantic function $\mu :G{T}_L\to M$ is standard compositional iff for every $n$-ary operation $\sigma \in {\mathrm{\Sigma }}_L$ there is a meaning operation $r_{\sigma }:M^n\to M$ such that for any $t_1,...,t_n\in Dom\sigma \subseteq G{T}_L$, $$\mu (\sigma (t_1,...,t_n))=r_{\sigma }(\mu (t_1),...,\mu (t_n)).$$

A semantic system $S$ is general compositional iff for every $n$-ary operation $\sigma \in {\mathrm{\Sigma }}_L$ and every member ${\mu }_i\in S^{\prime }$ there is a meaning operation $M^n\to M$ such that for any grammatical terms $t_1,...,t_n\in Dom\sigma$ $${\mu }_i(\sigma (t_1,...,t_n))=r_{\sigma ,i}({\mu }_{j_1}(t_1),...,{\mu }_{j_n}(t_n)),$$ where for $1⩽k⩽n$ $${\mu }_{j_k}={\mathrm{\Phi }}_S({\mu }_i,\sigma ,k).$$

A meaning algebra over a set of meanings $M$ is a triple $M{A}_M=⟨M,B_M,R_M⟩$, where—

1. $B_M$ is a finite set of basic meanings,
2. $R_M$ is a finite set of elementary meaning operations,
3. $M$ closes $B_M$ under $R_M$, and
4. for all $\delta ,{\delta }^{\prime }\in R_M$ and $x_1,...x_n,y_1,...,y_m$, $$\delta (x_1,...,x_n)\notin B_M$$ and, if $$\delta (x_1,...,x_n)={\delta }^{\prime }(y_1,...,y_m)$$ then $\delta ={\delta }^{\prime }$, $m=n$, and $x_i=y_i$ for $1⩽i⩽n$.

Given a grammatical term algebra $GT{A}_L$ and domain $M$ of meanings, a semantic system $S$ is a triple $⟨S^{\prime },{\mu }_S,{\mathrm{\Phi }}_S⟩$ where—

1. $S^{\prime }$ is a finite set of semantic functions ${\mu }_j:G{T}_L\to M$, ${\mu }_S\in S$, and
2. ${\mathrm{\Phi }}_S:S^{\prime }\times {\mathrm{\Sigma }}_L\times N\to S^{\prime }$ is a partial selection function.

Given some semantic function ${\mu }_j$ and a syntactic operation $\sigma$, ${\mathrm{\Phi }}_S$ then gives another semantic function ${\mu }_k$ for each $n$th-position term.

Finally, $S(t)={\mu }_S(t)$.

A semantic algebra over a language $L$ and domain $M$ of meanings is a triple $$S{A}_{L}M=⟨⟨G{T}_L,M⟩,⟨A{T}_L,B_M⟩,⟨{\mathrm{\Sigma }}_L,R_M⟩⟩$$ where—

1. $⟨G{T}_L,A{T}_L,{\mathrm{\Sigma }}_L⟩$ is a grammatical term algebra for $L$, and
2. $⟨M,B_M,R_M⟩$ is a meaning algebra for $M$.

The size of a term is the number of atoms and operators contained within it.

The input terms of a rewriting system are of the form ‘$\mu (t)$’ where $t$ is a syntactic term.

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 $\mu (t)$ to $s$.

The input complexity $C_R^i(k)$ is the maximal $C{t}_R(s)$ where $s$ has size $k$.

A term rewrite system (TRS) $\mathrm{\Phi }$ is a pair $⟨{\mathrm{\Sigma }}_{\mathrm{\Phi }},R_{\mathrm{\Phi }}⟩$ where—

1. ${\mathrm{\Sigma }}_{\mathrm{\Phi }}$ is a signature comprising a finite set of $n$-ary operators (including nullary constants), and
2. $R_{\mathrm{\Phi }}$ is a set of reductions over the set $T_{\mathrm{\Phi }}$ of terms over ${\mathrm{\Sigma }}_{\mathrm{\Phi }}$.

We will write $t_1{\to }_{\mathrm{\Phi }}{t}_2$ (omitting the subscript where context makes it obvious) when the application of some rule $r\in R_{\mathrm{\Phi }}$ yields the contractum $t_2$.

A sequence of applications $t_1\to t_2\to ...\to t_n$ is a derivation. We write $t_1{\to }_{\mathrm{\Phi }}^{+}{t}_n$ where ${\to }_{\mathrm{\Phi }}^{+}$ is the transitive closure of $\to$.

A $\mu$-system is a pair $\mathrm{\Phi }=⟨{\mathrm{\Sigma }}_{\mathrm{\Phi }},R_{\mathrm{\Phi }}⟩$ where—

1. $\mathrm{\Sigma }=⟨{\mathrm{\Sigma }}_o,{\mathrm{\Sigma }}_m⟩$ (an object- and meta-language signature),
2. ${\mathrm{\Sigma }}_o=⟨A_o,{\mathrm{\Sigma }}_o^{\prime }⟩$ where $A_o$ is a set of atomic terms and ${\mathrm{\Sigma }}^{\prime }$ is a set of $n$-ary syntactic operators, so that the closure $T_o$ of $A_O$ under ${\mathrm{\Sigma }}^{\prime }$ yields the grammatical term algebra $⟨T_O,A_O,{\mathrm{\Sigma }}_O^{\prime }⟩$ of OL,
3. ${\mathrm{\Sigma }}_m=⟨A_m,{\mathrm{\Sigma }}_m^{\prime },S,F,G⟩$ where—
1. $A_m$ is a nonempty set of atomic meta-language expressions,
2. ${\mathrm{\Sigma }}_m^{\prime }$ is a nonempty set of meta-language syntactic operators,
3. $S$ is a nonempty set of elementary meta-language function symbols,
4. $F$ is a possibly empty set of meta-language recursive function symbols over object language terms, and
5. $G$ is a possibly empty set of meta-language recursive function symbols over meta-language terms.

A complex indirect constant $\mu$-system $\mathrm{\Phi }$ must satisfy the following.

1. $R_{\mathrm{\Phi }}$ is finite.
2. For any rule, the rewrite variables on the rhs must be a subset of those on the left.
3. Rewrite variables $v_1,v_2,...$ take all and only object language grammatical terms as instances.
4. Rewrite variables $y_1,y_2,...$ take all and only expressions in $C_m$ as instances.
5. Every atomic rule $r\in R_{\mathrm{\Phi }}$ is of the form $${\mu }_i(t)\to e$$ where ${\mu }_i\in S$, $t\in A_O$ and $e$ is a simple or complex expression in $C_m$.
6. For every pair $⟨{\mu }_i\in S,t\in A_o⟩$ there is an atomic rule.
7. Every direct complex rule $r$ has the form $${\mu }_i(\alpha (v_1,...,v_n))\to K({\mu }_{k_1}(v_1),...,{\mu }_{k_n}(v_n))\Leftarrow \mathrm{Gr}(\alpha (v_1,...,v_n))$$ where Gr corresponds to grammaticality.
8. Every indirect complex rule has the form $${\mu }_i(\alpha (v_1,...,v_n))\to f({\mu }_{k_1}(v_1),...,{\mu }_{k_n}(v_n),v_1,...,v_n)\Leftarrow \mathrm{Gr}(\alpha (v_1,...,v_n))$$ where $v_1,...,v_n$ are optional and $f\in F$.
9. For every pair $⟨{\mu }_i\in S,\alpha \in {\mathrm{\Sigma }}_o^{\prime }$, there is a unique complex (indirect or direct) rule.
10. Every indirect ground rule is of the $F$-form $$f(y_1,...,y_n,...,t_n)\to K^{\prime }(f^{\prime }(y_1,...,y_n))$$ or the $G$-form $$g(e_1,...,e_n)\to K(e_1,...,e_n)$$ where $f,f^{\prime }\in F$, $g\in G$, $K,K^{\prime }$ are operators over ${\mathrm{\Sigma }}_m^{\prime }$, $e_1,...,e_n\in A_m$ and $t_1,...,t_j\in A_o$, and at most one of the primed operators is null.
11. Every indirect recurisve rule in $R_{\mathrm{\Phi }}$ has an $F$-form $$f(y_1,...,y_n,\sigma (v_1,...,v_n))\to K(f(y_1,...,y_n,v_1)...,f(y_1,...,y_n,v_n))$$ or $G$-form $$g(K(y_1,...,y_n))\to K^{\prime }(g^{\prime }(y_1,...,y_n))$$ where $f\in F$, $g,g^{\prime }\in G$, $K,K^{\prime }$ are operators over ${\mathrm{\Sigma }}_m^{\prime }$, $\sigma \in {\mathrm{\Sigma }}_O^{\prime }$, and at most one of the primed operators is null.

Complex indirect constant systems are convergent (§ 8.3.4).

Given a complex indirect constant $\mu$-system, for any term $t$, there is some minimum derivation length to a unique normal form.

Let $\mathrm{\Phi }$ be any complex indirect constant $\mu$-system satisfying the following.

1. For every $n⩾1$, there are object-language atoms $a_1,...a_n\in A_o$ such that for every $1⩽k⩽n$, where $t_1={\alpha }_1$ and $t_{k+1}=\delta ({\alpha }_{k+1},t_k)$, for some canonical expression $e\in C_m$, $\mu (t_k){\to }_{\mathrm{\Phi }}^{+}e$, and $t_k\in T_o$.
2. The complex rule for $\mu ,\delta$ is $$\mu (\delta (v_1,v_2))\to f(\mu (v_1),\mu (v_2),v_2)\Leftarrow \mathrm{Gr}(d(v_1,v_2)).$$
3. There are rules $$f(y_1,y_2,\delta (v_1,v_2))\to K(f(y_1,y_2,v_1),f(y_1,y_2,v_2))$$ and $$f(y_1,y_2,\alpha )\to K_{\alpha }(y_1,y_2)$$ for each $\alpha \in A_o$.

Then $\mathrm{\Phi }$ is intractable.