Journal. Review of Symbolic Logic [rsl]

Backlinks

Reference. Compositionality, computability, and complexity [pagin2021]

September 2021
Peter Pagin
Review of Symbolic Logic
10.1017/S1755020320000027
https://www.cambridge.org/core/journals/review-of-symbolic-logic/article/compositionality-computability-and-complexity/B166F47AC1DB1A67A9AD38CDA167B09B

Definition. Grammatical term algebra (§ 2.1) [pagin2021-gta]

September 2021
Peter Pagin

A grammatical term algebra $G T A_{L}$ of a language $L$ is a partial algebra $⟨ G T_{L}, A T_{L}, Σ_{L} ⟩$ , where—

$G T_{L}$ is the set of grammatical terms for $L$ ,
$A T_{L}$ is a finite set of atomic (grammatical) terms for $L$ , and
$Σ_{L}$ is a finite set of syntactic operations for $L$ . $G T_{L}$ is the closure of $A T_{L}$ under $Σ_{L}$ .

Definition. Meaning operations (§ 2.2) [pagin2021-meaning-operation]

September 2021
Peter Pagin

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

Definition. Semantic functions (§ 2.2) [pagin2021-semantic-function]

September 2021
Peter Pagin

Where $G T A_{L}$ is a grammatical term algebra and $M$ is a domain of meanings, any $μ : G T_{L} \to M$ is a semantic function.

Definition. Standard compositionality (§ 2.2) [pagin2021-standard-compositionality]

September 2021
Peter Pagin

Given a grammatical term algebra $G T A_{L}$ and domain $M$ of meanings, a semantic function $μ : G T_{L} \to M$ is standard compositional iff for every $n$ -ary operation $σ \in Σ_{L}$ there is a meaning operation $r_{σ} : M^{n} \to M$ such that for any $t_{1}, . . ., t_{n} \in Dom σ \subseteq G T_{L}$ , $μ (σ (t_{1}, . . ., t_{n})) = r_{σ} (μ (t_{1}), . . ., μ (t_{n})) .$

Definition. General compositionality (§ 2.3) [pagin2021-general-compositionality]

September 2021
Peter Pagin

A semantic system $S$ is general compositional iff for every $n$ -ary operation $σ \in Σ_{L}$ and every member $μ_{i} \in S^{'}$ there is a meaning operation $M^{n} \to M$ such that for any grammatical terms $t_{1}, . . ., t_{n} \in Dom σ$ $μ_{i} (σ (t_{1}, . . ., t_{n})) = r_{σ, i} (μ_{j_{1}} (t_{1}), . . ., μ_{j_{n}} (t_{n})),$ where for $1 ⩽ k ⩽ n$ $μ_{j_{k}} = Φ_{S} (μ_{i}, σ, k) .$

Definition. Meaning algebras (§ 3) [pagin2021-meaning-algebra]

September 2021
Peter Pagin

A meaning algebra over a set of meanings $M$ is a triple $M A_{M} = ⟨ M, B_{M}, R_{M} ⟩$ , where—

$B_{M}$ is a finite set of basic meanings,
$R_{M}$ is a finite set of elementary meaning operations,
$M$ closes $B_{M}$ under $R_{M}$ , and
for all $δ, δ^{'} \in R_{M}$ and $x_{1}, . . . x_{n}, y_{1}, . . ., y_{m}$ , $δ (x_{1}, . . ., x_{n}) \notin B_{M}$ and, if $δ (x_{1}, . . ., x_{n}) = δ^{'} (y_{1}, . . ., y_{m})$ then $δ = δ^{'}$ , $m = n$ , and $x_{i} = y_{i}$ for $1 ⩽ i ⩽ n$ .

Definition. Semantic systems (§ 3) [pagin2021-semantic-system]

September 2021
Peter Pagin

Given a grammatical term algebra $G T A_{L}$ and domain $M$ of meanings, a semantic system $S$ is a triple $⟨ S^{'}, μ_{S}, Φ_{S} ⟩$ where—

$S^{'}$ is a finite set of semantic functions $μ_{j} : G T_{L} \to M$ , $μ_{S} \in S$ , and
$Φ_{S} : S^{'} \times Σ_{L} \times N \to S^{'}$ is a partial selection function.

Given some semantic function $μ_{j}$ and a syntactic operation $σ$ , $Φ_{S}$ then gives another semantic function $μ_{k}$ for each $n$ th-position term.

Finally, $S (t) = μ_{S} (t)$ .

Definition. Semantic algebras (§ 3) [pagin2021-semantic-algebra]

September 2021
Peter Pagin

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} ⟩, ⟨ Σ_{L}, R_{M} ⟩ ⟩$ where—

$⟨ G T_{L}, A T_{L}, Σ_{L} ⟩$ is a grammatical term algebra for $L$ , and
$⟨ M, B_{M}, R_{M} ⟩$ is a meaning algebra for $M$ .

Definition. Size (§ 5) [pagin2021-size]

September 2021
Peter Pagin

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

Definition. Input terms (§ 5) [pagin2021-input-terms]

September 2021
Peter Pagin

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

Definition. 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$ .

Definition. Term rewrite systems (§ 6.1) [pagin2021-trs]

September 2021
Peter Pagin

A term rewrite system (TRS) $Φ$ is a pair $⟨ Σ_{Φ}, R_{Φ} ⟩$ where—

$Σ_{Φ}$ is a signature comprising a finite set of $n$ -ary operators (including nullary constants), and
$R_{Φ}$ is a set of reductions over the set $T_{Φ}$ of terms over $Σ_{Φ}$ .

We will write $t_{1} \to_{Φ} t_{2}$ (omitting the subscript where context makes it obvious) when the application of some rule $r \in R_{Φ}$ 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_{Φ}^{+} t_{n}$ where $\to_{Φ}^{+}$ is the transitive closure of $\to$ .

Definition. Conditional term rewrite systems (§ 6.1) [pagin2021-ctrs]

September 2021
Peter Pagin

In a conditional term rewrite system $Σ_{Φ}, R_{Φ}$ , the reductions are conditioned over some conditions $C_{1}, . . ., C_{n}$ .

Definition. Many-sorted term rewrite systems (§ 6.1) [pagin2021-many-sorted-trs]

September 2021
Peter Pagin

In a many-sorted term rewrite system, $T_{P} s i$ 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).

Definition. Normal form (§ 6.1) [pagin2021-normal-form]

September 2021
Peter Pagin

A term that cannot be reduced further is in normal form.

Definition. Termination (§ 6.1) [pagin2021-terminate]

September 2021
Peter Pagin

If every derivation leads to a term in normal form, a system terminates.

Definition. Confluence (§ 6.1) [pagin2021-confluence]

September 2021
Peter Pagin

$Φ$ is confluent iff, for all terms $t_{1}, t_{2}, t_{3}$ , whenever $t_{1} \to_{Φ}^{+} t_{2}$ and $t_{1} \to_{Φ}^{+} t_{3}$ , there is some $t_{4}$ such that $t_{2} \to_{Φ}^{+} t_{4}$ and $t_{3} \to_{Φ}^{+} t_{4}$ .

Definition. Convergence (§ 6.1) [pagin2021-convergence]

September 2021
Peter Pagin

A confluent system that terminates is convergent.

Definition. $μ$ -systems (§ 6.1) [pagin2021-mu-system]

September 2021
Peter Pagin

A $μ$ -system is a pair $Φ = ⟨ Σ_{Φ}, R_{Φ} ⟩$ where—

$Σ = ⟨ Σ_{o}, Σ_{m} ⟩$ (an object- and meta-language signature),
$Σ_{o} = ⟨ A_{o}, Σ_{o}^{'} ⟩$ where $A_{o}$ is a set of atomic terms and $Σ^{'}$ is a set of $n$ -ary syntactic operators, so that the closure $T_{o}$ of $A_{O}$ under $Σ^{'}$ yields the grammatical term algebra $⟨ T_{O}, A_{O}, Σ_{O}^{'} ⟩$ of OL,
$Σ_{m} = ⟨ A_{m}, Σ_{m}^{'}, S, F, G ⟩$ where—

$A_{m}$ is a nonempty set of atomic meta-language expressions,
$Σ_{m}^{'}$ is a nonempty set of meta-language syntactic operators,
$S$ is a nonempty set of elementary meta-language function symbols,
$F$ is a possibly empty set of meta-language recursive function symbols over object language terms, and
$G$ is a possibly empty set of meta-language recursive function symbols over meta-language terms.

Remark.

September 2021
Peter Pagin

The canonical expressions of ML, $C_{m}$ , close $A_{m}$ under $Σ_{m}^{'}$ , canonically express meanings, do not contain any $μ$ operators or $F$ / $G$ functors, and rewrite derivations terminate with them.

Remark.

September 2021
Peter Pagin

The set $S$ of the semantic vocabulary of $Φ$ contains at least the semantic function symbol $μ$ and is finite.

Remark.

September 2021
Peter Pagin

The set $S (T_{o})$ of $μ$ -terms is the set of input terms to derivations, given by applying a semantic function symbol to an OL term.

Remark.

September 2021
Peter Pagin

$F$ and $G$ contain additional function symbols do not represent semantic functions, are not inputs to any rules in $R_{Φ}$ , but can take arguments from $T_{O}$ , $S (T_{o})$ , and $C_{m}$ .

Remark.

September 2021
Peter Pagin

The set $T_{m}$ of meta-linguistic terms of $Σ_{M}$ is the closure of $A_{m} \cup T_{o}$ under $Σ_{m}^{'} \cup S \cup F \cup G$ .

Definition. Complex indirect constant $μ$ -systems (§ 8.3.4) [pagin2021-CIC]

September 2021
Peter Pagin

A complex indirect constant $μ$ -system $Φ$ must satisfy the following.

$R_{Φ}$ is finite.
For any rule, the rewrite variables on the rhs must be a subset of those on the left.
Rewrite variables $v_{1}, v_{2}, . . .$ take all and only object language grammatical terms as instances.
Rewrite variables $y_{1}, y_{2}, . . .$ take all and only expressions in $C_{m}$ as instances.
Every atomic rule $r \in R_{Φ}$ is of the form $μ_{i} (t) \to e$ where $μ_{i} \in S$ , $t \in A_{O}$ and $e$ is a simple or complex expression in $C_{m}$ .
For every pair $⟨ μ_{i} \in S, t \in A_{o} ⟩$ there is an atomic rule.
Every direct complex rule $r$ has the form $μ_{i} (α (v_{1}, . . ., v_{n})) \to K (μ_{k_{1}} (v_{1}), . . ., μ_{k_{n}} (v_{n})) \Leftarrow Gr (α (v_{1}, . . ., v_{n}))$ where Gr corresponds to grammaticality.
Every indirect complex rule has the form $μ_{i} (α (v_{1}, . . ., v_{n})) \to f (μ_{k_{1}} (v_{1}), . . ., μ_{k_{n}} (v_{n}), v_{1}, . . ., v_{n}) \Leftarrow Gr (α (v_{1}, . . ., v_{n}))$ where $v_{1}, . . ., v_{n}$ are optional and $f \in F$ .
For every pair $⟨ μ_{i} \in S, α \in Σ_{o}^{'}$ , there is a unique complex (indirect or direct) rule.
Every indirect ground rule is of the $F$ -form $f (y_{1}, . . ., y_{n}, . . ., t_{n}) \to K^{'} (f^{'} (y_{1}, . . ., y_{n}))$ or the $G$ -form $g (e_{1}, . . ., e_{n}) \to K (e_{1}, . . ., e_{n})$ where $f, f^{'} \in F$ , $g \in G$ , $K, K^{'}$ are operators over $Σ_{m}^{'}$ , $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.
Every indirect recurisve rule in $R_{Φ}$ has an $F$ -form $f (y_{1}, . . ., y_{n}, σ (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^{'} (g^{'} (y_{1}, . . ., y_{n}))$ where $f \in F$ , $g, g^{'} \in G$ , $K, K^{'}$ are operators over $Σ_{m}^{'}$ , $σ \in Σ_{O}^{'}$ , and at most one of the primed operators is null.

Proposition. [pagin2021-cic-terminate]

September 2021
Peter Pagin

Complex indirect constant systems are convergent (§ 8.3.4).

Corollary. [pagin2021-mdl]

September 2021
Peter Pagin

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

Proposition. [pagin2021-general]

September 2021
Peter Pagin

Let $Φ$ be any complex indirect constant $μ$ -system satisfying the following.

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} = α_{1}$ and $t_{k + 1} = δ (α_{k + 1}, t_{k})$ , for some canonical expression $e \in C_{m}$ , $μ (t_{k}) \to_{Φ}^{+} e$ , and $t_{k} \in T_{o}$ .
The complex rule for $μ, δ$ is $μ (δ (v_{1}, v_{2})) \to f (μ (v_{1}), μ (v_{2}), v_{2}) \Leftarrow Gr (d (v_{1}, v_{2})) .$
There are rules $f (y_{1}, y_{2}, δ (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}, α) \to K_{α} (y_{1}, y_{2})$ for each $α \in A_{o}$ .

Then $Φ$ is intractable.

Lemma.

September 2021
Peter Pagin

Fix some $k ⩾ 1$ and $α_{1}, . . ., α_{k}$ . Define $F (t) : = f (μ (α_{k + 1}, μ (t_{k}), t^{'})) .$

Moreover, define $l (t)$ as the number of atomic leaves of $t$ .

For every object-language subterm $t$ of $t_{k}$ , $T (F (t)) ⩾ l (t) \cdot T (μ (t_{k})) .$

Proof.

September 2021
Peter Pagin

By structural induction on $t$ .

If $t = α \in A_{O}$ , $F (α)$ has subterm $μ (t_{k})$ , which must be reduced to eliminate $m$ to obtain a canonical form. Moreover, there is only one atomic leaf. So $T (F (a)) ⩾ T (μ (t_{k})) = 1 \cdot T (μ (t_{k})) .$

Suppose $t = δ (t_{1}, t_{2})$ . Normalisation requires elimination of the root $f$ of $F (t)$ . Since the third argument has head $δ$ , only $f (y_{1}, y_{2}, δ (v_{1}, v_{2})) \to K (f (y_{1}, y_{2}, v_{1}), f (y_{1}, y_{2}, v_{2}))$ 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 $F (t) \to K (F (t_{1}), F (t_{2})) .$ Note $K$ is terminal by definition of complex indirect constant $μ$ -systems. So $T (F (t)) = 1 + T (F (t_{1})) + T (F (t_{2})) ⩾ l (t_{1}) \cdot T (μ (t_{k})) + l (t_{2}) \cdot T (μ (t_{k})) = l (t) \cdot T (μ (t_{k})) .$

Proof..

September 2021
Peter Pagin

Now consider a minimum-length derivation of $μ (t_{k + 1})$ . There is some minimum-length derivation that begins $μ (t_{k + 1}) \to F (t_{k})$ whence $T (μ (t_{k +_{1}})) = 1 + T (F (t_{k})) ⩾ k \cdot T (μ (t_{k}))$ whence $T (μ (t_{n})) ⩾ (n - 1)!$ .