Compositionality, computability, and complexity

Pagin, ‘Compositionality, computability, and complexity’

0.1. Definition. (Grammatical term algebra (§ 2.1))   A grammatical term algebra ${\text{GTA}}_{𝐿}$ of a language $𝐿$ is a partial algebra $⟨{\text{GT}}_{𝐿},{\text{AT}}_{𝐿},{\mathrm{\Sigma }}_{𝐿}⟩$, where—

1. ${\text{GT}}_{𝐿}$ is the set of grammatical terms for $𝐿$,
2. ${\text{AT}}_{𝐿}$ is a finite set of atomic (grammatical) terms for $𝐿$, and
3. ${\mathrm{\Sigma }}_{𝐿}$ is a finite set of syntactic operations for $𝐿$. ${\text{GT}}_{𝐿}$ is the closure of ${\text{AT}}_{𝐿}$ under ${\mathrm{\Sigma }}_{𝐿}$.

0.2. Definition. (Meaning operations (§ 2.2))   A meaning operation $𝑟$ over a domain of meanings $𝑀$ is some function ${𝑀}^{𝑛}\to 𝑀$.

0.3. Definition. (Semantic functions (§ 2.2))   Where ${\text{GTA}}_{𝐿}$ is a grammatical term algebra and $𝑀$ is a domain of meanings, any $𝜇:{\text{GT}}_{𝐿}\to 𝑀$ is a semantic function.

0.4. Definition. (Standard compositionality (§ 2.2))   Given a grammatical term algebra ${\text{GTA}}_{𝐿}$ and domain $𝑀$ of meanings, a semantic function $𝜇:{\text{GT}}_{𝐿}\to 𝑀$ is standard compositional iff for every $𝑛$-ary operation $𝜎\in {\mathrm{\Sigma }}_{𝐿}$ there is a meaning operation ${𝑟}_{𝜎}:{𝑀}^{𝑛}\to 𝑀$ such that for any ${𝑡}_1,\dots ,{𝑡}_{𝑛}\in Dom𝜎\subseteq {\text{GT}}_{𝐿}$,

$$𝜇\left(𝜎\left({𝑡}_1,\dots ,{𝑡}_{𝑛}\right)\right)={𝑟}_{𝜎}\left(𝜇\left({𝑡}_1\right),\dots ,𝜇\left({𝑡}_{𝑛}\right)\right).$$

0.5. Definition. (General compositionality (§ 2.3))   A semantic system $𝑆$ is general compositional iff for every $𝑛$-ary operation $𝜎\in {\mathrm{\Sigma }}_{𝐿}$ and every member ${𝜇}_{𝑖}\in {𝑆}^{\prime }$ there is a meaning operation ${𝑀}^{𝑛}\to 𝑀$ such that for any grammatical terms ${𝑡}_1,\dots ,{𝑡}_{𝑛}\in Dom𝜎$

$${𝜇}_{𝑖\left(𝜎\left({𝑡}_1,\dots ,{𝑡}_{𝑛}\right)\right)}={𝑟}_{𝜎,𝑖}\left({𝜇}_{{𝑗}_1}\left({𝑡}_1\right),\dots ,{𝜇}_{{𝑗}_{𝑛}}\left({𝑡}_{𝑛}\right)\right),$$

where for $1⩽𝑘⩽𝑛$

$${𝜇}_{{𝑗}_{𝑘}}={\mathrm{\Phi }}_{𝑆\left({𝜇}_{𝑖},𝜎,𝑘\right)}.$$

0.6. Definition. (Meaning algebras (§ 3))   A meaning algebra over a set of meanings $𝑀$ is a triple ${\text{MA}}_{𝑀}=⟨𝑀,{𝐵}_{𝑀},{𝑅}_{𝑀}⟩$, where—

1. ${𝐵}_{𝑀}$ is a finite set of basic meanings,
2. ${𝑅}_{𝑀}$ is a finite set of elementary meaning operations,
3. $𝑀$ closes ${𝐵}_{𝑀}$ under ${𝑅}_{𝑀}$, and

4. for all $𝛿,𝛿\prime \in {𝑅}_{𝑀}$ and ${𝑥}_1,\dots {𝑥}_{𝑛},{𝑦}_1,\dots ,{𝑦}_{𝑚}$,

   $$𝛿\left({𝑥}_1,\dots ,{𝑥}_{𝑛}\right)\notin {𝐵}_{𝑀}$$

   and, if

   $$𝛿\left({𝑥}_1,\dots ,{𝑥}_{𝑛}\right)=𝛿\prime \left({𝑦}_1,\dots ,{𝑦}_{𝑚}\right)$$

   then $𝛿=𝛿\prime$, $𝑚=𝑛$, and ${𝑥}_{𝑖}={𝑦}_{𝑖}$ for $1⩽𝑖⩽𝑛$.

0.7. Definition. (Semantic systems (§ 3))   Given a grammatical term algebra ${\text{GTA}}_{𝐿}$ and domain $𝑀$ of meanings, a semantic system $𝑆$ is a triple $⟨{𝑆}^{\prime },{𝜇}_{𝑆},{\mathrm{\Phi }}_{𝑆}⟩$ where—

1. ${𝑆}^{\prime }$ is a finite set of semantic functions ${𝜇}_{𝑗}:{\text{GT}}_{𝐿}\to 𝑀$, ${𝜇}_{𝑆}\in 𝑆$, and
2. ${\mathrm{\Phi }}_{𝑆}:{𝑆}^{\prime }\times {\mathrm{\Sigma }}_{𝐿}\times 𝑁\to {𝑆}^{\prime }$ is a partial selection function.

Given some semantic function ${𝜇}_{𝑗}$ and a syntactic operation $𝜎$, ${\mathrm{\Phi }}_{𝑆}$ then gives another semantic function ${𝜇}_{𝑘}$ for each $𝑛$th-position term.

Finally, $𝑆\left(𝑡\right)={𝜇}_{𝑆\left(𝑡\right)}$.

0.8. Definition. (Semantic algebras (§ 3))   A semantic algebra over a language $𝐿$ and domain $𝑀$ of meanings is a triple

$${\text{SA}}_{\text{LM}}=⟨⟨{\text{GT}}_{𝐿},𝑀⟩,⟨{\text{AT}}_{𝐿},{𝐵}_{𝑀}⟩,⟨{\mathrm{\Sigma }}_{𝐿},{𝑅}_{𝑀}⟩⟩$$

where—

1. $⟨{\text{GT}}_{𝐿},{\text{AT}}_{𝐿},{\mathrm{\Sigma }}_{𝐿}⟩$ is a grammatical term algebra for $𝐿$, and
2. $⟨𝑀,{𝐵}_{𝑀},{𝑅}_{𝑀}⟩$ is a meaning algebra for $𝑀$.

0.9. Definition. (Size (§ 5))   The size of a term is the number of atoms and operators contained within it.

0.10. Definition. (Input terms (§ 5))   The input terms of a rewriting system are of the form ‘$𝜇\left(𝑡\right)$’ where $𝑡$ is a syntactic term.

0.11. Definition. (Input complexity (§ 5))   Let $𝑠$ be a normal term.

The term complexity ${\text{Ct}}_{𝑅\left(𝑠\right)}$ of $𝑠$ relative to $𝑅$ is the length of the shortest derivation from some input term $𝜇\left(𝑡\right)$ to $𝑠$.

The input complexity ${𝐶}_{𝑅}^{𝑖\left(𝑘\right)}$ is the maximal ${\text{Ct}}_{𝑅\left(𝑠\right)}$ where $𝑠$ has size $𝑘$.

0.12. Definition. (Term rewrite systems (§ 6.1))   A term rewrite system (TRS) $\mathrm{\Phi }$ is a pair $⟨{\mathrm{\Sigma }}_{\mathrm{\Phi }},{𝑅}_{\mathrm{\Phi }}⟩$ where—

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

We will write ${𝑡}_1\underset{\mathrm{\Phi }}{\to }{𝑡}_2$ (omitting the subscript where context makes it obvious) when the application of some rule $𝑟\in {𝑅}_{\mathrm{\Phi }}$ yields the contractum ${𝑡}_2$.

A sequence of applications ${𝑡}_1\to {𝑡}_2\to \dots \to {𝑡}_{𝑛}$ is a derivation. We write ${𝑡}_1\underset{\mathrm{\Phi }}{\overset{+}{\to }}{𝑡}_{𝑛}$ where $\underset{\mathrm{\Phi }}{\overset{+}{\to }}$ is the transitive closure of $\to$.

0.13. Definition. (Conditional term rewrite systems (§ 6.1))   In a conditional term rewrite system ${\mathrm{\Sigma }}_{\mathrm{\Phi }},{𝑅}_{\mathrm{\Phi }}$, the reductions are conditioned over some conditions ${𝐶}_1,\dots ,{𝐶}_{𝑛}$.

0.14. Definition. (Many-sorted term rewrite systems (§ 6.1))   In a many-sorted term rewrite system, ${𝑇}_{\mathrm{\Psi }}$ is partitioned into subsets corresponding to sorts, and argument places for operators have sort restrictions; complex terms whose subterms satisfy the sort restrictions are well-sorted (corresponding to grammaticality).

0.15. Definition. (Normal form (§ 6.1))   A term that cannot be reduced further is in normal form.

0.16. Definition. (Termination (§ 6.1))   If every derivation leads to a term in normal form, a system terminates.

0.17. Definition. (Confluence (§ 6.1))   $\mathrm{\Phi }$ is confluent iff, for all terms ${𝑡}_1,{𝑡}_2,{𝑡}_3$, whenever ${𝑡}_1\underset{\mathrm{\Phi }}{\overset{+}{\to }}{𝑡}_2$ and ${𝑡}_1\underset{\mathrm{\Phi }}{\overset{+}{\to }}{𝑡}_3$, there is some ${𝑡}_4$ such that ${𝑡}_2\underset{\mathrm{\Phi }}{\overset{+}{\to }}{𝑡}_4$ and ${𝑡}_3\underset{\mathrm{\Phi }}{\overset{+}{\to }}{𝑡}_4$.

0.18. Definition. (Convergence (§ 6.1))   A confluent system that terminates is convergent.

0.19. Definition. (#{\mu}-systems (§ 6.1))   A $𝜇$-system is a pair $\mathrm{\Phi }=⟨{\mathrm{\Sigma }}_{\mathrm{\Phi }},{𝑅}_{\mathrm{\Phi }}⟩$ where—

1. $\mathrm{\Sigma }=⟨{\mathrm{\Sigma }}_{𝑜},{\mathrm{\Sigma }}_{𝑚}⟩$ (an object- and meta-language signature),
2. ${\mathrm{\Sigma }}_{𝑜}=⟨{𝐴}_{𝑜},\mathrm{\Sigma }{\prime }_{𝑜}⟩$ where ${𝐴}_{𝑜}$ is a set of atomic terms and $\mathrm{\Sigma }\prime$ is a set of $𝑛$-ary syntactic operators, so that the closure ${𝑇}_{𝑜}$ of ${𝐴}_{𝑂}$ under $\mathrm{\Sigma }\prime$ yields the grammatical term algebra $⟨{𝑇}_{𝑂},{𝐴}_{𝑂},\mathrm{\Sigma }{\prime }_{𝑂}⟩$ of OL,
3. ${\mathrm{\Sigma }}_{𝑚}=⟨{𝐴}_{𝑚},\mathrm{\Sigma }{\prime }_{𝑚},𝑆,𝐹,𝐺⟩$ where—
4. ${𝐴}_{𝑚}$ is a nonempty set of atomic meta-language expressions,
5. $\mathrm{\Sigma }{\prime }_{𝑚}$ is a nonempty set of meta-language syntactic operators,
6. $𝑆$ is a nonempty set of elementary meta-language function symbols,
7. $𝐹$ is a possibly empty set of meta-language recursive function symbols over object language terms, and
8. $𝐺$ is a possibly empty set of meta-language recursive function symbols over meta-language terms.

0.20. Remark.   The canonical expressions of ML, ${𝐶}_{𝑚}$, close ${𝐴}_{𝑚}$ under $\mathrm{\Sigma }{\prime }_{𝑚}$, canonically express meanings, do not contain any $𝜇$ operators or $𝐹$/$𝐺$ functors, and rewrite derivations terminate with them.

0.21. Remark.   The set $𝑆$ of the semantic vocabulary of $\mathrm{\Phi }$ contains at least the semantic function symbol $𝜇$ and is finite.

0.22. Remark.   The set $𝑆\left({𝑇}_{𝑜}\right)$ of $𝜇$-terms is the set of input terms to derivations, given by applying a semantic function symbol to an OL term.

0.23. Remark.   $𝐹$ and $𝐺$ contain additional function symbols do not represent semantic functions, are not inputs to any rules in ${𝑅}_{\mathrm{\Phi }}$, but can take arguments from ${𝑇}_{𝑂}$, $𝑆\left({𝑇}_{𝑜}\right)$, and ${𝐶}_{𝑚}$.

0.24. Remark.   The set ${𝑇}_{𝑚}$ of meta-linguistic terms of ${\mathrm{\Sigma }}_{𝑀}$ is the closure of ${𝐴}_{𝑚}\cup {𝑇}_{𝑜}$ under $\mathrm{\Sigma }{\prime }_{𝑚}\cup 𝑆\cup 𝐹\cup 𝐺$.

0.25. Definition. (Complex indirect constant #{\mu}-systems (§ 8.3.4))   A complex indirect constant $𝜇$-system $\mathrm{\Phi }$ must satisfy the following.

1. ${𝑅}_{\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 ${𝑣}_1,{𝑣}_2,\dots$ take all and only object language grammatical terms as instances.
4. Rewrite variables ${𝑦}_1,{𝑦}_2,\dots$ take all and only expressions in ${𝐶}_{𝑚}$ as instances.

5. Every atomic rule $𝑟\in {𝑅}_{\mathrm{\Phi }}$ is of the form

   $${𝜇}_{𝑖\left(𝑡\right)}\to 𝑒$$

   where ${𝜇}_{𝑖}\in 𝑆$, $𝑡\in {𝐴}_{𝑂}$ and $𝑒$ is a simple or complex expression in ${𝐶}_{𝑚}$.

6. For every pair $⟨{𝜇}_{𝑖}\in 𝑆,𝑡\in {𝐴}_{𝑜}⟩$ there is an atomic rule.

7. Every direct complex rule $𝑟$ has the form

   $${𝜇}_{𝑖\left(𝛼\left({𝑣}_1,\dots ,{𝑣}_{𝑛}\right)\right)}\to 𝐾\left({𝜇}_{{𝑘}_1}\left({𝑣}_1\right),\dots ,{𝜇}_{{𝑘}_{𝑛}}\left({𝑣}_{𝑛}\right)\right)\Leftarrow \text{Gr}\left(𝛼\left({𝑣}_1,\dots ,{𝑣}_{𝑛}\right)\right)$$

   where Gr corresponds to grammaticality.

8. Every indirect complex rule has the form

   $${𝜇}_{𝑖\left(𝛼\left({𝑣}_1,\dots ,{𝑣}_{𝑛}\right)\right)}\to 𝑓\left({𝜇}_{{𝑘}_1}\left({𝑣}_1\right),\dots ,{𝜇}_{{𝑘}_{𝑛}}\left({𝑣}_{𝑛}\right),{𝑣}_1,\dots ,{𝑣}_{𝑛}\right)\Leftarrow \text{Gr}\left(𝛼\left({𝑣}_1,\dots ,{𝑣}_{𝑛}\right)\right)$$

   where ${𝑣}_1,\dots ,{𝑣}_{𝑛}$ are optional and $𝑓\in 𝐹$.

9. For every pair $⟨{𝜇}_{𝑖}\in 𝑆,𝛼\in \mathrm{\Sigma }{\prime }_{𝑜}$, there is a unique complex (indirect or direct) rule.

10. Every indirect ground rule is of the $𝐹$-form

    $$𝑓\left({𝑦}_1,\dots ,{𝑦}_{𝑛},\dots ,{𝑡}_{𝑛}\right)\to {𝐾}^{\prime }\left({𝑓}^{\prime }\left({𝑦}_1,\dots ,{𝑦}_{𝑛}\right)\right)$$

    or the $𝐺$-form

    $$𝑔\left({𝑒}_1,\dots ,{𝑒}_{𝑛}\right)\to 𝐾\left({𝑒}_1,\dots ,{𝑒}_{𝑛}\right)$$

    where $𝑓,{𝑓}^{\prime }\in 𝐹$, $𝑔\in 𝐺$, $𝐾,{𝐾}^{\prime }$ are operators over $\mathrm{\Sigma }{\prime }_{𝑚}$, ${𝑒}_1,\dots ,{𝑒}_{𝑛}\in {𝐴}_{𝑚}$ and ${𝑡}_1,\dots ,{𝑡}_{𝑗}\in {𝐴}_{𝑜}$, and at most one of the primed operators is null.

11. Every indirect recurisve rule in ${𝑅}_{\mathrm{\Phi }}$ has an $𝐹$-form

    $$𝑓\left({𝑦}_1,\dots ,{𝑦}_{𝑛},𝜎\left({𝑣}_1,\dots ,{𝑣}_{𝑛}\right)\right)\to 𝐾\left(𝑓\left({𝑦}_1,\dots ,{𝑦}_{𝑛},{𝑣}_1\right)\dots ,𝑓\left({𝑦}_1,\dots ,{𝑦}_{𝑛},{𝑣}_{𝑛}\right)\right)$$

    or $𝐺$-form

    $$𝑔\left(𝐾\left({𝑦}_1,\dots ,{𝑦}_{𝑛}\right)\right)\to {𝐾}^{\prime }\left({𝑔}^{\prime }\left({𝑦}_1,\dots ,{𝑦}_{𝑛}\right)\right)$$

    where $𝑓\in 𝐹$, $𝑔,{𝑔}^{\prime }\in 𝐺$, $𝐾,{𝐾}^{\prime }$ are operators over $\mathrm{\Sigma }{\prime }_{𝑚}$, $𝜎\in \mathrm{\Sigma }{\prime }_{𝑂}$, and at most one of the primed operators is null.

0.26. Proposition.   Complex indirect constant systems are convergent (§ 8.3.4).

0.1. Corollary.   Given a complex indirect constant $𝜇$-system, for any term $𝑡$, there is some minimum derivation length to a unique normal form.

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

1. For every $𝑛⩾1$, there are object-language atoms ${𝑎}_1,\dots {𝑎}_{𝑛}\in {𝐴}_{𝑜}$ such that for every $1⩽𝑘⩽𝑛$, where ${𝑡}_1={𝛼}_1$ and ${𝑡}_{𝑘+1}=𝛿\left({𝛼}_{𝑘+1},{𝑡}_{𝑘}\right)$, for some canonical expression $𝑒\in {𝐶}_{𝑚}$, $𝜇\left({𝑡}_{𝑘}\right)\underset{\mathrm{\Phi }}{\overset{+}{\to }}𝑒$, and ${𝑡}_{𝑘}\in {𝑇}_{𝑜}$.

2. The complex rule for $𝜇,𝛿$ is

   $$𝜇\left(𝛿\left({𝑣}_1,{𝑣}_2\right)\right)\to 𝑓\left(𝜇\left({𝑣}_1\right),𝜇\left({𝑣}_2\right),{𝑣}_2\right)\Leftarrow \text{Gr}\left(𝑑\left({𝑣}_1,{𝑣}_2\right)\right).$$

3. There are rules

   $$𝑓\left({𝑦}_1,{𝑦}_2,𝛿\left({𝑣}_1,{𝑣}_2\right)\right)\to 𝐾\left(𝑓\left({𝑦}_1,{𝑦}_2,{𝑣}_1\right),𝑓\left({𝑦}_1,{𝑦}_2,{𝑣}_2\right)\right)$$

   and

   $$𝑓\left({𝑦}_1,{𝑦}_2,𝛼\right)\to {𝐾}_{𝛼}\left({𝑦}_1,{𝑦}_2\right)$$

   for each $𝛼\in {𝐴}_{𝑜}$.

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

0.28. Lemma.   Fix some $𝑘⩾1$ and ${𝛼}_1,\dots ,{𝛼}_{𝑘}$. Define

$$𝐹\left(𝑡\right)≔𝑓\left(𝜇\left({𝛼}_{𝑘+1},𝜇\left({𝑡}_{𝑘}\right),{𝑡}^{\prime }\right)\right).$$

Moreover, define $𝑙\left(𝑡\right)$ as the number of atomic leaves of $𝑡$.

For every object-language subterm $𝑡$ of ${𝑡}_{𝑘}$,

$$𝑇\left(𝐹\left(𝑡\right)\right)⩾𝑙\left(𝑡\right)\cdot 𝑇\left(𝜇\left({𝑡}_{𝑘}\right)\right).$$

Proof. By structural induction on $𝑡$.

If $𝑡=𝛼\in {𝐴}_{𝑂}$, $𝐹\left(𝛼\right)$ has subterm $𝜇\left({𝑡}_{𝑘}\right)$, which must be reduced to eliminate $𝑚$ to obtain a canonical form. Moreover, there is only one atomic leaf. So

$$𝑇\left(𝐹\left(𝑎\right)\right)⩾𝑇\left(𝜇\left({𝑡}_{𝑘}\right)\right)=1\cdot 𝑇\left(𝜇\left({𝑡}_{𝑘}\right)\right).$$

Suppose $𝑡=𝛿\left({𝑡}_1,{𝑡}_2\right)$. Normalisation requires elimination of the root $𝑓$ of $𝐹\left(𝑡\right)$. Since the third argument has head $𝛿$, only

$$𝑓\left({𝑦}_1,{𝑦}_2,𝛿\left({𝑣}_1,{𝑣}_2\right)\right)\to 𝐾\left(𝑓\left({𝑦}_1,{𝑦}_2,{𝑣}_1\right),𝑓\left({𝑦}_1,{𝑦}_2,{𝑣}_2\right)\right)$$

will do so. Every derivation (minimum-length or otherwise) will have to apply that rule at some point. Without loss of generality, apply it at the beginning. Then

$$𝐹\left(𝑡\right)\to 𝐾\left(𝐹\left({𝑡}_1\right),𝐹\left({𝑡}_2\right)\right).$$

Note $𝐾$ is terminal by definition of complex indirect constant $𝜇$-systems. So

$$𝑇\left(𝐹\left(𝑡\right)\right)=1+𝑇\left(𝐹\left({𝑡}_1\right)\right)+𝑇\left(𝐹\left({𝑡}_2\right)\right)⩾𝑙\left({𝑡}_1\right)\cdot 𝑇\left(𝜇\left({𝑡}_{𝑘}\right)\right)+𝑙\left({𝑡}_2\right)\cdot 𝑇\left(𝜇\left({𝑡}_{𝑘}\right)\right)=𝑙\left(𝑡\right)\cdot 𝑇\left(𝜇\left({𝑡}_{𝑘}\right)\right).$$

Proof. Now consider a minimum-length derivation of $𝜇\left({𝑡}_{𝑘+1}\right)$. There is some minimum-length derivation that begins

$$𝜇\left({𝑡}_{𝑘+1}\right)\to 𝐹\left({𝑡}_{𝑘}\right)$$

whence

$$𝑇\left(𝜇\left({𝑡}_{𝑘{+}_1}\right)\right)=1+𝑇\left(𝐹\left({𝑡}_{𝑘}\right)\right)⩾𝑘\cdot 𝑇\left(𝜇\left({𝑡}_{𝑘}\right)\right)$$

whence $𝑇\left(𝜇\left({𝑡}_{𝑛}\right)\right)⩾\left(𝑛-1\right)!$.⁠$\square$