<figure><img src="image_1.png" /></figure>

HAL
open science

# Bottom-up computation of recursive programs

Gérard Berry

► To cite this version:

Gérard Berry. Bottom-up computation of recursive programs. [Research Report] IRIA-RR-133, IRIA. 1975, pp.59. hal-04716091

HAL Id: hal-04716091

https://inria.hal.science/hal-04716091v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
RIA
laboria

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_3.png" /></figure>

Bottom-up computation
of recursive programs

Géraud
G. Berry

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

Rapport de Recherche n° 133
Septembre 1975
BOTTOM-UP COMPUTATION OF RECURSIVE PROGRAMS

G. Berry

Ecole Nationale Supérieure des Mines, Paris
IRIA/LABORIA

Résumé.

Le but de cet article est de définir et d'étudier un mécanisme d'implantation des programmes récursifs, que nous appelons mécanisme de production, par opposition au mécanisme habituel de récursion. Le principe en est de calculer "par le bas", partant des valeurs de base données par les conditions d'arrêt, en direction du résultat désiré. Nous utilisons pour cela une traduction d'un programme récursif en un système d'équations dans un espace d'ensembles. Nous introduisons des conditions de déterminisme, impliquant l'unicité de l'ensemble des valeurs intermédiaires nécessaires à un calcul. Nous étudions la structure de cet ensemble. En application, nous montrons l'optimalité d'une implantation du programme d'Ackermann (algorithme de Rice).

Abstract.

In this paper, we define and study a mechanism for the implementation of recursive programs : we call it production mechanism by opposition to the usual recursion mechanism. It computes bottom-up, starting from the basic values given by halting conditions, and generates intermediate values leading to the result. We use for this purpose a translation of a recursive program into a system of equations in a space of sets. We introduce determinism conditions providing the uniqueness of the set of intermediate values ; we study the structure of this set. As an application, we show the optimality of an implementation of Ackermann program (Rice's algorithm).
# INTRODUCTION

When dealing with computer programs, one usually makes a distinction between flow-charts and recursive programs. We restrict here our attention to the latter ones. Their generality has been showed by Luckham, Park and Paterson [13].

Properties of programs have to be expressed in some mathematical framework. Among the possible approaches, one of the most widely used is Scott's fixpoint semantics: a recursive program is viewed as a set of equations in some function space. The function it computes is defined as the least fixpoint of the (monotonic) functional determined by the equations.

This approach has been showed suitable for studying various properties of programs, such as correctness, termination, equivalence (see Manna-Vuillemin [3], Milner [4], etc...). It has also been used by Vuillemin [11,12] to study the time complexity of the computations, as defined by the number of substitutions.

On the other hand, in order to develop the "fixpoint induction" technique, Park [7] presents a translation of a recursive program into a system of equations on a space of subsets of a domain. These subsets represent in fact graphs of functions, and the formalism is essentially equivalent to Scott's one.

In this paper, we want to show that working with graphs is suited to formalise a *production process*, which is a dual to the usual recursion process. The recursion mechanism can be considered as defining top-down computations, which start from the given argument to reach the halting conditions. On the other hand, certain "good" iterative programs compute just in the opposite way: they start from the basic values given by the halting conditions, and then compute intermediate values of the function towards the desired result. These programs generally avoid computing several times intermediate values, and use simple storage management. Well-known examples are iterative programs for computing
Fibonacci numbers, integer partitions, or Ackermann function (see Rice [8]).

The formalism presented here allows us to define and handle the precise set of values necessary to compute the result of a program for a given argument. The basic objects we manipulate consist in argument-value pairs instead of terms or functions.

In the first section, we present a way of translating a recursive program into a predicate defining a monotonic production function on graphs; we prove the correctness of the mechanism.

A class of production functions of special interest is the class of those functions for which the set of intermediate values is unambiguously determined at each step of a computation: we call them *deterministic production functions*. The second section is devoted to a study of interpretations which give to a program such a production function.

In the third section, we study properties of production functions, independently of the programming aspects. We weaken the determinism condition, and consider a *quasi-determinism condition*, which corresponds to the uniqueness of the whole set of intermediate values. In this scope, we introduce the notion of *self-reproducing set* which will allow us to describe in a precise way *bottom-up computations* and the *quasi-determinism condition*. We study the structure of these sets.

In the last section, we define the notions of *time and space optimality* of bottom-up computations. As an example, we show that Rice's algorithm [8] realises an optimal implementation of Ackermann program.

Moreover, although this aspect is not developed in the paper, this example should convince the reader that our approach is adequate to a study of space complexity. This last point strengthens the parallel that one guesses between our formalism and that of Jean Vuillemin.
NOTATIONS

Given a set $D$, we denote by $P(D)$ the powerset of $D$.

The symbol $\subseteq$ will denote:

- when used with lower case letters, Scott's relation "less defined than";

- when used with upper case letters, the usual set inclusion.

A n-tuple $(x_1, x_2, ..., x_n)$ is denoted by $\overline{x}$; its i-th component is denoted by $x_i$ or $(\overline{x})_i$.

The cardinality of a finite set $X$ is denoted by $card(X)$.
# I Translation of a recursive program into a monotonic production function.

The production mechanism can be illustrated by the Fibonacci program :

$$ \text{Fib}(n) = \text{if } n=0 \text{ v } n=1 \text{ then } 1 \text{ else } \text{Fib}(n-1) + \text{Fib}(n-2) $$

Given a subset X of the graph of Fib, we can use the program to generate new points in the graph. For instance, if X contains the two points < 4, fib(4) = 5 > and < 5, fib(5) = 8 >, we can generate the new point < 6, fib(6) = 5+8 = 13 >. More precisely, the set produced by X in this example can be defined by :

$$ \phi(X) = \{ (n,z) \in \mathbb{N}^2 | \exists y_1, y_2 ( \text{ if } n=0 \text{ v } n=1 \text{ then } z=1 \text{ else } z = y_1 + y_2 ) \\ \wedge (n-1, y_1) \in X \wedge (n-2, y_2) \in X \} $$

The purpose of this section is to formalise a translation of a recursive program into a predicate defining the production function $\phi$. This translation is such that the least fixpoint of $\phi$ represents the graph of the function computed by the program. It extends Park's translation, which corresponds to the call-by-value rule.

## I-1 Discrete domains and recursive programs

**Definitions** : A discrete domain is a set D containing a distinguished element $\perp$, the undefined element, and ordered by the relation $x \prec y$ iff $x = \perp$ or $y = \perp$.

The relation $\subseteq$ extends to $D^P$ :

$$ \forall \bar{x}, \bar{x}' \in D^P \quad \bar{x} \subseteq \bar{x}' \quad \Leftrightarrow \quad \forall i \in \{1, 2, \dots, p\} \quad x_i \subseteq x_i' $$

In $D^P$, two elements $\bar{x}$ and $\bar{x}'$ always have a greatest lower bound (i.e. $\bar{x} \wedge \bar{x}'$ defined by $(\bar{x} \wedge \bar{x}')_i = \perp$ if $x_i \neq x_i', (\bar{x} \wedge \bar{x}')_i = x_i$ if $x_i = x_i'$.

If two elements $\bar{x}$ and $\bar{x}'$ have a least upper bound (i.e. $\bar{x} \vee \bar{x}'$, they are said to be joinable (abbreviated $\bar{x} \upharpoonright \bar{x}'$)).
A function $f : D^p \to D$ is *monotonic* (increasing), iff for all $\bar{x}, \bar{x}' \in D^p$, $\bar{x} \preceq \bar{x}' \Rightarrow f(\bar{x}) \preceq f(\bar{x}')$.

The set $\Delta^p$ of the monotonic functions from $D^p$ to $D$ is ordered by the relation $\preceq$ defined by :

$$ \forall f,g \in \Delta^p : f \leq g \Leftrightarrow \forall \bar{x} \in D^p : f(\bar{x}) \leq g(\bar{x}). $$

For each $\bar{x}$, either $f(\bar{x})$ is undefined, or $f(\bar{x}) = g(\bar{x})$.

The structure $(\Delta^n, \leq)$ is a continuous lattice (cf Scott [9]). We also denote by $\perp$ the constant mappings to $\perp$.

(I-1-1) **proposition** : Let $\bar{x}, \bar{x}' \in D^p$. Then $\bar{x}$ and $\bar{x}'$ are joinable iff for all $i \in I^p$, $x_i \neq \perp$ and $x_i' \neq \perp$ imply $x_i = x_i'$. If $f \in \Delta^p$, if $\bar{x}' \uparrow \bar{x}$, if $f(\bar{x}) \neq \perp$ and $f(\bar{x}') \neq \perp$, then $f(\bar{x}) = f(\bar{x}')$.

**Proof** : The first part directly follows from the definition.

Let $\bar{x} \uparrow \bar{x}'$, $f(\bar{x}) \neq \perp$, $f(\bar{x}') \neq \perp$. Then $\bar{x}$ and $\bar{x}'$ have a $1 \times \mathbf{b}$ $\bar{x} \vee \bar{x}'$. Since $f$ is monotonic, $f(\bar{x}) = f(\bar{x} \vee \bar{x}')$ and $f(\bar{x}') = f(\bar{x} \vee \bar{x}')$. $\square$

Let us now define the recursive program schemes.

The basic alphabet is divided into a set of connectors, a set of variables $V = \{x_1, x_2, \dots, x_k\}$, a set of unknown function symbols $F = \{F_1, F_2, \dots, F_m\}$. To each function symbol $f$ is associated an integer $\rho(s)$, the arity of $s$.

**Definitions** : The set of terms is the language generated by the algebraic grammar :

$$ \xi = \sum_{v \in V} v + \sum_{b \in B} h(\frac{\xi, \xi, \dots, \xi}{\rho(b)}) + \sum_{f \in F} f(\frac{\xi, \xi, \dots, \xi}{\rho(f)}) $$

Given a word $w$, we denote by $w[a_1/b_1, a_2/b_2, \dots, a_n/b_n]$ the word obtained by substituting in $w$ every occurrence of the symbol $b_1$ (resp. $b_2, \dots, b_n$) by the symbol $a_1$ (resp. $a_2, \dots, a_n$).
A recursive program scheme Σ is a set of equations

$$ \sum_i \begin{cases} f_i(x_1, x_2, \dots, x_p(f_i)) = \tau_i \\ i = 0, 1, \dots, N \end{cases} $$

where the $τ_i$ are terms only containing variables in $x_1, x_2, \dots, x_p(f_i)$, basic function symbols and unknown function symbols in $f_1, f_2, \dots, f_N$.

A discrete interpretation I is given by:

1) a discrete domain $D_I$

2) for each basic function symbol $b$, a monotonic function $I(b) \in \Delta^b$.

A recursive program scheme-discrete interpretation pair is called a recursive program.

(I-1-2) **Theorem**: A recursive program $(\Sigma, I)$ defines a functional $\phi$ from $\Delta^\rho(f_1) \times \Delta^\rho(f_2) \times \dots \times \Delta^\rho(f_N)$ to itself: $\phi(g_1, g_2, \dots, g_N)$ is the n-tuple of functions defined by the terms $\tau_i[g_1/f_1, g_2/f_2, \dots, g_N/f_N]$. This functional is monotonic and continuous with respect to the ordering $\leq$, and has a least fixpoint $Y(\Sigma, I)$, called the solution of the equation.

This fixpoint is the limit of the Kleene sequence
$K_P = \langle k_1^P, k_2^P, \dots, k_N^P \rangle$ such that:

$$ k_i^0 = \perp \text{ for } i \in \{1, 2, \dots, N\} $$

$$ k_i^{P+1} = \lambda x_1, x_2, \dots, x_p(f_i) \circ \tau_i \left[ k_1^P/f_1, k_2^P/f_2, \dots, k_N^P/f_N \right] $$

The sequence $K_P$ satisfies $K_0 \subseteq K_1 \subseteq K_2 \subseteq \dots \subseteq K_P \subseteq \dots \subseteq Y(\Sigma, I)$.

A proof may be found in Vuillemin [12] or Nivat [6].
**Abbreviations** : For simplicity, we abbreviate

$$ \tau_i[g_1/f_1, g_2/f_2, \dots, g_N/f_N, Y_1/x_1, Y_2/x_2, \dots, Y_\rho(f_i)/x_\rho(f_i)] $$
by $\tau_i(g_1, g_2, \dots, g_N) (Y_1, Y_2, \dots, Y_\rho(f_i))$

In the case of single equation programs, we denote by $\tau^m(\perp)$ the functions of Kleene's sequence. So $\tau^0(\perp) = \perp$, and $\tau^{m+1}(\perp)$ is the function computed by the term $\tau(\tau^m(\perp))$.

## I-2 Reduction to one single equation

In the translation process, we shall prefer to manipulate programs containing a single equation. Given a program, we construct another single equation program performing the same computations, by giving to a generic function the name of the function to be computed as an argument.

Let $(\Sigma, I)$ be a recursive program. We assume $D_I \cap F = \emptyset$. Let $\rho$ be the maximal arity of the $f_i$.

We define a transformation $T$ on terms by :

1. $T(v) = v$ if $v \in V$

2. $T(b(t_1, t_2, \dots, t_\rho(h))) = b(T(t_1), T(t_2), \dots, T(t_\rho(h)))$

3. $T(f_1(t_1, t_2, \dots, t_\rho(f_i))) = h(f_i, T(t_1), T(t_2), \dots, T(t_\rho(f_i)), \underbrace{\perp, \perp, \dots, \perp}_{\rho-\rho(f_i)})$

with $\rho-\rho(f_i)$ symbols to complete the argument list.

We now construct the following program $(\Sigma', I')$ :

1. $V' = V \cup \{f\}$ where $f$ is a new symbol.

2. $B' = B \cup F \cup \{\perp, \text{choice}\}, \perp$ and the elements of $F$ being considered 0-ary (constants) and choice $N+1$-ary.

3. $F' = \{h\}$ where $h$ is a new symbol, $\rho+1$-ary.

4. The program scheme $\Sigma'$ is defined by :

$$ \Sigma' : h(f, x_1, x_2, \dots, x_\rho) = \tau = \text{choice} (f, T(\tau_1), T(\tau_2), \dots, T(\tau_N)) $$
5. The interpretation I' is defined by :

5a. $D_I' = D_I \cup F$

5b. $I'(b) (d_1, d_2, \dots, d_p(b)) = I(b) (d_1, d_2, \dots, d_p(b))$ \\
for $b \in B$ and $d_1, d_2, \dots, d_p(b) \in D$ \\
$I'(b) (d_1, d_2, \dots, d_p(b)) = \perp$ otherwise

5c. $I'(\perp) = \perp$

5d. $I'(\text{choice} (f_1, d_1, d_2, \dots, d_p)) = d_i$

(I-2-1) **proposition** : Let < $k_1^P, k_2^P, \dots, k_N^P$ > and $g^P$ be the Kleene sequences of (Σ,I) and (Σ',I'), let ($K_1, K_2, \dots, K_N$) and g be the solutions of (Σ,I) and (Σ',I'). Then :

$$
a) \forall p \in \mathbb{N} \quad \underbrace{\lambda \bar{x} . k_i^p(\bar{x}) = \lambda \bar{x} . g^p(f_i, \bar{x}, \bot, \bot, \dots, \bot)}_{\rho \to \rho(f_i)}
$$

$$
b) \quad \lambda \bar{x} . K_i(\bar{x}) = \underbrace{\lambda \bar{x} . g(f_i, \bar{x}, \bot, \bot, \dots, \bot)}_{\rho \to \rho(f_i)}
$$

proof : a) by induction on p :

- Obvious for p=0 (all functions are ⊥).

- Assume the property true for p-1. Then :

$$
\begin{align*}
\underbrace{\lambda \bar{x} . g^P(f_i, \bar{x}, \bot, \bot, \dots, \bot)}_{\rho \to \rho(f_i)} &= \lambda \bar{x} . \underset{\rho=\rho(f_i)}{\text{choice}} (f_i, T(\tau_1) (g^{\Gamma-1}) (\bar{x}, \bot, \bot, \dots, \bot), \\
&\quad T(\tau_2) (g^{\Gamma-1}) (\bar{x}, \bot, \bot, \dots, \bot), \dots, T(\tau_N) (g^{\Gamma-1}) (\bar{x}, \bot, \bot, \dots, \bot)) \\
&= \lambda \bar{x} . T(\tau_i) (g^{\Gamma-1}) (\bar{x}, \bot, \bot, \dots, \bot).
\end{align*}
$$

The induction hypothesis implies that we can replace in $T(\tau_i)$
every subterm of the form $g^{p-1}(f_j, \bar{\alpha}, \bot, \bot, \dots, \bot)$ by $k_j^{p-1}(\bar{\alpha})$. We can therefore
replace the term $T(\tau_i)$ $(g^{\Gamma-1})(\bar{x}, \bot, \bot, \dots, \bot)$ by the term
$\tau_i (k_1^{\Gamma-1}, k_2^{\Gamma-1}, \dots, k_N^{\Gamma-1}) (\bar{x}, \bot, \bot, \dots, \bot)$, which defines the function $k_i^\Gamma$.

b) Follows from a. by continuity. []
**Example :**

$$ \sum_{i} \begin{cases} f_1(x_1, x_2) = f_1(x_1, f_2(x_2)) \\ f_2(x_1) = f_2(x_1, f_2(x_2)) \end{cases} $$

$$ \Sigma' : h(f, x_1, x_2) = \textit{choice} (f, h(f_1, x_1, h(f_2, x_2, \perp)), h(h(f_1, x_1, x_2))) $$

## I-3 Monotonic functions over subsets

**Definitions :** $\Phi : P(A) \to P(A)$ is *monotonic* (increasing) iff :

$$ \forall X, Y \subseteq A \quad X \subseteq Y \Rightarrow \Phi(X) \subseteq \Phi(Y) $$

- $X \subseteq A$ $\Phi$-produces $x$ iff $x \in \Phi(X)$

- $X$ is a minimal $\Phi$-producer of $x$ iff $X$ produces $x$ and no proper subset of $X$ produces $x$.

- $X$ is a fixpoint of $\Phi$ iff $X = \Phi(X)$

- $\Phi$ is continuous iff for every increasing sequence

$$ X_0 \subseteq X_1 \subseteq \dots \subseteq X_n \subseteq \dots, \quad \Phi(\bigcup_{i \in N} X_i) = \bigcup_{i \in N} \Phi(X_i) $$

(I-3-1)

**Theorem :** (Knaster-Tarski) Every monotonic function $\Phi : P(A) \to P(A)$ has a least fixpoint $Y(\Phi)$. If $\Phi$ is continuous, then $Y(\Phi)$ is the limit of the Kleene sequence $\Phi(\emptyset), \Phi^2(\emptyset), \dots, \Phi^n(\emptyset), \dots$

*Proof given in Park [7].*

(I-3-2)

**proposition :** $\Phi$ is continuous iff for every point $x$ of $\Phi(A)$, all minimal producers of $x$ are finite.

**Proof :** Assume $\Phi$ continuous. Let $x \in \Phi(A)$ have an infinite minimal producer $P$.

Let $P' = \{P_0, P_1, \dots, P_n\}$ be a denumerable subset of $P$, let $P'' = P-P'$. The sequence $P_n = P'' \cup \{P_0, P_1, \dots, P_n\}$ is such that for every $n$ $P_n \neq P$ and $\bigcup_{n \in N} P_n = P$.
Then $x \in \Phi(\bigcup_{n \in N} P_n)$, and $x \notin \Phi(P_n)$ for all $n \in N$, which is impossible.

Assume now that all minimal producers are finite, let $X_1, \dots, X_n, \dots$ be an increasing sequence. By monotonicity, $\phi(U X_n) \supseteq U \phi(X_n)$. Assume $x \in \phi(U X_n)$. Then $U X_n$ contains a minimal producer $P$ of $x$. Since $P$ is finite, $P \subseteq X_n$ holds for some $n$, and $x \in U \phi(X_n)$.

## I-4 Translation of a recursive program into a monotonic predicate.

According to I-2, we only translate single equation programs. Let $\Sigma : f(x_1,x_2,\dots,x_\rho) = \tau(f)(x_1,x_2,\dots,x_\rho)$ be a recursive scheme with $n$ occurrences of $f$ in $\tau$. We first label these occurrences by the integers $1,2,\dots,n$, denoting then by $f^1, f^2, \dots, f^n$.

**Definitions**: We consider a set $Y = \{y_1, y_2, \dots, y_n\}$ of bound variable symbols, a result variable symbol $z$, and a set variable symbol $X$.

We denote by $T^i = f^i(t_1^i, t_2^i, \dots, t_\rho^i)$ the subterm of $\tau$ corresponding to the occurrence $i$ of $f$, and by $T^0$ the term $\tau$ itself.

We define a *transformation* $T$ on labelled terms which consists in
replacing a subterm $f^i(t_1^i, t_2^i, \dots, t_n^i)$ by the bound variable $y_i$ :

a) $T(v) = v$ if $v$ is a variable symbol.

a) $T(b(t_1, t_2, \dots, t_k)) = b(T(t_1), \dots, T(t_k))$
if $b$ is a basic function symbol.

c) $T(f^i(t_1^i, t_2^i, \dots, t_p^i)) = y_i$.

If $T$ is a term, $T(t)$ only contains basic function symbols and variable symbols in $\bar{x}$ or $\bar{y}$.

For every integer $i \in \{0, 1, \dots, n\}$, $I_i$ will denote the set of
labels of bound variable occurring in one of the terms $T(t_i^i)$ ($\bar{x}, \bar{y}$) for $1 \le j \le p$.
By construction, if $i \neq j$ implies $I_i \cap I_j = \emptyset$, and we have

$\bigcup_{i \in \{0,1,...,n\}} \tilde{I}_i = \{1,2,...,n\}$. For every $k \in \{1,2,...,n\}$, there exists a unique $i$ such that $k \in I_i$.

For the innermost occurrences of $f$, $I_i = \emptyset$.

The nesting level $nl(i)$ is defined by $nl(i)=0$ iff $I_i = \emptyset$, $nl(i) = 1 + \max_{j \in I_i} nl(j)$ otherwise, so that $nl(i)$ is the maximal number of nested occurrences of $f$ in the term $T^i$.

Let us now define the translated predicate $P_\Sigma$ :

**Definitions**: For every $i \in \{1,2,...,n\}$, the elementary predicate $P_i$ is
defined by :

$$
P_i = [ (T(t_1^i) (\bar{y}, \bar{y}), T(t_2^i) (\bar{x}, \bar{y}), \dots, T(t_n^i) (\bar{x}, \bar{y}), y_i) \in X \lor y_i = \perp ]
$$

The predicate $P_\Sigma$ associated to $\Sigma$ is defined by :

$$
P_{\Sigma}(x_1, x_2, \dots, x_{c(X)}, X) = \exists y_1 y_2 \dots y_n (z \neq \perp) \wedge (z = \tau(\tau^0)) \wedge p_1 \wedge p_2 \wedge \dots \wedge p_n
$$

\textbf{Example :} $\Sigma : f(x_1,x_2) = a(f^1(b(x_1,x_2), c(f^2(x_2,x_1))))$

$$
P_{\Sigma}(x_1, x_2, z, X) = \exists y_1, y_2 \quad z \neq \perp \wedge z = a(y_1) \wedge [(b(x_1, x_2), c(y_2), y_1) \in X \lor y_1 = \perp] \\
\qquad \wedge [(x_2, x_1, y_2) \in X \lor y_2 = \perp]]
$$

We now use $P_\Sigma$ to define the production function $\Phi_\Sigma$ :

**Definition**: Let $\Sigma$ be a single-equation program scheme, let $I$ be a discrete interpretation. The production function $\Phi_{(\Sigma,I)} : \Pi_I^{\rho+1} \to \Pi_I^{\rho+1}$ associated to the program $(\Sigma,I)$ is defined by :

$$
\Phi_{(\Sigma, I)}(X) = \{ (x_1, x_2, \dots, x_\rho, z) \mid P_{\Sigma}(x_1, x_2, \dots, x_\rho, z, X) \}
$$

We abbreviate $P_\Sigma$ and $\Phi_{(\Sigma,I)}$ by $P$ and $\Phi$ when no confusion arises.

**Remark**: If we take out the $y_i = \perp$, the translation is essentially equivalent to the one given in Park [7].
(I-4-1) **proposition** $\Phi_{(\Sigma, I)}$ is monotonic and continuous

**Proof** : The elementary predicates are monatomic, and the definition of $\Phi$
involves no negation : $\Phi$ is monotonic.

Since the number of elementary predicates is finite, $\Phi$ is
also continuous (I-3-2).

I

I-5 Correctness of the translation

We first need two definitions :

**Definition** : Let $b$ be a function from $I^F$ to D. The defined part of the graph of $b$, denoted dpg(b), is the set of $p+1$-tuples $(x_1, x_2, \dots, x_P, z)$ such that $z \neq I$ and $z=b(x_1, x_2, \dots, x_P)$.

**Definition** : Let (Σ, I) be a recursive program. A n-tuple $\bar{\alpha}=(\alpha_1, \alpha_2, ..., \alpha_n) \in D_I^n$ is admissible for $(\bar{x}, z, X)$ iff it satisfies $z=T(T^0) \wedge P_1 \wedge P_2 \wedge ... \wedge P_n$ (i.e. $P_Σ$ without the quantifiers).

Then $(\bar{x},z) \in \Phi(X)$ iff there exists an admissible n-tuple for $(\bar{x},z,X)$.

We can now prove the correctness of the translation.

(I-5-1) **Theorem** : Let (Σ, I) be a recursive program. Let h be monotonic function
from I$^F$ to D, let H denote dpg(h). Then :

$$
(\bar{x}, z) \in \Phi_{(\Sigma, I)}(H) \iff z \neq I \wedge z = \tau(h)(\bar{x}), \text{ or equivalent } \Phi_{(\Sigma, I)}(H) = \text{dpg}(\tau(h))
$$

If a $n$-tuple $\bar{\alpha}$ is admissible for $(\bar{x}, z, H)$, then :

$$
\forall i \in \{1, 2, \dots, n\} \quad \alpha_i \subseteq T^i(h)(\bar{x}).
$$

**Proof** : 1) dpg(τ(h)) ⊆ Φ(H)

Assume $z \neq I \wedge z=\tau(h)(\bar{x})$. If $\bar{\alpha}$ is defined by $\alpha_i=T^i(h)(\bar{x})$ for all $i$, then by construction of $P_\Sigma$, $\bar{\alpha}$ is admissible for $(\bar{x},z,H)$.
$$ \zeta) \Phi(H) \subseteq \text{dpg}(\tau(h)) $$

Let $(\bar{x},z) \in \Phi(H)$; then $z \neq \perp$. Let $\bar{\alpha}$ be admissible for $(\bar{x},z,H)$. We show by induction on the nesting levels that for all $i$, $\alpha_i \subseteq T^i(h)(\bar{x})$.

2a) Case $n1(i)=0$. The terms $T(t_j^i)(\bar{x},\bar{\alpha})$ in $p_i$ only contain basic functions and variables of $\bar{x}$.

Hence $T(t_j^i)(\bar{x},\bar{\alpha}) = t_j^i(\bar{x})$. By construction of $p_i$, either $\alpha_i=\perp$, or $(t_1^i(\bar{x}), t_2^i(\bar{x}), \dots, t_\rho^i(\bar{x}), \alpha_i) \in H$, which means $\alpha_i=h(t_1^i(\bar{x}), t_2^i(\bar{x}), \dots, t_\rho^i(\bar{x}))=T^i(h)(\bar{x})$.

2b) Assume the property true for all labels of nesting level less than $k$, and let $i$ be of nesting level $k$. The terms $T(t_j^i)(\bar{x},\bar{\alpha})$ only contain basic functions, variables in $\bar{x}$ and bound variables of nesting level less than $k$.

The induction hypothesis and the monotonicity of the basic functions imply :

$$ \forall j \ 1 \leq j \leq \rho \quad T(t_j^i)(\bar{x}, \bar{\alpha}) \subseteq t_j^i(\bar{x}) $$

If $\alpha_i$ is defined, it is such that

$$ (T(t_1^i(\bar{x},\bar{\alpha})), T(t_2^i(\bar{x},\bar{\alpha})), \dots, T(t_\rho^i(\bar{x},\bar{\alpha}), \alpha_i)) \in H $$

Then by monotonicity of $h$: $(t_1^i(\bar{x}), t_2^i(\bar{x}), \dots, t_\rho^i(\bar{x}), \alpha_i) \in H$

$$ \text{This means } \alpha_i=h(t_1^i(\bar{x}), t_2^i(\bar{x}), \dots, t_\rho^i(\bar{x})) = T^i(h)(\bar{x}) $$

The same argument applies to $z$: since $z \neq \perp$ and $z=T(\tau)(\bar{x},\bar{\alpha})$, we have $z=\tau(h)(\bar{x},\bar{\alpha})$.

□

(I-5-2) **Corollary**: Let $(\Sigma,I)$ be a recursive program. Then for every $m \geq 0$, $\phi^m(\emptyset) = \text{dpg}(\tau^m(\perp))$ ; $Y(\phi) = \text{dpg}(Y(\Sigma,I))$.

If $(\bar{x},z) \in \phi^m(\emptyset)$, and if $\bar{\alpha}$ is admissible for $(\bar{x},z,\phi^{m-1}(\emptyset))$, then for all $i \in \{1,2,\dots,n\}$:

$$ \alpha_i \subseteq T^i(\tau^{m-1}(\perp))(\bar{x}) \subseteq T^i(Y(\Sigma,I))(\bar{x}) $$
**Proof**: First part: by induction on $m$. For $m=0$, $\phi^0(\emptyset)=\emptyset$, $\tau^0(\perp)=\perp$, $\emptyset=dpg(\perp)$.

Assuming $\phi^m(\emptyset) = dpg(\tau^m(\perp))$,
(I-5-1) implies $\phi(\phi^m(\emptyset)) = dpg(\tau(\tau^m(\perp)))$, which means $\phi^{m+1}(\emptyset) = dpg(\tau^{m+1}(\perp))$.
Now $Y(\phi)=dpg(Y(\Sigma,I))$ follows by continuity.

second part : the first inequality directly follows from (I-5-1). The
second one is implied by $\tau^m(\perp) \subseteq Y(\Sigma, I)$.

□

I-6 **Extension of the production function.**

Let $(\bar{x},z) \in \phi^m(\emptyset)$. By monotonicity of $\tau^m(\perp)$, we know that for all $\bar{x}' \supseteq \bar{x}$, $(\bar{x}',z) \in \phi^m(\emptyset)$. It may however happen that for some $X$, $(\bar{x},z) \in \phi(X)$ and $(\bar{x}',z) \notin \phi(X)$. For instance :

$\Sigma : f(x_1,x_2) = \begin{array}{ll} 0 & \text{if } x=0 \\ \infty & \text{else} \end{array} \text{ f}(x_1-1,x_2)$

Let $X = \{(0,\perp,0)\}$. Then $(1,\perp,0) \in \phi(X)$ and $(1,n,0) \notin \phi(X)$ for $n \in \mathbb{N}$. We now extend $\phi$ to a more powerful production function $\Psi$.

**Definitions**: Let $D$ be a discrete domain, let $X \subseteq D^P$. The set $\hat{X}$ is defined by $\hat{X} = \{\bar{x}' \mid x \in D^P \mid \exists \bar{x} \in X \ \bar{x} \subseteq \bar{x}'\}$. The extended production function $\Psi$ is defined by : $\forall X \subseteq D^{P+1} \quad \Psi(X) = \phi(\hat{X})$

(I-6-1) **Proposition** : 1. $\Psi$ is monotonic and continuous

$$
2. \forall m \in \mathbb{N} \quad \psi^m(\emptyset) = \phi^m(\emptyset) \ ; \ \Psi(\psi) = \Psi(\phi)
$$

**proof**: 1. Clearly $X \subseteq Y$ implies $\hat{X} \subseteq \hat{Y}$; $\Psi$ is monotonic.

Let $(\bar{x},z) \in \Psi(D^{P+1})$, let $X$ $\Psi$-produce $(\bar{x},z)$.

Then $(\bar{x},z) \in \phi(\hat{X})$. Since $\phi$ is continuous, $\hat{X}$ contains a finite
$\phi$-producer $Y$ of $(\bar{x},z)$ (cf. I-3-2). Let $Y' \subseteq X$ be defined by

$$
Y' = \{(\bar{\alpha}, \beta) \in X \mid (\exists (\bar{\gamma}, \delta) \in Y (\bar{\alpha}, \beta) \subseteq (\bar{\gamma}, \delta)) \wedge [(\bar{\alpha}', \beta') \in X \Rightarrow \sim (\alpha', \beta') \subseteq (\alpha, \beta)]\}
$$
Then $Y'$ is finite and $\psi$-produces $(\bar{x},z)$. Hence $\psi$ is continuous.

2. Since $\hat{\emptyset}=\emptyset$, $\psi(\emptyset)=\phi(\emptyset)$. Assume $\phi^m(\emptyset)=\psi^r(\emptyset)$. By monotonicity of $\tau^m(\emptyset)$, $\hat{\phi^r(\emptyset)}=\phi^m(\emptyset)$, and $\psi^{m+1}(\emptyset)=\psi(\psi^m(\emptyset))=\psi(\phi^m(\emptyset))=\phi(\phi^m(\emptyset))=\phi^{m+1}(\emptyset)$. Now $Y(\psi)=Y(\phi)$ follows by continuity. $\square$

(I-6-2) **Proposition**: If $(\bar{x},z) \in \psi(X)$ and if $\bar{x}' \supseteq \bar{x}$, then $(\bar{x}',z) \in \psi(X)$. If $\bar{\alpha}$ is admissible for $(\bar{x},z,\hat{X})$, then $\bar{\alpha}$ is also admissible for $(\bar{x}',z,\hat{X})$.

**Proof**: Let $\bar{\alpha}$ be admissible for $(\bar{x},z,\hat{X})$. Then for every $i$ such that $\alpha_i \neq 1$:
$$ (T(t_1^i)(\bar{x},\bar{\alpha}), T(t_2^i)(\bar{x},\bar{\alpha}), \dots, T(t_{\rho^i})(\bar{x},\bar{\alpha}), \alpha_i) \in \hat{X} $$

But $T(t_j^i)(\bar{x}',\bar{\alpha}) \supseteq T(t_j^i)(\bar{x},\bar{\alpha})$ implies :

$$ (T(t_1^i)(\bar{x}',\bar{\alpha}), T(t_2^i)(\bar{x}',\bar{\alpha}), \dots, T(t_{\rho^i})(\bar{x}',\bar{\alpha}), \alpha_i) \in \hat{Y} $$

Now $z=T(\mathbb{T}^\circ)(\bar{x},\bar{\alpha})$ implies $z=T(T^\circ)(\bar{x}',\bar{\alpha})$, and $\bar{\alpha}$ is admissible for $(\bar{x}',z,\hat{X})$. $\square$
## II- Deterministic production functions and stable interpretations.

Let or denote the "parallel or" function ($\perp$ or true = true or $\perp$ = true), and consider the following program, which tests if z is the sum of x and y : $\text{sum}(x,y,z) = \text{if } x=0 \land y=0 \land z=0 \text{ then } 0 \text{ else } \text{sum}(x-1,y,z-1) \text{ or } \text{sum}(x,y-1,z-1)$

Starting from x,y,z>0, there are several ways to perform the computation ; we have no reason to choose one rather than another.

Moreover, let $f_1(x)$ and $f_2(x)$ be two recursively defined boolean functions, and consider the program $f(x) = f_1(x)$ or $f_2(x)$. There is only one way of computing $f(a)$ : to perform the computations of $f_1(a)$ and $f_2(a)$ in parallel ; it is even not decidable which of the two computations is the most efficient.

In his study of time complexity of computation rules, Vuillemin [11,12] introduces a determinism condition for top-down computations : the sequentiality condition. According to production functions, we can consider the two following conditions :

- **stepwise determinism** : the set of intermediate values is unambiguously determined at each production step ; formally, every point has a unique minimal producer $mp(x)$. The whole set of intermediate values for x is then determined by transitively applying $mp$. This will be satisfied by **stable interpretations**.

- **Global determinism** : a "best" whole set of intermediate values is unambiguously determined for every argument. This weaker condition will be formalised as the *quasi-determinism condition* on production functions (section III) it seems difficult to characterise corresponding interpretations.

The following program satisfies the second condition but not the first (it is possible but useless to produce $(x,0)$ by $(x+1,0))$ : $f(x) = \text{if } x=0 \text{ then } 0 \text{ else } f(x-1) \text{ or } f(x+1)$

## II-1 Deterministic production functions.

**Definition** : A monotonic function $\phi: P(D) \to P(D)$ is *deterministic* if and only if every point x in $\phi(D)$ has a unique minimal producer $mp(x)$.
(II-1-1) **proposition** : A monotonic function $\phi$ is deterministic iff for every finite or infinite family $X_i$, $i \in I$, of subsets of $D$, $\phi(\bigcap_{i \in I} X_i) = \bigcap_{i \in I} \phi(X_i)$.

**Proof** : 1. Assume $\phi$ deterministic. Let $x \in \bigcap_{i \in I} \phi(X_i)$. Then $x \in \phi(X_i)$ for all $i$, and $\mathrm{mp}(x) \subseteq X_i$.

Hence $\mathrm{mp}(x) \subseteq \bigcap_{i \in I} X_i$, $x \in \phi(\bigcap_{i \in I} X_i)$ and $\phi(\bigcap_{i \in I} X_i) \supseteq \bigcap_{i \in I} \phi(X_i)$

The reverse inclusion results from the monotonicity of $\phi$.

2. Assume $\phi(\bigcap_{i \in I} X_i) = \bigcap_{i \in I} \phi(X_i)$. Then $\mathrm{mp}(x) = \{X | x \in \phi(X)\}$.

□

## II-2 Stable functions.

Let us define the restricted class of functions we shall use in programs :

**Definition** : Let $D$ be a discrete domain, let $b$ be a monotonic function from $D^P$ to $D$. Then $b$ is **stable by minimalisation** (or simply stable) if and only if for every joinable $\bar{x}$ and $\bar{x}'$, $b(\bar{x} \wedge \bar{x}') = b(\bar{x}) \wedge b(\bar{x}')$.

(II-2-1) **Proposition** : A function $b : D^P \to D$ is stable if and only if for every $\bar{x} \in D^P$ there exists in $D^P$ a unique minimal element $m_b(\bar{x}) \subseteq \bar{x}$ such that $b(m_b(\bar{x})) = b(\bar{x})$.

**Proof** : If $b$ is stable, then $m_b(\bar{x})$ is the g.l.b. of the set

$$ Y = \{ \bar{y} \in D^P \mid \bar{x} \rightarrow \bar{y} \wedge b(\bar{y}) = b(\bar{x}) \}. $$

Assume conversely the existence of $m_b(\bar{x})$ for every $\bar{x} \in D^P$. Let $\bar{x}$ and $\bar{x}'$ be joinable. If $b(\bar{x}) = \perp$ or $b(\bar{x}') = \perp$, then $b(\bar{x} \wedge \bar{x}') = \perp$ by monotonicity.

If $b(\bar{x}) = b(\bar{x}') \neq \perp$, then $b(\bar{x} \vee \bar{x}') = b(\bar{x}) = b(\bar{x}')$, and $m_b(\bar{x} \vee \bar{x}') \subseteq \bar{x}$, $m_b(\bar{x} \vee \bar{x}') \subseteq \bar{x}'$. This implies $m_b(\bar{x} \vee \bar{x}') \subseteq \bar{x} \wedge \bar{x}'$ and by monotonicity $b(\bar{x} \wedge \bar{x}') = b(m_b(\bar{x} \vee \bar{x}')) = b(\bar{x}) = b(\bar{x}')$.

□
Let us study the connection with Vuillemin's sequential functions [11,12] :

**Definition** : A monotonic function $b : D^p \to D$ is sequential if and only if for every $\bar{x} \in D^p$ there exists a critical index $i$ such that $\bar{y} \supseteq \bar{x}$ and $y_i = x_i$ imply $b(\bar{y}) = b(\bar{x})$.

**Examples** : Consider the usual if-then-else function. For $\bar{x} = (\perp, x_2, x_3)$ the critical index is 1. For $\bar{x} = (\text{true}, x_2, x_3)$ (resp. $(\text{false}, x_2, x_3)$), the critical index is 2 (resp. 3).

The choice function introduced in (I-2) is also sequential.

The class of stable functions properly extends the class of sequential functions :

(II-2-2) **proposition** : Every sequential function is stable. There exist stable functions which are not sequential

**proof** : a) Assume $b : D^p \to D$ is sequential but not stable. Let $\bar{x}^1$ and $\bar{x}^2$ be such that $\bar{x}^1 \perp \bar{x}^2$, $b(\bar{x}^1) = b(\bar{x}^2) \neq \perp$, $b(\bar{x}^1 \wedge \bar{x}^2) = \perp$.

For every index $i \in \{1,2,...,p\}$, we have either
$(\bar{x}^1 \wedge \bar{x}^2)_i = x_i^1$ or $(\bar{x}^1 \wedge \bar{x}^2)_i = x_i^2$.

In the first case $\bar{x}^1 = \bar{x}^1 \wedge \bar{x}^2$ and $f(\bar{x}^2) \supset f(\bar{x}^1 \wedge \bar{x}^2)$; in the second case $\bar{x}^2 = \bar{x}^1 \wedge \bar{x}^2$ and $f(\bar{x}^2) \supset f(\bar{x}^1 \wedge \bar{x}^2)$.

Therefore $\bar{x}^1 \wedge \bar{x}^2$ has no critical index.

b) Let $D = \{\perp,0,1,2\}$. Let $b$ be the smallest function such that:

$$b(0,1,\perp) = 0, b(1,\perp,0) = 1, b(\perp,0,1) = 2$$

One can easily check that $b$ is stable, but that $(\perp,\perp,\perp)$ has no critical index.

□
## II-3 Stable interpretations.

**Definition**: Let $\Sigma$ be a program scheme, let $I$ be a discrete interpretation. Then $I$ is stable if and only if all basic functions $I(b)$ are stable.

(II-3-1) **Lemma**: Let $I$ be a stable interpretation, let $T$ be a term only containing basic function symbols. Then $T$ defines a stable function.

**Proof**: by induction on the formation of the term :

a) $T(x_1, x_2, \dots, x_n) = x_i$ ; obvious case.

b) $T(\bar{x}) = b(T_1(\bar{x}), T_2(\bar{x}), \dots, T_m(\bar{x}))$, assuming that the terms $T_i(\bar{x})$ define stable functions.

Let $\bar{x}_1$ and $\bar{x}_2$ be joinable and such that $T(\bar{x}_1) = T(\bar{x}_2) \neq \perp$.

By (I-1-1), the two $m$-tuples $(T_1(\bar{x}^1), T_2(\bar{x}^1), \dots, T_m(\bar{x}^1))$ and $(T_1(\bar{x}^2), T_2(\bar{x}^2), \dots, T_m(\bar{x}^2))$ are joinable ; by induction hypothesis, their g.l.b. is the $m$-tuple :

$$ (T_1(\bar{x}_1^1 \wedge \bar{x}_2^1), T_2(\bar{x}_1^1 \wedge \bar{x}_2^1), \dots, T_m(\bar{x}_1^1 \wedge \bar{x}_2^1)). $$

The result follows from the stability of $b$.

□

(II-3-2) **Theorem**: Let $\Sigma$ be a recursive scheme, let $I$ be a stable interpretation. Then the functions $\tau^n(\perp)$ and the fixpoint $Y(\Sigma, I)$ are stable.

**Proof**: a) One easily shows by induction on $m$ that every function $\tau^m(\perp)$ is computed by a term only containing basic functions and the undefined function. The lemma applies.

b) Let $g$ denote $Y(\Sigma, I)$. Let $\bar{x}^1, \bar{x}^2 \in D^F$ be joinable and such that $g(\bar{x}^1) = g(\bar{x}^2) \neq \perp$.
There exists a least $m$ such that $\tau^m(\perp)(\bar{x}^1) = \tau^m(\perp)(\bar{x}^2) = g(\bar{x}^1)$.

Then $\tau^m(\perp)(\bar{x}^1 \wedge \bar{x}^2) = \tau^m(\perp)(\bar{x}^1) = \tau^m(\perp)(\bar{x}^2)$, and by monotonicity :

$$g(\bar{x}^1 \wedge \bar{x}^2) = g(\bar{x}^1) = g(\bar{x}^2).$$

We now prove a crucial property of the stable interpretations :

(II-3-3) **Theorem** : Let $\Sigma$ be a program scheme, let $I$ be a stable interpretation. If $\bar{x}$ is such that $\tau^m(\perp)(\bar{x}) = z \neq \perp$, if $\bar{x}'$ is joinable to $\bar{x}$ and such that $Y(\Sigma,I)(\bar{x}') \neq \perp$, then $\tau^m(\perp)(\bar{x}') = z$.

**Proof** : By induction on $m$. Let $g$ denote $Y(\Sigma,I)$.

1) $\underline{m} \equiv \underline{0}$. Then $z = \tau(\perp)(\bar{x}) = T^0(\bar{x},\underline{1})$ where $\underline{1}$ denotes the n-tuple $(\perp,\perp,\dots,\perp)$. Let $\bar{x}'$ be such that $\bar{x} \uparrow \bar{x}'$ and $g(\bar{x}') = z$. Since $g$ is fixpoint, $z = \tau(g)(\bar{x}') = T^0(\bar{x}',\underline{\alpha})$ with $\underline{\alpha} = \tau^i(g)(\bar{x}')$. The $\rho+n$-tuples $(\bar{x},\underline{1})$ and $(\bar{x}',\underline{\alpha})$ are joinable, and their $g.1.b.$ is $(\bar{x} \wedge \bar{x}',\underline{1})$. Therefore $T^0(\bar{x} \wedge \bar{x}',\underline{1}) = z$ and by monotonicity $T^0(\bar{x}',\underline{1}) = z$, which is equivalent to $z = \tau(\perp)(\bar{x}')$.

2) Assume the property true for $m$ :

$$\forall \bar{y}, \bar{y}' \in D^\rho (\tau^m(\perp)(\bar{y}) = z) \wedge (\bar{y} \uparrow \bar{y}') \wedge (g(\bar{y}') = z) \Longrightarrow \tau^m(\perp)(\bar{y}') = z$$

We show by induction on the formation of the terms that for every term $T(f)(\bar{x})$ we have :

$$(T(\tau^m(\perp))(\bar{x}) = z \neq \perp) \wedge (\bar{x} \uparrow \bar{x}') \wedge (g(\bar{x}') = z) \Longrightarrow T(\tau^m(\perp))(\bar{x}') = z.$$

2a) $T = x_i$ obvious case

2b) $T = b(t_1, t_2, \dots, t_k)$, where $b$ is a basic function and where the property holds for $t_1, t_2, \dots, t_k$.

Then $T(g)(\bar{x}') = b(t_1(g)(\bar{x}'), t_2(g)(\bar{x}'), \dots, t_k(g)(\bar{x}')) = b(\underline{\alpha})$

$$T(\tau^m(\perp))(\bar{x}) = b(t_1(\tau^m(\perp))(\bar{x}), t_2(\tau^m(\perp))(\bar{x}), \dots, t_k(\tau^m(\perp))(\bar{x})) = b(\underline{\beta})$$
But $\tau^m(\perp) \subseteq g$ implies $t_i(\tau^m(\perp))(\bar{x}) \subseteq t_i(g)(\bar{x})$. By (I-1-1), $\bar{\alpha}$ and $\bar{\beta}$ are joinable. Then $b(\bar{\alpha}) = b(\bar{\beta}) = b(\bar{\alpha} \wedge \bar{\beta})$.

For every index $i$ such that $(\bar{\alpha} \wedge \bar{\beta})_i$ is defined,

$(\bar{\alpha} \wedge \bar{\beta})_i = t_i(g)(\bar{x}') = t_i(\tau^m(\perp))(\bar{x}) \neq \perp$.

The induction hypothesis on the subterms applies and yields

$t_i(g)(\bar{x}') = t_i(\tau^m(\perp))(\bar{x}')$.

We deduce $(\bar{\alpha} \wedge \bar{\beta}) \subseteq (t_1(\tau^m(\perp))(\bar{x}'), t_2(\tau^m(\perp))(\bar{x}'), \dots, t_k(\tau^m(\perp))(\bar{x}'))$ and the result follows by monotonicity of $b$.

$$2c) T = f(t_1, t_2, \dots, t_p)$$

Since $g$ is a stable function, the previous argument holds, and we can replace $g$ by $\tau^m(\perp)$ in the subterms $t_i$:

$$T(g)(\bar{x}') = g(t_1(\tau^m(\perp))(\bar{x}'), t_2(\tau^m(\perp))(\bar{x}'), \dots, t_p(\tau^m(\perp))(\bar{x}')) = g(\bar{\alpha})$$

$$T(\tau^m(\perp))(\bar{x}) = \tau^m(\perp)(t_1(\tau^m(\perp))(\bar{x}), t_2(\tau^m(\perp))(\bar{x}), \dots, t_p(\tau^m(\perp))(\bar{x})) = \tau^m(\perp)(\bar{\beta})$$

But $\bar{x} \uparrow \bar{x}'$ implies $\bar{\alpha} \uparrow \bar{\beta}$; the global induction hypothesis applies and yields:

$$T(g)(\bar{x}') = \tau^m(\perp)(t_1(\tau^m(\perp))(\bar{x}'), t_2(\tau^m(\perp))(\bar{x}'), \dots, t_p(\tau^m(\perp))(\bar{x}'))$$

which is the desired result.

Let now $\bar{x}, \bar{x}' \in D^\rho$ be such that $\tau^{m+1}(\perp)(\bar{x}) = z \neq \perp, g(\bar{x}') = z$ and $\bar{x} \uparrow \bar{x}'$. Then $z$ is the value of the term $\tau(\tau^m(\perp))(\bar{x})$, and also the value of the term $\tau(g)(\bar{x}')$ (since $g$ is the fixpoint).

Applying the preceding result for terms to $\tau$, we get:

$$\tau(g)(\bar{x}') = \tau(\tau^m(\perp))(\bar{x}') = \tau^{m+1}(\perp)(\bar{x}')$$

□
This property is not true under general interpretations.
Consider for instance the program

$$f(x,y) = (x=0) \text{ or } (x=1 \land y=0) \text{ or } f(x-1,0)$$

$$\text{Here } \tau(\perp) (1,0) = true, \tau(\perp) (1,\perp) = \perp, \tau^2(\perp) (1,\perp) = true$$

Let us finally study the admissible n-tuples.

(II-3-4) Theorem : Let $\Sigma$ be a recursive scheme, let $I$ be a stable interpretation. Let $(\bar{x}, z)$ belong to $\Phi^m(\emptyset)$.

1. The set of admissible n-tuples for $(\bar{x},z,Y(\Phi))$ has a minimal element $\bar{\gamma}$ under the ordering $\subseteq$.

2. $\bar{\gamma}$ is also the minimal admissible n-tuple for $(m_g(\bar{x}),z,Y(\Phi))$

3. $\bar{\gamma}$ is admissible for $(\bar{x},z,\Phi^{m-1}(\emptyset))$

Proof : Let $g$ denote $Y(\Sigma,I)$.

1. Let $I_i$ be the set of labels of the bound variables occurring in $T(T^i)$ (cf. I-4). Let $f_i$ denote the cardinality of $I_i$, let $\beta_i = f_i^L(g)(\bar{x})$.

We construct for every $j$ a subset $J_i$ of $I_i$ satisfying the following two conditions :

a) there exists an n-tuple $\bar{\alpha}$ admissible for $(\bar{x},z,Y(\Phi))$ such that $\alpha_j = \beta_j$ if $j \in J_i$, $\alpha_i = \perp$ if $j \notin J_i$ and $j \in I_i$.

b) for every n-tuple $\bar{\alpha}$ admissible for $(\bar{x},z,Y(\Phi))$, for all $j \in J_i$, $\alpha_j = \beta_j \neq \perp$.

Let $i$ be a label. Three cases are possible :

1) $I_i = \emptyset$: then $J_i = \emptyset$ satisfies a and b.

2) For every $\bar{\alpha}$ admissible for $(\bar{x},z,Y(\Phi))$, $\alpha_i \neq \perp$.
Then $\alpha_i = \beta_i := T(T^i) (\bar{x}, \alpha_{i1}, \alpha_{i2}, \dots, \alpha_{i_l})$ with $i_j \in I_i$.

The term $T(T^i)$ is stable, and there exists a minimal $\ell_i$-tuple
$\bar{\delta} = (\delta_{i_1}, \delta_{i_2}, \dots, \delta_{i_\ell})$ such that $\alpha_i = \beta_i = T(T^i) (\bar{x}, \bar{\delta})$. We choose
for $J_i$ the set of labels such that $\delta_{i_k} \neq \perp$. Then $J_i$ satisfies
a and b.

3) There exists a $\bar{\alpha}$ admissible for $(\bar{x}, z, Y(\phi))$ such that $\alpha_i = \perp$.
Then the $n$-tuple $\bar{\delta}$ defined by $\delta_j = \alpha_j$ if $j \notin I_i$, $\delta_j = \perp$ if $j \in I_i$,
is also admissible, and $J_i = \emptyset$ satisfies a and b.

We now define $\bar{\gamma}$ by $\gamma_j = \beta_j$ if $j \in J_i$ for some $i$, $\gamma_j = \perp$ otherwise.
Then $\bar{\gamma}$ is by construction the only minimal acceptable $n$-tuple for $(\bar{x}, z, Y(\phi))$.

2. Let $\bar{x}'$ denote $m_g(\bar{x})$. Since $g(\bar{x}') = \perp \neq \perp$, there exists a $n$-tuple $\bar{\gamma}'$ admissible for $(\bar{x}', z, Y(\phi))$. By (I-6-2), $\bar{\gamma}'$ is also admissible for $(\bar{x}, z, Y(\phi))$, and hence $\bar{\gamma}' \supseteq \bar{\gamma}$. Therefore $(\bar{x}, \bar{\gamma})$ and $(\bar{x}', \bar{\gamma}')$ are joinable, with $(\bar{x}, \bar{\gamma}) \lor (\bar{x}', \bar{\gamma}') = (\bar{x}, \bar{\gamma}')$ and $(\bar{x}, \bar{\gamma}) \land (\bar{x}', \bar{\gamma}') = (\bar{x}', \bar{\gamma})$.

- The predicates $z=T(T^0)(\bar{x},\bar{\gamma})$ and $z=T(T^0)(\bar{x}',\bar{\gamma}')$ are true,
and $T(T^0)$ defines a stable function. Hence $z=T(T^0)(\bar{x}',\bar{\gamma})$ holds.

- Let $i$ be such that $\gamma_i \neq \perp$. Then $\gamma_i' = \gamma_i$ and :

$$
\xi_i = (T(t_1^i)(\bar{x}, \bar{\gamma}), T(t_2^i)(\bar{x}, \bar{\gamma}), \dots, T(t_\rho^i)(\bar{x}, \bar{\gamma}), \gamma_i) \in Y(\phi)
$$

$$
\xi_i' = (T(t_1^i)(\bar{x}', \bar{\gamma}'), T(t_2^i)(\bar{x}', \bar{\gamma}'), \dots, T(t_\rho^i)(\bar{x}', \bar{\gamma}'), \gamma_i) \in Y(\phi)
$$

Since $(\bar{x}, \bar{\gamma}) \uparrow (\bar{x}', \bar{\gamma}')$, we also have $\xi_i \uparrow \xi_i'$.

Since $g$ is stable, $\xi_i \wedge \xi_i' \in Y(\phi)$.

For each $j$ such that $(\xi_i \wedge \xi_j') \neq \perp$, we have

$$
T(t_j^i)(\bar{x}, \bar{\gamma}) = T(t_j^i)(\bar{x}', \bar{\gamma}') = T(t_j^i)(\bar{x}', \bar{\gamma}') \neq \perp
$$
The stability of $\Gamma(t_j^i)$ implies $\Gamma(t_j^i)(\bar{x}',\bar{y})=\Gamma(t_j^i)(\bar{x}',\bar{y}')$.

Therefore $\xi_i \wedge \xi'_i \subseteq \Gamma(t_1^i)(\bar{x}',\bar{y}), \Gamma(t_2^i)(\bar{x}',\bar{y}), \dots, \Gamma(t_\rho^i)(\bar{x}',\bar{y})$.

Now by (I-6-2) :

$$((\Gamma(t_1^i)(\bar{x}',\bar{y}), \Gamma(t_2^i)(\bar{x}',\bar{y}), \dots, \Gamma(t_\rho^i)(\bar{x}',\bar{y}), \gamma_i) \in Y(\Phi))$$

Finally, $\bar{y}$ satisfying $z=\Gamma(\Gamma^0)(\bar{x}',\bar{y})$ and $p_i$ for all $i$, $\bar{y}$ is admissible for $(\bar{x}',z,\Gamma(\Phi))$.

3. Assume $(\bar{x},z) \in \Phi^m(\emptyset)$. There exists $\bar{y}'$ admissible for $(\bar{x},z,\Phi^{m-1}(\emptyset))$. Since $\Phi^{m-1}(\emptyset) \subseteq Y(\Phi)$, $\bar{y}'$ is also admissible for $(\bar{x},z,\Gamma(\Phi))$ and $\bar{y}' \equiv \bar{y}$.

For each $i$ such that $\gamma_i \neq \emptyset$, we have :

$$\xi_i = (\Gamma(t_1^i)(\bar{x},\bar{y}), \Gamma(t_2^i)(\bar{x},\bar{y}), \dots, \Gamma(t_\rho^i)(\bar{x},\bar{y}), \gamma_i) \in Y(\Phi)$$

$$\xi'_i = (\Gamma(t_1^i)(\bar{x},\bar{y}'), \Gamma(t_2^i)(\bar{x},\bar{y}'), \dots, \Gamma(t_\rho^i)(\bar{x},\bar{y}'), \gamma'_i) \in \Phi^{m-1}(\emptyset)$$

($\bar{x},\bar{y}$) and ($\bar{x},\bar{y}'$) being joinable, $\xi_i$ and $\xi'_i$ are joinable, and by (II-3-3) :

$$(\Gamma(t_1^i)(\bar{x},\bar{y}), \Gamma(t_2^i)(\bar{x},\bar{y}), \dots, \Gamma(t_\rho^i)(\bar{x},\bar{y}), \gamma_i) = \xi_i \in \Phi^{m-1}(\emptyset)$$

which means that $\bar{y}$ is admissible for $(\bar{x},z,\Phi^{m-1}(\emptyset))$.

□

## II-4 Stable interpretations and $\Psi$-producers

Even under stable interpretations, the extended production function $\Psi$ is in general not deterministic. Consider the example :

$$f(x_1,x_2) = \begin{cases} 1 & \text{if } x_1=0 \text{ then } 0 \text{ else } f(x-1,f(x-2,y)) \\ 0 & \text{if } x_1=1 \end{cases}$$

Here $(2,1,0)$ has two distinct minimal $\Psi$-producers

$$P_1 = \{(1,\perp,0)\} \text{ and } P_2 = \{(1,0,0), (0,1,0)\}.$$

But $P_1$ is of smaller cardinality than $P_2$, and contains more compact information : the existence of $(1,\perp,0)$ in $\Psi(\emptyset)$ implies the
existence of (1,0,0) by monotonicity, and the point (0,1,0) is not
really useful for the computation.

To formalise this intuitive comparison between Ψ-producers,
we define the following partial preoder :

**Definition** : Let D be a discrete domain, let X,Y ≤ D<sup>F</sup>

The relation ≑ is defined by :

$$
X \sqsubseteq Y \Leftrightarrow \forall \bar{x} \in X \ \exists \bar{y} \in Y \ \bar{x} \subseteq \bar{y}
$$

We now state the main result of this section :

(II-4-1) **_Theorem_**: Let Σ be a recursive program scheme, let I be a stable interpretation.

Let $(\bar{x},z) \in Y(\Psi)$, let $MP(\bar{x},z)$ denote the family of the
minimal $\Psi$-producers of $(\bar{x},z)$.

1. The relation ≑ induces a partial ordering on MP($\bar{x}$,z).

2. MP($\bar{x},z$) has a unique minimal element under ≑, which will be called the optimal producer of ($\bar{x},z$), and denoted opt($\bar{x},z$).

3. If ($\bar{x}$,z) ∈ $\Psi^m$(Ø), then opt($\bar{x}$,z) ⊆ $\Psi^{m-1}$(Ø).

4. If $\bar{\gamma}$ is the minimal admissible n-tuple for $(\bar{x},z, Y(\Psi))$, then $\bar{\gamma}$ is admissible for $(\bar{x},z, \text{opt}(\bar{x},z))$

5. If $\bar{x}'$ is joinable to $\bar{x}$ and if $(\bar{x}',z) \in Y(\Psi)$ then $\text{opt}(\bar{x}',z) = \text{opt}(\bar{x},z)$.

6. For every φ-producer or ψ-producer P of (x,z), the cardinality of opt(x,z) is less than or equal to the cardinality of P.
**Proof :** 1. Let $P \in \mathrm{MP}(\bar{x},z)$. Then for every $p,p' \in P$, $p \subsetneq p'$ is false : otherwise $P-\{p'\}=\hat{P}$, and $P-\{p'\}$ produces $(\bar{x},z)$.

Assume now $P_1, P_2 \in \mathrm{MP}(\bar{x},z)$, $P_1 \subseteq P_2$, $P_2 \subseteq P_1$.

Let $p_1 \in P_1$. There exists $p_2 \in P_2$ such that $p_1 \subseteq p_2$, and $p'_1 \in P_1$ such that $p_2 \subseteq p'_1$. But, as seen before, $p_1 \subseteq p'_1$ implies $p_1=p'_1 = p_2$.

Hence $p_1 \in P_2$ and $p_1 \subseteq P_2$. Similarly $P_2 \subseteq P_1$. The relation is antisymmetric.

2. Let $(\bar{x},z) \in Y(\Psi)$, let $\bar{\gamma}$ be the minimal admissible n-tuple for $(\bar{x},z, Y(\Psi))$. Let $P_0$ be the set of the points :

$$ \xi_i = (T(t_1^i), (\bar{x}, \bar{\gamma}), T(t_2^i), (\bar{x}, \bar{\gamma}), \dots, T(t_{\rho_i}^i), (\bar{x}, \bar{\gamma}), \gamma_i) \text{ with } \gamma_i \neq \perp $$

Then $P_0$ produces $(\bar{x},z)$. But $Y(\Sigma,I)$ is a stable function : for every $\xi_i$ there exists a least $\eta_i \in \xi_i$ such that $\eta_i \in Y(\phi)$.

Let $\mathrm{opt}(\bar{x},z)$ be the set of the $\eta_i$.

By construction $\mathrm{opt}(\bar{x},z) \subseteq P_0$, and therefore $\mathrm{opt}(\bar{x},z) \in P_0 : \mathrm{opt}(\bar{x},z)$ produces $(\bar{x},z)$.

Assume $R \subseteq Y(\Psi)$ produces $(\bar{x},z)$, and let $\bar{\alpha}$ be admissible for $(\bar{x},z, \hat{R})$. By (II-3-4), $\bar{\alpha} \supseteq \bar{\gamma}$, and $\hat{R}$ contains at least the points :

$$ \xi_i' = (T(t_1^i), (\bar{x}, \bar{\alpha}), T(t_2^i), (\bar{x}, \bar{\alpha}), \dots, T(t_{\rho_i}^i), (\bar{x}, \bar{\alpha}), \gamma_i) \text{ with } \gamma_i \neq \perp $$

For each $i$ such that $\gamma_i \neq \perp$ we have $\xi_i \subseteq \xi_i'$ and hence $\eta_i \subseteq \xi_i'$. But $R$ contains at least one $\eta_i'$ such that $\eta_i' \subseteq \xi_i'$. Necessarily, $\eta_i \subseteq \eta_i'$, and $\mathrm{opt}(\bar{x},z) \subseteq \hat{R}$.

Since $\mathrm{opt}(\bar{x},z)$ is finite, we prove that it is a minimal $\Psi$-producer of $(\bar{x},z)$ by showing that it is a $\Psi$-producer of minimal cardinality. Assume that $U$ produces $(\bar{x},z)$ and assume $\mathrm{card}(U) < \mathrm{card}(\mathrm{opt}(\bar{x},z))$. Since $\mathrm{opt}(\bar{x},z) \subseteq U$, there exist $\eta_1, \eta_2 \in \mathrm{opt}(\bar{x},z)$ and $u \in U$ such that $\eta_1 \subseteq u$ and $\eta_2 \subseteq u$. This is impossible, since by construction $\eta_1$ and $\eta_2$ cannot be joinable.
3. Since $\bar{\gamma}$ is also admissible for $(\bar{x},z,\phi^{m-1}(\emptyset))$, we have $P_0 \subseteq \phi^{m-1}(\emptyset)$. Now (II-3-3) implies $\text{opt}(\bar{x},z) \subseteq \phi^{m-1}(\emptyset)$.

4. The n-tuple $\bar{\gamma}$ is admissible for $P_0$, and $\text{opt}(\bar{x},z) \supseteq P_0$.

4. If $\bar{x} \uparrow \bar{x}'$ and if $(\bar{x}',z) \in Y(\psi)$, then by (II-3-4) $\bar{\gamma}$ is also the minimal admissible n-tuple for $(\bar{x}',z,Y(\phi))$.

6. We showed in 2. that $\text{opt}(\bar{x},z)$ is a $\psi$-producer of minimal cardinality. But every $\phi$-producer is also a $\psi$-producer. $\square$

## II-5 Construction of the deterministic production function $\theta(\Sigma, I)$.

Our last step is to construct a new production function $\theta$ by selecting among the $\psi$-producers the optimal one. In fact $\theta$ itself will not be deterministic: we only defined the optimal producers for the points in $Y(\psi)$. However its "restriction" to its fixpoint will be deterministic: every point of $Y(\theta)$ will have a unique minimal producer included in $Y(\theta)$, and all the results of the next section will hold.

We call minimal a point $(\bar{x},z)$ such that $(\bar{x},z) \in Y(\psi)$, and $\bar{x}' \in \bar{x}$ implies $(\bar{x}',z) \notin Y(\psi)$. By construction every point of $\text{opt}(\bar{x},z)$ is minimal.

Given, for some $m, \psi^m(\emptyset)$ and $(\bar{x},z)$ in $\psi^m(\emptyset)$, we can effectively test if $(\bar{x},z)$ is minimal: we just test if $\psi^m(\emptyset)$ contains no point $(\bar{x},z)$ with $\bar{x}' \in \bar{x}$; the number of possible points is finite.

However this method fails if we only know a proper subset $X$ of $\psi^m(\emptyset)$, as will be the case in most of the actual bottom-up computations (see Chapter III).

We shall modify $\psi$ by adding to every point $(\bar{x},z)$ a flag $fl$ set to 1 iff $(\bar{x},z)$ is minimal.

**Definition**: If $X \subseteq D^{\rho+1} \times \{0,1\}$, $\mathfrak{P}(X)$ denotes the projection of $X$ on $\rho^{\rho+1}$
**Definition**: Let $(\Sigma, I)$ be a recursive program.

The production function $\Theta(\Sigma, I): P(D_I^{\rho+1} \times \{0,1\}) \to P(\Gamma_I^{\rho+1} \times \{0,1\})$ is defined by

$$ \Theta(X) = \{ (\bar{x},z,fl) \in D_I^{\rho+1} \times \{0,1\} | S(\bar{x},z,X) \wedge [fl = 1 \Leftrightarrow \forall \bar{x}' \subset \bar{x} \sim S(\bar{x}',z,X)] \} $$
with $S(\bar{x},z,X) = \exists Y \subseteq X (\forall (\bar{y},t, fly) \in Y, fly = 1) \wedge P(\bar{x},z,P(Y))$

(II-5-1) **Proposition** :

1. $\Theta$ is monotonic and continuous

2. $\forall m \in \mathbb{N} \ p(\Theta^m(\emptyset)) = \Psi^m(\emptyset) \ ; \ p(Y(\Theta)) = Y(\Psi)$

3. If $(\bar{x},z,fl) \in Y(\Theta)$, $fl = 1$ is equivalent to $(\bar{x},z)$ minimal.

4. If the interpretation $I$ is stable, then every point $(\bar{x},z,fl)$ in $Y(\Theta)$ has a unique minimal producer included in $Y(\Theta)$; this minimal producer is $\text{opt}(\bar{x},z) \times \{1\}$.

**Proof** :

1. $\Theta$ is monotonic by construction.

Assume $X$ is a $\Theta$-producer of $(\bar{x},z,fl)$. By construction of $\Theta$, $X$ contains a subset $Y$ such that every point of $Y$ has a flag 1 and such that $Y$ $\Psi$-produces $(\bar{x},z)$. Since $\Psi$ is continuous, $Y$ contains a finite subset $Y'$ $\Psi$-producing $(\bar{x},z)$. Now $Y' \times \{1\}$ is finite, included in $X$, and $\Theta$-produces $(\bar{x},z)$. Hence $\Theta$ is continuous (I-3-2).

2. 2a. **Case $X = \emptyset$** :

$$ \Theta(\emptyset) = \{ (\bar{x},z,fl) | P(\bar{x},z,\emptyset) \wedge [fl = 1 \Leftrightarrow \forall \bar{x}' \subset \bar{x} \sim P(\bar{x}',z,\emptyset)] \} $$

Then $(\bar{x},z,1) \in \Theta(\emptyset)$ is equivalent to $(\bar{x},z) \in \Psi(\emptyset)$ and $(\bar{x},z)$ minimal, and $(\bar{x},z,0) \in \Theta(\emptyset)$ is equivalent to $(\bar{x},z) \in \Psi(\emptyset)$ and $(\bar{x},z)$ not minimal.

2.b. Induction hypothesis :
2.b.1. $p(\theta^m(\emptyset)) = \psi^m(\emptyset)$

2.b.2. $(\bar{x},z,1) \in \Theta^m(\emptyset) \iff (\bar{x},z) \text{ minimal.}$

The inclusion $p(\Theta^{m+1}(\emptyset)) \subseteq \Phi^{m+1}(\emptyset)$ directly results from the construction of $\Theta$ and from 2.b.1.

Let $(\bar{x},z) \in \Phi^{m+1}(\emptyset)$. Let $A^m$ be the set of the minimal points of $\Phi^m(\emptyset)$. Clearly $A^m$ $\psi$-produces $(\bar{x},z)$. By 2.b.1. and 2.b.2., $A^m \times \{1\} \subseteq \Theta^m(\emptyset)$, and therefore $A^m$ $\Theta$-produces either $(\bar{x},z,0)$ or $(\bar{x},z,1)$.

3. By construction.

4. Every point of $\text{opt}(\bar{x},z)$ is minimal by construction ; therefore $\text{opt}(\bar{x},z) \times \{1\}$ $\Theta$-produces $(\bar{x},z,0)$ or $(\bar{x},z,1)$.

If $\Gamma$ $\Theta$-produces $(\bar{x},z,f1)$, there exists $P' \subseteq P$ such that every point of $P'$ is minimal and such that $p(P') \psi$-produces $(\bar{x},z)$. Then $P \supseteq \text{opt}(\bar{x},z)$ and $P \supseteq \text{opt}(\bar{x},z)$.

[ ]

**Remark :** It may be the case that I is not stable and $\Theta(\Sigma, I)$ is deterministic; for example : $f(x_1, x_2) = (x_1=0)$ or $(x_2=0)$

In this case $Y(\Theta) = \Theta(\emptyset)$, $\text{opt}(x_1,x_2,0) = \emptyset$.

However, given a non-stable function $b : D^P \to D^P$, we can construct a non-deterministic program just by using the sequential *if-then-else*, and constant functions:

there exist two joinables p-tuples $\alpha^{-1}$ and $\alpha^{-2}$ such that :

1. $b(\alpha^{-1}) = b(\alpha^{-2}) = z \neq \perp$

2. $\exists i, j \quad \begin{array}{l} \alpha_i^{1} \neq \perp, \alpha_i^{2} = \perp, \alpha_j^{1} = \perp, \alpha_j^{2} \neq \perp, \\ k \neq i \land k \neq j \quad \Rightarrow \quad \alpha_k^{1} = \alpha_k^{2} \end{array}$
Assume for simplicity $i=1, j=2$. Let $D_I = D \cup \{c\}$ where $c \notin D$, and consider the following program :

$$
\begin{align*}
f(x_1, x_2) &= \begin{cases} 
      \text{if } x_1 = \alpha_1^1 & \text{then } \alpha_1^1 \text{ else} \\
      \text{if } x_2 = \alpha_2^2 & \text{then } \alpha_2^2 \text{ else} \\
      \text{else } & \text{else}
      \end{cases} \\
      &\begin{array}{@{}l@{}}
      \text{h}(f(\alpha_1^1, x_2), f(x_1, \alpha_2^2), \alpha_3^1, \alpha_4^1, \dots, \alpha_p^1)
      \end{array}
\end{align*}
$$

One can check that (c,c,z,0) belongs to Θ²(Ø) and has
two distinct minimal Θ-producers {($\alpha_1^1, \perp, \alpha_1^1, 1$)} and {($c, \alpha_2^2, \alpha_2^2, 1$)}.
### III - Bottom-up computations. Quasi-deterministic production functions.

Let $D$ be an arbitrary set and $\phi$ be a monotonic function from $P(D)$ to $P(D)$. Every notion is defined with respect to $\phi$, and symbols may be prefixed by $\phi$ if necessary : $\phi$-b.u.c.s., $\phi$-s.r., $\phi$-dom...

We first formalise the notion of bottom-up computation of a point in $Y(\phi)$.

We next express the quasi-determinism condition (cf section II), and then study some properties of the quasi-deterministic functions.

Lastly, we present induction techniques based on the structure of the set of intermediate values.

Illustrations are given in diagram 1. (in annex).

### III-1 Bottom-up computation sequences; storage configuration sequences.

For defining bottom-up computations, we use as basic operation the production of a point by a subset of $D$, starting from initially empty information.

**Definition** : A bottom-up computation sequence (abbreviated b.u.c.s) is a sequence $X_0, X_1, \dots, X_n, \dots$ of subsets of $D$ such that $X_0 = \emptyset$ and $\forall n \ge 0 \ X_n \subseteq X_{n+1} \subseteq X_n \cup \phi(X_n)$.

**Definition** : A storage configuration sequence (abbreviated s.c.s) is a sequence $X_0, X_1, \dots, X_n, \dots$ of subsets of $D$ such that $X_0 = \emptyset$ and $\forall n \ge 0 \ X_{n+1} \subseteq X_n \cup \phi(X_n)$.

In a s.c.s., we are allowed to discard the intermediate values when they are no longer useful for the computation. S.c.s. correspond to actual computations, and b.u.c.s. correspond to histories of computations.

This is emphasised by the following relationship :
(III-1-1) **proposition** : Every b.u.c.s. is a s.c.s.

Let {$X_n, n \in N$} be a s.c.s. ; then the sequence $X_n = \bigcup_{csp \le n} Y_p$ is a b.u.c.s. .

**Definition** : A point $x \in D$ is computed by a s.c.s. {$X_n, n \in N$} iff $x \in \bigcup_n X_n$

**Definition** : A s.c.s. {$X_n, n \in N$} is simple iff it satisfies the following condition :

$$ \forall x \in \bigcup_n X_n \sim \exists p, q, r \in N \ x \in X_p \wedge x \notin X_q \wedge x \in X_r $$

In a simple s.c.s. we are not allowed to recompute intermediate values.

An example of simple s.c.s. (and h.u.c.s.) is Kleene's sequence : $\emptyset, \emptyset^2, \emptyset^3, \dots, \emptyset^n, \dots$.

### III-2 Self-reproducing sets. Quasi-deterministic functions.

We now introduce the basic property which will allow us to characterise the members and limits of h.u.c.s., and to express the quasi-determinism condition.

**Definition** : A subset $S$ of $D$ is self-reproducing (abbreviated s.r.) iff it satisfies $S \subseteq \Phi(S)$.

(III-2-1) **proposition** : If $S$ is s.r., so is $\Phi(S)$ ; A finite or infinite union of s.r. sets is s.r. ; For every $n \in N$, $\Phi^n(\emptyset)$ is s.r. .

**Proof** : Directly follows from the monotonicity of $\Phi$.
(III-2-2) **proposition** : Every member or limit of a b.u.c.s. is s.r. .

**Proof** : Let {$X_n, n \in N$} be a b.u.c.s. . If $n=0$, then $X_0 = \emptyset$, and $X_0 \subseteq \Phi(X_0)$.
Assume $X_n \subseteq \Phi(X_n)$. Then $X_{n+1} \subseteq X_n \cup \Phi(X_n)$ implies $X_{n+1} \subseteq \Phi(X_n)$, and
$x_n \subseteq X_{n+1}$ implies $\Phi(X_n) \subseteq \Phi(X_{n+1})$; finally $X_{n+1} \subseteq \Phi(X_{n+1})$. The limit
$\bigcup_n X_n$ is s.r. since it is a union of s.r. sets.

[ ]

The intuitive definition of the quasi-determinism condition was
the existence of a least set of necessary and sufficient intermediates
values for any given argument.

We now give the following formal definition :

**Définition** : $\Phi$ is quasi-deterministic iff every point $x \in \Phi(D)$ has a unique minimal self-reproducing producer $prod(x)$.

(III-2-3) **proposition** : A function $\Phi$ is quasi-deterministic iff for every
finite or infinite family $S_i$, $i \in I$, of s.r. sets $\Phi(\bigcap_{i \in I} S_i) = \bigcap_{i \in I} \Phi(S_i)$.

**proof** : see (II-1-1).

<figure><img src="image_4.png" /></figure>

The deterministic functions preserve intersection on arbitrary
subsets (II-1-1), and are therefore also quasi-deterministic. All the results
in this chapter are established for quasi-deterministic functions, and also
hold for deterministic functions.

We now characterise the members and limits of computation sequences :

(III-2-4) **proposition**: Let $\Phi$ be quasi-deterministic and continuous.

a) $X \subseteq Y(\Phi)$ is the limit of a b.u.c.s. iff X is s.r.

b) $X \subseteq Y(\Phi)$ is member of a b.u.c.s. iff X is s.r. and included
in $\Phi^m(\emptyset)$ for some $m \ge 0$.

**proof** : Let {$X_n, n \in N$} be a b.u.c.s. . Then $X_n$ and $\bigcup_{n \in N} X_n$ are s.r. by (III-2-2).
By induction on $n$, $X_n \subseteq \Phi^n(\emptyset)$.
Let S be s.r., let $X_n = S \cap \phi^n(\emptyset)$.

Then $X_0 = \emptyset$, $X_n \subseteq X_{n+1}$, and $\phi(X_{n-1}) = \phi(S \cap \phi^{n-1}(\emptyset))$ implies
$\phi(X_{n-1}) = \phi(S) \cap \phi^n(\emptyset) \supseteq S \cap \phi^{n}(\emptyset) = X_n$. Hence $\{X_n, n \in N\}$ is a b.u.c.s.,
which has limit S. If $S \subseteq \phi^m(\emptyset)$, then $X_m = S$, and S is also member of
the b.u.c.s. .
[]

A quasi-deterministic function may not be deterministic; however nothing can be gained by using the non determinism facilities : let $P_1$ be a minimal producer of x included in prod(x), let $P_2$ be another minimal producer such that $P_2 \not\subseteq$ prod(x). We can produce x by first producing either $P_1$ or $P_2$. Assume $\{X_n, n \in N\}$ is a b.u.c.s. such that $X_n \supseteq P_2$. Then $x \in \phi(X_n)$. But $X_n$ is s.r. and produces x : $X_n \supseteq \text{prod}(x)$ , and $X_n \supseteq P_1$ ; computing $P_2$ is simply a waste of time. Therefore prod(x) is actually the set of necessary and sufficient intermediate values we wanted to define.

**Remark** : It may be the case that prod(x) itself contains several distinct minimal producers of x.

### III-3 Producers and domains. The ordering $\prec$

<figure><img src="image_5.png" /></figure>

**Definition** : Let $\phi$ be quasi-deterministic. The domain of $x$, $dom(x)$, is the smallest s.r. set containing $x$.

(III-3-1) **proposition** : Let $\phi$ be quasi-deterministic and continuous, let $x \in Y(\phi)$,

1. $dom(x) = prod(x) \cup \{x\}$

2. $x \notin prod(x)$

3. The relation $x \prec y$ defined to hold iff $x \in dom(y)$ induces a well-founded ordering on $Y(\phi)$.

**proof** : 1. Since $dom(x)$ is s.r. and contains $x$, it produces $x$ and $dom(x) \supseteq prod(x) \cup \{x\}$. Now $\phi(prod(x) \cup \{x\}) \supseteq \phi(prod(x)) \supseteq prod(x) \cup \{x\}$. Then $prod(x) \cup \{x\}$ is s.r. and contains $x$; hence $prod(x) \cup \{x\} \supseteq dom(x)$.

2. Let $n$ be the smallest integer such that $x \in \phi^{n}(\emptyset)$.
Then $\phi^{n-1}(\emptyset)$ is s.r. and produces $x$; hence $prod(x) \subseteq \phi^{n-1}(\emptyset)$ and $x \notin prod(x)$.
3. The relation $\prec$ is obviously reflexive and transitive. It is also antisymmetric: assume $x \prec y, y \prec x$, $x \neq y$. Then $x \in \text{prod}(y)$ implies $\text{prod}(x) \subseteq \text{prod}(y)$, and $y \in \text{prod}(x)$ implies $y \in \text{prod}(y)$, contradicting 2.

If $x \in \phi^n(\emptyset)$ and $y < x$, then $\text{prod}(x) \subseteq \phi^{n-1}(\emptyset)$ and $y \in \phi^{n-1}(\emptyset)$.
The relation $\prec$ is well-founded. $\Box$

We extend the definitions of $\text{prod}(x)$ and $\text{dom}(x)$ to subsets of $D$:

**Definition 3.1**: Let $\emptyset$ be quasi-deterministic,

Let $X \subseteq Y(\emptyset)$. Then $\text{dom}(X)$ denotes the smallest s.r. set containing $X$, $\text{prod}(X)$ denotes the smallest s.r. set producing $X$.

$$ (\text{III-3-2) proposition 3.1}: \quad \text{1. } \text{dom}(X) = \bigcup_{x \in X} \text{dom}(x) $$

$$ \text{2. } \text{prod}(X) = \bigcup_{x \in X} \text{prod}(x) $$

$$ \text{3. } \text{dom}(X) = \text{prod}(X) \cup X $$

$$ \text{4. } \text{prod}(X) = \text{prod}(\text{dom}(X)) $$

$$ \text{5. S s.r. } \Leftrightarrow S = \text{dom}(S) \Leftrightarrow S \subseteq \text{prod}(S) $$

**proof**: 1, 2, 3, 5 directly follow from the definitions.

$$ \text{4. } \text{prod}(\text{dom}(X)) = \bigcup_{x \in \text{dom}(X)} \text{prod}(x) $$

But $\text{dom}(X) = X \cup \text{prod}(X)$. If $x \in \text{prod}(X)$, then $\exists x' \in X$ $x \in \text{prod}(x')$.
Hence $\text{prod}(x) \subseteq \text{prod}(x')$.

$$ \text{Therefore } \bigcup_{x \in \text{dom}(X)} \text{prod}(x) = \bigcup_{x \in X} \text{prod}(x) = \text{prod}(X) \quad \Box $$
### III-4 **Extremal points and extremal set of a s.r. set.**

A set $S$ is s.r. iff $S = \bigcup_{x \in S} \text{dom}(x)$. We note that if $y \in S$ is such that $\exists z \in S$ $y \in \text{prod}(z)$, then $S = \bigcup_{x \in S - \{y\}} \text{dom}(x)$. We are interested here in specifying a least set $E$ which characterises $S$ by $S = \text{dom}(E)$.

**Definition:** Let $\phi$ quasi-deterministic, let $S$ be s.r. A point $x \in S$ is extremal for $S$ iff $x \notin \text{prod}(S)$. A subset $E$ of $S$ is extremal for $S$ iff $S = \text{dom}(E)$ and $\forall e, e' \in E \ exists \ e < e'$. By convention, $\emptyset$ is extremal for $\emptyset$.

(III-4-1) **proposition** : A point $x$ is extremal for a s.r. set $S$ iff $S - \{x\}$ is s.r. .

**proof** : Let $x$ be extremal for $S$. Then $S - \{x\} \supseteq \text{prod}(S)$, and $\phi(S - \{x\}) \supseteq S - \{x\}$.

Assume conversely that $S - \{x\}$ is s.r. .

Then $S - \{x\} \supseteq \text{prod}(S - \{x\})$, and $S - \{x\} \supseteq \text{prod}(x)$, since $S$ produces $x$. Finally $S - \{x\} \supseteq \text{prod}(S)$ and $x \notin \text{prod}(S)$.

(III-4-2) **proposition** : Let $S$ be s.r. . Then $E \subseteq S$ is extremal for $S$ iff $S = \text{dom}(E)$ and $E \cap \text{prod}(S) = \emptyset$.

**Proof** : Clearly, if $E$ satisfies $S = \text{dom}(E)$ and $E \cap \text{prod}(S) = \emptyset$, then $E$ is extremal for $S$.

Assume conversely $E$ extremal for $S$. Assume $\exists e \in E$ such $\in \text{prod}(S)$. Then $\exists s \in S$ such $\in \text{prod}(s)$. Since $s = \text{dom}(E)$, $\exists e' \in E$ such $\in \text{dom}(e')$. Finally $\in \text{prod}(e')$, which is impossible.

(III-4-3) **proposition** : A s.r. set $S$ has at most one extremal set $\text{ext}(S)$. If it exists, $\text{ext}(S)$ is the set of extremal points of $S$. If $E' \subseteq S$ satisfies $S = \text{dom}(E')$, then $E' \supseteq \text{ext}(S)$.

**Proof** : Let $E$ be extremal for $S$. If $\notin E$, then $\notin \text{prod}(S)$ and $e$ is extremal for $S$.
Let e be extremal for S. Assume $e \in E$. Then $S\{-e\}$ is s.r., and
$E \subseteq S\{-e\}$ implies $dom(E) \subseteq S\{-e\}$, contradicting $dom(E) = S$.

If $E'$ satisfies $dom(E') = S$, then $E'$ clearly contains the
extremal points of S. $\square$

A s.r. set S may have no extremal set : this is the case for
$Y(\phi)$ if $Y(\phi) \neq \phi^n(\emptyset)$ for all $n$. This is however not the case for the
bounded sets:

**Definition**: A set X is *n*-bounded iff $X \subseteq \phi^n(\emptyset)$. The *n*-th *slice* of $Y(\phi)$ is defined by $\tau^n = \phi^n(\emptyset) - \phi^{n-1}(\emptyset)$.

(III-4-4) **theorem**: Let $\phi$ be quasi-deterministic, let S be s.r. included in $Y(\phi)$. Then S has an extremal set ; $ext(S)$ is the union of $S \cap \tau^n$ and of the points of $ext(S \cap \phi^{n-1}(\emptyset))$ which do not belong to $dom(S \cap \tau^n)$.

**Proof**: By induction on $n$

- $n=0$; by convention, $\emptyset = ext(\emptyset)$.

- Assume the property true for $n-1$, let S be n-bounded. Then $S \cap \phi^{n-1}(\emptyset)$ has an extremal set $E_1$. Let $E_1' = \{e \in E_1 | e \in dom(S \cap \tau^n)\}$, let $E = E_1' \cup (S \cap \tau^n)$. By construction, $E$ satisfies $dom(E) = S$.

Let $e \in S \cap \tau^n$; since $prod(S) \subseteq \phi^{n-1}(\emptyset)$, e is extremal for S.

Let $e \in E_1'$. Then $e \notin prod(S \cap \tau^n)$ and $e \notin prod(S \cap \phi^{n-1}(\emptyset))$

imply $e \notin prod(S)$ : $e$ is extremal for S.

Therefore $E = ext(S)$.

(III-4-5) **Corollary 1**: Let $x \in Y(\phi)$. Then $prod(x)$ has an extremal set.
Moreover, if $\phi$ is deterministic, then $ext(prod(x)) \supseteq mp(x)$.

**Proof**: If $x \in Y(\phi)$, then $x \in \phi^n(\emptyset)$ for some $n$ and $prod(x)$ is $(n-1)$-bounded.

Assume $\phi$ deterministic, assume $x \in ext.prod(x)$ satisfies $x \notin mp(x)$.

Then $prod(x)-\{x\}$ is s.r., contains $mp(x)$, and produces $x$: contradiction
with the minimality of $prod(x)$. $\square$
(III-4-6) **Corollary 2** : Let $\Phi$ be quasi-deterministic, let $X_n$ be a b.u.c.s. .
Then $X_n$ has an extremal set, which contains $X_n - X_{n-1}$.

**Proof** : By induction on n, $X_n$ is n-bounded, and (III-4-3) applies. Now
$X_n \subseteq \Phi(X_{n-1})$ implies $\text{prod}(X_n) \subseteq X_{n-1}$. Therefore $\text{ext}(X_n) \supseteq X_n - X_{n-1}$. $\square$

### III-5 **Extremal sets.**

According to the previous results, we can define the extremal
sets in an intrinsic way.

**Definition** : Let $\Phi$ be quasi-deterministic. A set $E \subseteq D$ is **extremal** iff $E$ is extremal for $dom(E)$.

(III-5-1) **proposition** : Let $\Phi$ be quasi-deterministic

$$E \text{ extremal} \iff E \cap \text{prod}(E) = \emptyset \iff \text{prod}(E) = \text{dom}(E) = E$$

**Proof** : Since $dom(E) = prod(E) \cup E$, $E \cap prod(E) = \emptyset$ is equivalent
to $prod(E) = dom(E) - E$. But $prod(E) = proddom(E))$, and $E \cap prod(E) = \emptyset$
is equivalent to $E \cap prod dom(E)) = \emptyset$. $\square$

The relation $\prec$ extends to extremal sets :

**Definition** : Let $\Phi$ be quasi deterministic, let $\text{EXT}$ denote the family of the extremal sets included in $Y(\Phi)$. The relation $\prec$ is defined on $\text{EXT}$ by
$E_1 \prec E_2 \iff \text{dom}(E_1) \subseteq \text{dom}(E_2)$

(III-5-2) **proposition** : The relation $\prec$ is a partial ordering on $\text{EXT}$.

**proof** : Reflexivity and transitivity are obvious.

$$\text{Assume } E_1 \prec E_2, E_2 \prec E_1. \text{ Then } \text{dom}(E_1) = \text{dom}(E_2).$$

Since a s.r. set has a unique extremal set, $E_1 = E_2$. The
relation is antisymmetric. $\square$

We now study the structure $(\text{EXT}, \prec)$.
(III-5-3) **Lemma**: Let $E_1, E_2 \in \text{EXT}$. Then $E_1, E_2$ implies $\text{prod}(E_1) \subseteq \text{prod}(E_2)$.

**Proof**: We have $\text{prod}(E_1) \subseteq \text{dom}(E_1) \subseteq \text{dom}(E_2) = \text{prod}(E_2) \cup E_2$.

Assume $\exists e_2 \in E_2, e_2 \in \text{prod}(E_1)$. Then $\exists e_1 \in E_1, e_2 \in \text{prod}(e_1)$. Since $e_1 \in \text{dom}(E_2)$, $\exists e'_2 \in E_2, e_1 \in \text{dom}(e'_2)$. We get $e_2 \in \text{prod}(e'_2)$, which is impossible since $E_2$ is extremal. $\square$

(III-5-4) **Theorem**: Let $E_1, E_2 \in \text{EXT}$. Then $E_1$ and $E_2$ have a least upper bound $\max(E_1, E_2)$ in $(\text{EXT}, \leq)$. This l.u.b. satisfies the following properties:

$$1. \max(E_1, E_2) = \text{ext}(\text{dom}(E_1) \cup \text{dom}(E_2))$$

$$2. \max(E_1, E_2) = \{e_1 \in E_1 \mid e_1 \notin \text{prod}(E_2)\} \cup \{e_2 \in E_2 \mid e_2 \notin \text{prod}(E_1)\}$$

$$3. \text{prod}(\max(E_1, E_2)) = \text{prod}(E_1) \cup \text{prod}(E_2).$$

**Proof**: Consider the set $E$ defined by property 2. ; $E$ is extremal by construction.

Since $E \subseteq E_1 \cup E_2$, we have $\text{dom}(E) \subseteq \text{dom}(F_1) \cup \text{dom}(E_2)$.

Let $x \in \text{dom}(E_1) \cup \text{dom}(E_2)$ ; we can assume $x \in \text{dom}(E_1)$.

Then $\exists e_1 \in E_1, x \in \text{dom}(e_1)$.

If $e_1 \notin \text{prod}(E_2)$, then $e_1 \in E$ and $x \in \text{dom}(E)$.

If $e_1 \in \text{prod}(E_2)$, there exists $e_2 \in E_2$ such that $e_1 \in \text{prod}(e_2)$; $e_1 \in \text{prod}(E_1)$ being impossible, we have $e_2 \notin \text{prod}(E_1)$, and hence $e_2 \in E$ and $x \in \text{dom}(E)$.

Finally $\text{dom}(E) = \text{dom}(E_1) \cup \text{dom}(E_2)$. Property 1. is proved.

This implies $E \succ E_1$ and $E \succcurlyeq E_2$. If $E' \succ E_1$ and $E' \succcurlyeq E_2$, then $\text{dom}(E') \supseteq \text{dom}(E_1) \cup \text{dom}(E_2) = \text{dom}(E)$, and $E' \succcurlyeq F$. Therefore $E$ is the l.u.b of $E_1$ and $E_2$.

By construction, $E$ is of the form $E'_1 \cup E'_2$ with $E'_1 \subseteq E_1$ and $E'_2 \subseteq E_2$. Hence $\text{prod}(E) = \text{prod}(E'_1) \cup \text{prod}(E'_2)$, and $\text{prod}(E) \subseteq \text{prod}(E_1) \cup \text{prod}(E_2)$.

The reverse inclusion follows from (III-5-3), and property 3. is proved. $\square$
(III-5-5) **proposition** : Two elements $E_1$ and $E_2$ of EXT have a g.l.b. in $(\mathrm{EXT},\llcorner)$ iff $\mathrm{dom}(E_1) \cap \mathrm{dom}(E_2)$ has an extremal set. If it exists, this g.l.b. satisfies $\min(E_1, E_2) = \mathrm{ext}(\mathrm{dom}(E_1) \cap \mathrm{dom}(E_2))$

**proof** : If $\mathrm{dom}(E_1) \cap \mathrm{dom}(E_2)$ has an extremal set E, then E is clearly the g.l.b. of $E_1$ and $E_2$.

Assume conversely that $E_1$ and $E_2$ have a g.l.b. E, assume $\mathrm{dom}(E) \subseteq \mathrm{dom}(E_1) \cap \mathrm{dom}(E_2)$. Let $a \in \mathrm{dom}(E)$, $a \neq E$, $E' = \max(\{e\}, E)$. Then $E' \neq E$, $E' \supsetneq E$, $E' \preceq E_1$, $E' \preceq E_2$, which is impossible. $\square$

### III-6 S-complete sets

Among the extremal sets included in a s.r. set, those which are maximal with respect to inclusion present a very rich structure. They seem to be also useful for determining the storage requirements of bottom-up computations (see section 4).

**Definition** : Let $\emptyset$ be quasi-deterministic and continuous, let S be a s.r. included in $Y(\emptyset)$. A set $C \subseteq S$ is S-complete iff C is extremal and no extremal set included in S properly contains C.

SCOMP denotes the family of the S-complete sets.

(III-6-1) **proposition** : Let $C \subseteq S$ be extremal. Then C is S-complete iff $\forall x \in S-\mathrm{dom}(C) \quad \mathrm{dom}(x) \cap C \neq \emptyset$

**proof** : 1. Assume C S-complete, let $x \in S-\mathrm{dom}(C)$ satisfy $\mathrm{dom}(x) \cap C = \emptyset$. Then for all c in C, $c \notin \mathrm{dom}(x)$ and $x \notin \mathrm{dom}(c)$; hence $C \cup \{x\}$ is extremal, is included in S and strictly contains C: contradiction with C S-complete.

2. Assume $\forall x \in S - \mathrm{dom}(C) \ \mathrm{dom}(x) \cap C \neq \emptyset$.

Assume there exists $a \in S$ such that $C \cup \{a\}$ is extremal. Then $\mathrm{dom}(a) \cap C = \emptyset$ and $a \notin \mathrm{dom}(C)$, which is impossible. $\square$

The next characterisation does not directly involve the points of C, but the domain of C:
(III-6-2) **theorem**: Let $C \subseteq S$ be extremal. Then C is S-complete iff
the following two conditions hold:

1. $\forall x \in S \prod(x) \subseteq \text{prod}(C) \Rightarrow x \in \text{dom}(C)$

2. $\forall x \in S - \text{prod}(C) \quad \text{dom}(x) \cap \text{dom}(C) \neq \emptyset$

**proof**: a) Assume C S-complete. The second condition holds by (III-6-1).
Assume there exists $x \in S$ such that $x \notin \text{dom}(C)$ and $\text{prod}(x) \subseteq \text{prod}(C)$.

Then $x \notin \text{prod}(C)$, and for all $\alpha \in C$, $\alpha \notin \text{prod}(x)$; This means
that $C \cup \{x\}$ is extremal, contradicting the S-completeness of C.

b) Assume both conditions hold, let $x \in S - \text{prod}(C)$.
Since $x \in \phi^n(\emptyset)$ for some $n$, the set $\text{dom}(x) \cap \text{dom}(C)$ is n-bounded and
has an extremal set E (III-4-4). Because of the second condition, E is not
empty. Let $e \in E$, Lemma (III-5-3) implies $\text{prod}(e) \subseteq \text{prod}(C)$, and
first condition implies $e \in \text{dom}(C)$. Therefore $e \in \text{dom}(x) \cap C$, and
C is S-complete by (III-6-1). $\square$

(III-6-3) **Corollary**: Let C be S-complete, let $C_1 \subseteq S$ be such that
$C \prec C_1$. Then $C_1$ is S-complete iff $\forall x \in S \ \text{prod}(x) \subseteq \text{prod}(C_1) \Rightarrow x \in \text{dom}(C_1)$
**proof**: The condition 2. of (III-6-2) holds for C, and $\text{dom}(C_1) \supseteq \text{dom}(C)$.
It also holds for $C_1$. $\square$

The slices give natural examples of S-complete sets :

(III-6-4) **proposition**: Let S be s.r. not n-bounded. Then $S \cap \tau^n$ is not empty and is S-complete.

Since S is not n-bounded, there exists a least $m \ge n$ such that
$S \cap \tau^m \ne \emptyset$. Let $y \in S \cap \tau^m$. Then $\text{prod}(y) \subseteq \text{prod}(S) \cap \phi^{m-1}(\emptyset) = \text{prod}(S) \cap \phi^n(\emptyset)$.
Assume $S \cap \tau^m = \emptyset$. Then $\text{prod}(y) \subseteq \text{prod}(S) \cap \phi^{n-1}(\emptyset)$ implies $y \in S \cap \tau^m$,
which is impossible. Therefore $S \cap \tau^m \ne \emptyset$.
Clearly, $S \cap \tau^n$ is extremal. Let $y \in S$ be such that $y \notin \text{dom}(S \cap \tau^n)$. Then $\text{dom}(y)$ is not n-bounded, and $\text{dom}(y) \cap \tau^n \neq \emptyset$. Therefore $S \cap \tau^n$ is S-complete by (III-6-1).

### III-7 Lattice of the S-complete sets

**Definition:** Let $S$ be s.r., let $S'$ be s.r. included in $S$. The yield of $S'$ in $S$ is defined by:

$$Y_S(S') = (\Phi(S') - S') \cap S = \{s \in S \mid s \notin S' \land \text{prod}(s) \subseteq S'\}$$

(III-7-1) **Theorem:** Let $\Phi$ quasi-deterministic and continuous, let $S$ be s.r. and included in $Y(\Phi)$. Then $(SCOMP, \llcorner)$ is a lattice; the l.u.b. and g.l.b. satisfy the following properties:

1. $cmax_S(C_1, C_2) = Y_S(\text{prod}(C_1) \cup \text{prod}(C_2))$.

2. $\text{prod}(cmax_S(C_1, C_2)) = \text{prod}(C_1) \cup \text{prod}(C_2)$.

3. $cmin_S(C_1, C_2) = Y_S(\text{prod}(C_1) \cap \text{prod}(C_2))$.

4. $cmin_S(C_1, C_2) = \min(C_1, C_2) = \text{ext}(\text{dom}(C_1) \cap \text{dom}(C_2))$.

5. $cmin_S(C_1, C_2) = (C_1 \cap \text{dom}(C_2)) \cup (C_2 \cap \text{dom}(C_1))$.

6. $\text{prod}(cmin_S(C_1, C_2)) = \text{prod}(C_1) \cap \text{prod}(C_2)$.

**Proof:** a) Let $C = Y_S(\text{prod}(C_1) \cup \text{prod}(C_2))$.

Clearly, $C$ is extremal and contains $\max(C_1, C_2)$ (cf III-5-4). Hence $C \supseteq C_1$ and $C \supseteq C_2$. By (III-5-3), $\text{prod}(C) \supseteq \text{prod}(C_1) \cup \text{prod}(C_2)$. By construction, $\text{prod}(C) \subseteq \text{prod}(C_1) \cup \text{prod}(C_2)$, and 2. holds.

Assume $x \in S$ and $\text{prod}(x) \subseteq \text{prod}(C)$.

If $x \notin \text{prod}(C_1) \cup \text{prod}(C_2)$, then $x \in C$ by definition of $C$. Otherwise $x \in \text{dom}(C_1) \cup \text{dom}(C_2) \subseteq \text{dom}(C)$. Hence $C$ is S-complete by (III-6-3).

Assume $C'$ S-complete, $C' \supseteq C_1, C' \supseteq C_2$. Let $c \in C$. Then $\text{prod}(c) \subseteq \text{prod}(C) = \text{prod}(C_1) \cup \text{prod}(C_2)$. But by (III-5-3),
$\mathrm{prod}(C_1) \cup \mathrm{prod}(C_2) \subseteq \mathrm{prod}(C')$. Hence $c \in \mathrm{dom}(C')$ by (III-6-2).
Therefore $C \prec C'$, and $C$ is the l.u.b. of $C_1$ and $C_2$ in SCOMP.

b) Let $C = Y_S ( \mathrm{prod}(C_1) \cap \mathrm{prod}(C_2) )$

b1: Let $c \in C$. Then $\mathrm{prod}(c) \subseteq \mathrm{prod}(C_1) \cup \mathrm{prod}(C_2)$ implies by (III-6-2) $c \in \mathrm{dom}(C_1) \cap \mathrm{dom}(C_2)$. Since $c \notin \mathrm{prod}(C_1) \cap \mathrm{prod}(C_2)$, we have either $c \notin \mathrm{prod}(C_1)$ and $c \in C_1 \cap \mathrm{dom}(C_2)$, or $c \in \mathrm{prod}(C_2)$ and $c \in C_2 \cap \mathrm{dom}(C_1)$. Therefore $C \subseteq (C_1 \cap \mathrm{dom}(C_2)) \cup (C_2 \cap \mathrm{dom}(C_1))$. The reverse inclusion holds by construction, and property 5. is proved.

b2: We now have $\mathrm{dom}(C) = \mathrm{dom}(C_1 \cap \mathrm{dom}(C_2)) \cup \mathrm{dom}(C_2 \cap \mathrm{dom}(C_1))$, and therefore $\mathrm{dom}(C) = \mathrm{dom}(C_1) \cap \mathrm{dom}(C_2)$; (cf. III-3-2). Since $C$ is extremal by construction, property 4. holds.

b3: To show that $C$ is S-complete, we apply (III-6-2).
Assume $x \in S-\mathrm{dom}(C)$. Three cases are possible:

Case 1: $x \notin \mathrm{dom}(C_1)$ and $x \in \mathrm{dom}(C_2)$. Then $\mathrm{dom}(x) \cap C_1 \neq \emptyset$, $\mathrm{dom}(x) \cap (C_1 \cap \mathrm{dom}(C_2)) \neq \emptyset$ and $\mathrm{dom}(x) \cap C \neq \emptyset$.

Case 2: $x \notin \mathrm{dom}(C_1)$ and $x \in \mathrm{dom}(C_2)$. Symmetric to case 1.

Case 3: $x \notin \mathrm{dom}(C_1)$ and $x \notin \mathrm{dom}(C_2)$. Then $\mathrm{dom}(x) \cap C_1 \neq \emptyset$.
Let $c_1 \in \mathrm{dom}(x) \cap C_1$. If $c_1 \in \mathrm{dom}(C_2)$, then $c_1 \in C$. Otherwise $\mathrm{dom}(c_1) \cap C_2 \neq \emptyset$, $\mathrm{dom}(x) \cap (C_2 \cap \mathrm{dom}(c_1)) \neq \emptyset$ and $\mathrm{dom}(x) \cap C \neq \emptyset$.

Eventually, $C$ being the g.l.b. of $C_1$ and $C_2$ in $(\mathrm{EXT}, \prec)$ is also their g.l.b. in $(\mathrm{SCOMP}, \prec)$.

### III-8 Bottom-up computations and induction techniques.

We do not define precisely "bottom-up algorithms" or "bottom-up computation rules". However we remark that there is always a way of effectively producing every point of $Y(\Phi)$ when $D$ is denumerable:
(III-8-1) **Proposition** : Let $D = \{d_n, n \in N\}$, let $\phi : P(D) \to P(D)$ be monotonic and continuous. Let $X_n$ be the sequence of subsets of D defined by :

$$X_0 = \emptyset$$

$X_n = X_{n-1} \cup \{d_i\}$ if there exist a least integer $i$ such that $d_i \notin X_{n-1}$ and $d_i \in \phi(X_{n-1})$

$X_n = X_{n-1}$ otherwise.

Then $\{X_n, n \in N\}$ is a b.u.c.s., and has limit $Y(\phi)$.

**Proof** : The sequence is a b.u.c.s. by construction, and $\cup_n X_n \subseteq Y(\phi)$ holds by induction on n.

Assume that $\cup_n X_n$ is not a fixpoint; then there would exist an integer $p$ such that $d_p \notin \cup_n X_n$ and $d_p \in \phi(\cup_n X_n)$. By continuity, $d_p \in \phi(X_n)$. Let $q$ be such that $d_p \in \phi(X_q)$. Then $d_p \in \phi(X_r)$ for $r \ge q$, and there exist a sequence $d_{i_q}, d_{i_q+1}, \dots, d_{i_q+q}, \dots$ of distinct points of D such that for every $1 \le n$ :

$$d_{i_q+1} \in X_{q+1}, \quad d_{i_q+q} \notin X_{q+1-q}, \quad d_{i_q+q+1} \in \phi(X_{q+1-q}), \quad i_{q+1} < p.$$

This is impossible, since there only exist a finite number of integers less than $p$.

<figure><img src="image_6.png" /></figure>

Top-down computation rules do not avoid recomputation of intermediate values ( except by using memo-functions, which may involve additional tests and a waste of storage.) . It seems that when using "uniform bottom-up computation rules", we cannot avoid to compute useless intermediate values; there is probably no uniform way of characterising the domain of a given point.

We now develop some induction techniques which might allow to characterise the domains in particular examples.

All the induction principles we present derive from the following one :
(III-8-2) **Proposition** : Let $\Phi$ be continuous. Let $h : D \to P(D)$ be such that $\forall x \in \Phi^n(\emptyset) h(x) \subseteq \Phi^{n-1}(\emptyset)$. Let $P$ be a property such that for every $x \in Y(\Phi)$, if $P$ is true for every member of $h(x)$, then $P$ is true of $x$. Then one can conclude that $P$ is true of every member of $Y(\Phi)$.

$$[\forall x \in Y(\Phi) \quad [\forall y \in h(x) \ P(y)] \Rightarrow P(x)] \vdash \quad [\forall x \in Y(\Phi) \ P(x)]$$

**Proof** : By induction on $n$: Assume $\forall x \in Y(\Phi) \ [\forall y \in h(x) \ P(y)] \Rightarrow P(x)$.
Let $x \in \Phi(\emptyset)$. Then $h(x) = \emptyset$, and $P(x)$ holds.
Assume $\forall y \in \Phi^n(\emptyset) \ P(y)$. Let $x \in \Phi^{n+1}(\emptyset)$. Then $h(x) \subseteq \Phi^n(\emptyset)$ implies $\forall y \in h(x) \ P(y)$, and therefore $P(x)$. $\Box$

Some possible choices for $h(x)$ are:

1. $h(x) = \Phi^{n-1}(\emptyset)$. We obtain the usual computational induction principle (Morris [5]).

2. $h(x) = \text{prod}(x)$. We obtain the usual structural induction principle applied to the relation $\prec$.

3. $h(x) = \text{ext}(\text{prod}(x))$.

4. $h(x) = \text{mp}(x)$ if $\Phi$ is deterministic. This principle seems to be the most useful when dealing with recursive programs : the set $\text{mp}(x)$ is directly given by the elementary predicates of the translated formula.

An example of application of this last principle is given in the next section.
IV Time and space optimality. Application to Ackermann program.

IV-1 Time and space optimality of storage configuration sequences.

Given a recursive program, there exist several different implementations, using either recursion mechanism or production mechanisms. It is natural to compare these implementations. We shall use as time and space complexity measures the number of recursion or production steps and the number of intermediate values respectively.

Our formalism provides naturally these evaluations for the implementations using production mechanisms: let {$Y_n, n \in \mathbb{N}$} be a storage configuration sequence which computes a point $(\bar{x},z)$.

- The *amount of space* used by this sequence is the maximal cardinality of $Y_n$.

- The sequence is *optimal with respect to time* if its limit is the domain of $(\bar{x},z)$ and if it is simple (cf. III-1) :that is no intermediate value is computed twice, only useful intermediate values are computed.

- The sequence is *optimal* iff it is optimal with respect to time, and iff it is optimal with respect to space among those s.c.s which are optimal with respect to time. (It may be the case that one can use less space by recomputing some intermediate values).

An algorithm realising an implementation is said *optimal* iff for every argument the s.c.s. it determines is optimal.

We emphasise the fact that optimality is defined *with respect to the implementation of a given recursive program*, and not with respect to the function it computes. For instance, the Fibonacci function can be defined by the two following programs:

$$ P1: \text{fib}(n) = \text{if } n=0 \text{ v } n=1 \text{ then } 1 \text{ else } \text{fib}(n-1) + \text{fib}(n-2) $$

$$ P2: \text{fib}(n) = \text{if } n=0 \text{ v } n=1 \text{ then } 1 \text{ else if } n=2 \text{ then } 2 \\ \text{else } (\text{fib}(n-1) + \text{fib}(n-2) + \text{fib}(n-3))/2 $$

An optimal implementation of $P2$ is not optimal for the computation of $\text{fib}(n)$, $n>2$: there always exist better implementations of $P1$; in fact, no implementation of $P1$ is an implementation of $P2$, and conversely.
IV-2 Application : Ackermann program.

The purpose of the next sections is to show that Rice's
algorithm [8] realises an optimal bottom-up implementation of Ackermann
program.

Ackermann program is defined on $N_u\{\perp\}$ by the following program
scheme:

$A(m,n) = \text{if } m=0 \text{ then } n+1 \text{ else if } n=0 \text{ then } A(m-1,1) \text{ else } A(m-1,A(m,n-1))$

The tests $m=0$ and $n=0$ imply $\forall m,n \in N A(\perp,1)=A(m,\perp)=A(\perp,n)=\perp$.

Hence no bound variable can be set to $\perp$, and the associated production
function may be simply defined by:

$$
\Phi(X) = \{ (m,n,z) \in \mathbb{N}^3 \mid \exists y_1, y_2, y_3 \in \mathbb{N} \ [z = \begin{cases} \text{if } m=0 \text{ then } n+1 \text{ else if } n=0 \text{ then } y_1 \text{ else } y_2 \end{cases} \wedge [(m-1,1, y_1) \in X] \wedge [(m-1, y_3, y_2) \in X] \wedge [(m, n-1, y_3) \in X]] \}
$$

As the function Θ in (II-5), the function φ is not deterministic,
but is such that every point in Y(φ) has a unique minimal producer in Y(φ).

- If $m=0$, then $mp(m,n,z)=\emptyset$.

- If $m \neq 0$ and $n=0$, then $mp(m,n,z) = \{(m-1,1,z)\}$.

- If $m \neq 0$ and $n \neq 0$, then $mp(m,n,z) = \{(m,n-1,A(m,n-1)), (m-1,A(m,n-1),z)\}$

(IV-2-1) **Proposition:** 1. *The function is total: $\forall m, n \in N A(m, n) \in N$.*

2. $\forall m,n,n' \in N \ n'>n \Rightarrow A(m,n') > A(m,n)$.

3. $\forall m, m', n \in N \ m' > m \Rightarrow A(m', n) > A(m, n).$

**Proof:** A proof of 1. is given in Manna [2] (p.410) ; it uses the well-
foundedness of the lexicographic ordering $\le_\ell$ on $N^2$ : $(x,y)\le_\ell (x',y')$ holds
iff $x\le x'$ or $x=x'$ and $y\le y'$. Properties 2. and 3. are well-known, and can be
easily proved by induction on ($N,\le$) and ($N^2,\le_\ell$). $\square$

We now characterise the domains:

(IV-2-2) **Proposition:** Let $(m, n, z) \in Y(\phi)$. Then:

1. if $m=0$, then $\text{dom}(m,n,z) = \{(m,n,z)\}$;

2. if $m \neq 0$, then $\text{dom}(m,n,z) = \{(m',n',z') \in Y(\phi) \mid m' \leq m \wedge z' \leq z\}$.

**Proof:** By induction on the minimal producers (III-8-2').

Let $D(m,n,z) = \{(m',n',z') \in Y(\phi) \mid m' \le m \wedge z' \le z\}$
Case $m=0$: then $mp(m,n,z)=\emptyset$ implies property 1.

Case $m \neq 0, n=0$: assume $dom(m-1,1,z) = D(m-1,1,z)$; then
$dom(m,0,z) = D(m-1,1,z) \cup \{(m,n,z)\} \subseteq D(m,0,z)$.

Let $(m',n',z') \in D(m,0,z)$; if $m' < m$, then $m' \le m-1$ and $z' \le z$ imply $(m',n',z') \in D(m-1,1,z) \subseteq dom(m,0,z)$; if $m' < m$, then (IV-2-1) implies $n'=0$; therefore $(m',n',z') = (m,0,z)$ and $(m',n',z') \in dom(m,0,z)$.

Finally $dom(m,0,z) = D(m,C,z)$.

Case $m \neq 0, n \neq 0$: let $z1=A(m,n-1)$; assume $dom(m,n-1,z1)=D(m,n-1,z1)$ and $dom(m-1,z1,z)=D(m-1,z1,z)$. Then:
$$dom(m,n,z) = D(m,n-1,z1) \cup D(m-1,z1,z) \cup \{(m,n,z)\}$$
Proposition (IV-2-1) implies $z1 < z$, and therefore $dom(m,n,z) \subseteq D(m,n,z)$.

Let $(m,n',z') \in D(m,n,z)$:

- if $m'=m$, then (IV-2-1) implies $n' \le n$; if $n'=n$, then $(m',n',z')=(m,n,z)$; otherwise $(m',n',z') \in D(m,n-1,z1)$.

- If $m' < m$, then $(m',n',z') \in D(m-1,z1,z)$.

In both cases, $(m',n',z') \in dom(m,n,z)$. Eventually, $dom(m,n,z)=D(m,n,z)$.

□
IV-3 A bottom-up implementation of Ackermann program.

The following PASCAL program implements a variant of Rice's
algorithm [8].

function ACK(M:INTEGER;N:INTEGER):INTEGER;
var VAL:PLACE:array[0..10]of INTEGER;
I,Z,T:INTEGER;
begin
  %TEST M=0%
  if M=0 then ACK:=N+1
else % TEST N=0%
  if N=0 then
    begin
      M:=M-1;
      N:=0
    end
else begin
  for I:=1 to M do %INITIALISATIONS%
    begin
      VAL[I]:=1;
      PLACE[I]:=-1;
    end;
  PLACE[0]:=0;
  T:=0;
  Z:=2 % FIRST VALUE OF Z%;
repeat
  begin
    %BLOCK A%
    PLACE[0]:=PLACE[0]+1;
    VAL[0]:=Z;
    T:=T+1;
  end %A%;
  I:=1;
  while (VAL[I]=PLACE[I-1]) and (I<=N) do
    begin
      %BLOCK B%
      VAL[I]:=Z;
      PLACE[I]:=PLACE[I]+1;
      I:=I+1;
      T:=T+1;
    end %B%;
    Z:=Z+1 % VALUE INCREMENTED%;
until PLACE[M]=N % END TEST%;
ACK:=VAL[M];
end;
end %ACK%;
**Remark:** the arrays `PLACE` and `VAL` should have dimension 0..M (PASCAL does not allow flexible arrays).

If $M=0$, the program is directly exited with `ACK=N+1`; if $N=0$, the argument $(M,N)$ is transformed into $(M-1,1)$; therefore we only investigate the case $M>0, N>0$.

A termination proof is given in Manna [2] (p. 200-202), and we only give an informal correctness proof; a formal one could be constructed by using the defining predicate of $\Phi$ in assertions.

The algorithm uses the fact that for every $z>1$, the arguments such that $A(m,n)=z$ form a finite sequence of the form $(0,n1), (1,n2), \dots, (k,nk)$.

Points in the graph are represented by triples $(I, \text{PLACE}[I], \text{VAL}[I])$. A new point is created each time one of the blocks A or B is exited. The variable T counts the number of such exits, and will be called the *time counter*; (T is useless for the algorithm itself). For every variable X, let $X_t$ denote the value of X at time t; let $d_t$ be the new triple introduced, let $Y_t$ be the set of intermediate triples "in storage":

$$d_t = (I_t, \text{PLACE}[I_t], \text{VAL}[I_t])$$

$$Y_t = \{ (J, \text{PLACE}[J_t], \text{VAL}[J_t]) \mid 0 \le J \le M \land \text{VAL}[J_t] > 0 \}$$

Let $T_0$ be the value of T when the program is exited.

(IV-3-1) **Proposition:** For every $M, N > 0$, the sequence $\{ \tilde{Y}_t \mid 1 \le t \le T_0 \}$ is a simple s.c.s. with limit $\text{dom}(M, N, A(M, N))$; $\text{ACK}(M, N) = A(M, N)$.

**proof:**

1. $\tilde{Y}_t$ is a s.c.s.

- **Case** $I_t=0$: block A was exited, and $\text{VAL}[0]_t = \text{PLACE}[0]_t + 1$; hence $d_t \in \Phi(\emptyset)$.

- **Case** $I_t \ne 0$, $\text{PLACE}[I_t]_t=0$: block B was exited at time t, and also at time $t-1$; the following relations hold:

$I_{t-1} = I_t - 1$ ; $Z_{t-1} = Z_t$

$\text{VAL}[I_t]_{t-1} = 1$ ; $\text{PLACE}[I_t]_{t-1} = -1$

$\text{VAL}[I_t]_t = Z_t$

Since the *do* loop was entered, we also have:

$\text{PLACE}[I_{t-1}]_{t-1} = \text{VAL}[I_t]_{t-1} = 1$
Hence $d_{t-1} = (I_{t-1}, \text{PLACE}[I_{t-1}]_{t-1}, \text{VAL}[I_{t-1}]_{t-1}) = (I_{t-1,1}, Z_t)$.
Therefore $d_t \in \Phi(\{d_{t-1}\}) \subseteq \Phi(Y_{t-1})$.

- Case $I_t \neq 0$, $\text{PLACE}[I_t]_t \neq 0$: similar proof; one easily shows that $Y_{t-1}$ contains the two points $(I_t, \text{PLACE}[I_t]_{t-1}, \text{VAL}[I_t]_{t-1})$ and $(I_t-1, \text{VAL}[I_t]_{t-1}, Z_t)$. This implies $d_t \in \Phi(Y_{t-1})$.

2. $Y_t$ is simple: the pairs $(Z_t, I_t)$ strictly increase with respect to the lexicographic ordering $\le_\ell$ on $N^2$; no value is computed twice.

3. $\text{ACK}(M,N) = A(M,N)$: since $Y_t$ is a s.c.s., the results of the first sections imply for every $t$ $\text{VAL}[I_t]_t = A(I_t, \text{PLACE}[I_t]_t)$. When the program is exited, we have $I_{T0}^M$, $\text{PLACE}[I_{T0}]_{T0} = N$ and $\text{ACK} = \text{VAL}[I_{T0}]_{T0} = A(M,N)$.

4. $\bigcup_{1 \le t \le T0} Y_t = \text{dom}(M,N,A(M,N))$: Let $S = \bigcup_{1 \le t \le T0} Y_t$; for every $t$, we have $I_t \le M$ and $Z_t \le Z_{T0}$. By (IV-2-2), $d_t \in \text{dom}(M,N,A(M,N))$; Hence $S \subseteq \text{dom}(M,N,A(M,N))$.

But $S$ is s.r. (III-1-1, III-2-4), and contains $(M,N,A(M,N))$: therefore $S \supseteq \text{dom}(M,N,A(M,N))$. $\square$

## IV-4 Optimality of the algorithm.

Proposition (IV-3-1) shows that the algorithm is optimal with respect to time. Given $x,y>0$, the simple s.c.s. it defines uses $x+1$ space units to compute $A(x,y)$. Our purpose is to show that no simple s.c.s. can use less than $x+1$ space units. (we only consider s.c.s. of the form $\{Y_n, 0 \le n \le N\}$ such that $(x,y,A(x,y)) \in Y_N$).

We use a technique similar to that developed by Cook and Sethi in [14].
**Definition**: Let $x \in Y(\Phi)$. A path from $x$ to $\Phi(\emptyset)$ is a sequence $x_0, x_1, \dots, x_n$ of points of $Y(\Phi)$ such that $x_0=x$, $x_n \in Y(\Phi)$, $\forall p \ 1 \le p \le n \ x_{p+1} \in \text{mp}(x_p)$.

The proof relies on the following lemma:

(IV-4-1) **Lemma**: Let $\Phi$ be deterministic, let $x \in Y(\Phi)$, let $\{Y_n, 0 \le n \le N\}$ be a simple s.c.s. with limit $\lim_{n \to \infty} Y_n$, and assume $x \in Y_N$. Let $\{X_n, 0 \le n \le N\}$ be the corresponding b.u.c.s.: $X_n = \lim_{0 \le p \le n} Y_p$. Let $k$ be the smallest integer such that $X_k \ge \text{dom}(x) \cap \Phi(\emptyset)$. Then for every path $P=\{x_0, x_1, \dots, x_q\}$ from $x$ to $\Phi(\emptyset)$, the following property holds:

$$ \forall k' \ k \le k' \le N \quad P \cap Y_{k'} \ne \emptyset $$

**Proof**: Assume the property false. Then there exists a path $P=\{x_0, x_1, \dots, x_q\}$ and an index $k'$, $k \le k' \le N$, such that $P \cap Y_{k'} = \emptyset$.

The set $P \cap X_k$, is not empty, since it contains at least $x_q$. Let $q'$ be the least integer such that $x_q' \in X_k'$.

We cannot have $q'=0$: otherwise $x \in X_k$, and $x \in Y_N$ would imply $x \in Y_{k'}$, and $P \cap Y_{k'} \ne \emptyset$ (cf definition of simplicity).

Since $x_q', Y_{k'}$, and $x_q', Y_m$ for some $m<k'$, $x_q', Y_m$ holds for $m' \ge k'$. Consider now the point $x_{q'-1}':$ by hypothesis, $x_q', \text{mp}(x_{q'-1})$ and $x_{q'-1}' Y_{k'}$ hold. This implies for every $m' \ge k'$ $\text{mp}(x_{q'-1}) \in Y_m$, and hence $x_{q'-1}' Y_m' + 1$. Finally, $x_{q'-1}' Y_m$ for all $m \le N$. This is impossible, since $x_{q'-1} \in \text{dom}(x)$ and $\text{dom}(x) = \text{dom}(x)$. $\Box$

Let us come back to Ackermann production function. Given $(x,y,z) \in Y(\Phi)$, our purpose is now to construct $x+1$ paths which are distinct in $X_k$ for every simple s.c.s. We use for this the construction of a $\text{dom}(x)$-complete set $C$. Let us define the following transformations:

**Definitions**: Let $(x,y,z) \in Y(\Phi)$, $x>0$, $y>0$.

$$ \mu(x,y,z) = (x-1,y1,z) \quad \text{with} \quad z = A(x-1,y1). $$

$$ \nu(x,y,z) = (x,y-1,z1) \quad \text{with} \quad z1 = A(x,y-1). $$
$$C(x,y,z) = \{c_m(x,y,z) \mid 0 \le m \le x\}$$

$$\text{with} \quad c_m(x,y,z) = \nu_\mu^{x-m}(x,y,z) \quad \text{for } 0<m\le x, \\ c_C(x,y,z) = \mu^x(x,y,z).$$

We denote $c_m(x,y,z) = (c_m^2, c_m^3)$. (See diagram 2).

(IV-4-2) **Lemma**: $x,y>0 \quad A(x,y-1) < A(x-1,A(x,y-1)-1)$.

**proof**: left to the reader.

(IV-4-3) **Proposition**: Let $x,y>0$; the set $C(x,y,z)$ is $dom(x,y,z)$-complete.

**Proof**: by (IV-2-1,IV-2-2), $C(x,y,z) \subseteq dom(x,y,z)$ holds.

By lemma (IV-4-2), we have $c_X^3 < c_{X-1}^3 < \dots < c_2^3 < c_1^3 < z = c_0^3$; hence $C(x,y,z)$ is extremal.

Let $(x',y',z') \in dom(x,y,z)$; if $x'>0$, then either $(x',y',z') \in dom(c_X)$, or $c_X \in dom(x',y',z')$. If $x'=0$, then either $(x',y',z') = c_0$ or $(x',y',z') \in dom(c_1)$. Therefore $C(x,y,z)$ is $dom(x,y,z)$-complete.

□

(IV-4-4) **Proposition**: Let $(x,y,z) \in Y(\emptyset)$, $x,y>0$; let $\{Y_n, 0 \le n \le N\}$ be a simple s.c.s. with limit $dom(x,y,z)$, let $\{X_n, 0 \le n \le N\}$ be the associated b.u.c.s.; let $k$ be the least integer such that $X_k \supseteq dom(x,y,z) \cap \emptyset$.

Then $(x',y',z') \in X_k$ implies $x' \le C$

**Proof**: assume $(x',y',z') \in X_k$, $x' \ne 0$; then $X_{k-1} \supseteq \text{prod}(x',y',z)$.

But by (IV-2-2), $\text{prod}(x',y',z) \cap \emptyset = \text{prod}(x,y,z) \cap \emptyset$; this contradicts the minimality of $k$.

We now show the final result :

(IV-4-5) **Theorem**: Let $\emptyset \ne \Phi$ denote the Ackermann production function, let $(x,y,z) \in Y(\emptyset)$, $x>0, y>0$. Let $\{Y_n, 0 \le n \le N\}$ be a simple s.c.s. with limit $dom(x,y,z)$. Then $\max_{C \le n \le N} \text{card}(Y_n) \ge x+1$.

**Proof**: to each $c_m$ we associate a path $P_m$ from $(x,y,z)$ to $\emptyset$ in the following way : we first apply $\mu$ $x$-m times and then $\nu$, to reach $c_m$;
we then apply $\mu$ m times to reach $\phi(\emptyset)$, thus keeping the third coordinate equal to $c_m^3$. Let a denote $(x,y,z)$:

$$P_0 = (a, \mu a, \mu^2 a, \dots, \mu^{x-1} a, \mu^x a = c_0)$$

$$P_1 = (a, \mu a, \mu^2 a, \dots, \mu^{x-1} a, \nu \mu^{x-1} a = c_1, \mu c_1)$$

$$P_m = (a, \mu a, \mu^2 a, \dots, \mu^{x-m} a, \nu \mu^{x-m} a = c_m, \mu c_m, \mu^2 c_m, \dots, \mu^m c_m)$$

$$P_x = (a, \nu a = c_x, \mu c_x, \mu^2 c_x, \dots, \mu^x c_x)$$

Let $m<m'$; by (IV-4-3), $P_m$ and $P_{m'}$ only intersect at points $a, \mu a, \mu^2 a, \dots, \mu^{x-m'} a$, and by (IV-4-4), these points do not belong to $X_k$.

Lemma (IV-4-1) implies the result. $\square$

<figure><img src="image_7.png" /></figure>

**Remark**: the fact that $C(x,y,z)$ is dom(a)-complete is not essential to the proof; however looking for S-complete sets seems to be a good heuristic in this class of problems.

### Acknowledgements.

I am grateful to Pr. M. Nivat for his advice and encouragement.

Many thanks to Bruno Courcelle, Jean Jacques Lévy, Philippe Flajolet, Charles Rackoff, and particularly Jean Marc Steyaert, who helped me in this work.
Bibliography

[1] R. Burstall, *Proving properties of programs by structural induction.*
Computer Journal, vol. 12, (1969), 41-48.

[2] Z. Manna, *Mathematical theory of computation.*
McGRAW-HILL computer science series.

[3] Z. Manna, J. Vuillemin, *Fixpoint approach to the theory of computation.*
CACM, vol 15, n°7, (1972).

[4] R. Milner, *Implementation and applications of Scott's logic for
computable functions.*
Proceedings ACM conference, ACM, New York, (1972).

[5] J.H. Morris, *Another recursion induction principle.*
CACM, vol. 14, n°5, (1971).

[6] M. Nivat, *On the interpretation of recursive program schemes.*
Rapport Laboria n°84, IRIA, (1974).

[7] D. Park, *Fixpoint induction and proofs of program properties.*
Machine Intelligence 5, Edinburgh University press, (1969).

[8] H.G. Rice, *Recursion and iteration.*
CACM, vol 8, n°2, 114-115, (1975).

[9] D. Scott, *Outline of a mathematical theory of computation.*
Oxford mono. PRG 2, Oxford University, (1970).

[10] D. Scott, C. Strachey, *Towards a mathematical semantics for programming
languages.*
Oxford mono. PFG 6, Oxford University, (1972).
[11] J. Vuillemin, *Proof techniques for recursive programs.*
Ph.D, CSD, Stanford University, (1973).

[12] J. Vuillemin, *Syntaxe, Sémantique et axiomatique d'un langage de programmation simple.*
Thèse de doctorat d'état ès-sciences mathematiques,
Université Paris VI, Paris.

[13] D. Luckham, D. Park, M. Paterson, *On formalised computer programs.*
Programming research group, Oxford University.

[14] S. Cook, R. Sethi, *Storage requirements for deterministic polynomial time recognizable languages.*
ACM symposium, Seattle, Washington, april 30- may 2, (1974).
DIAGRAM 1: a deterministic production function.

<figure><img src="image_8.png" /></figure>

The arrows represent the relation $x \preceq y$. The relation $\prec$ is obtained by transitivity.

------ : dom(x)

O : mp(x)

+++ : an extremal set.

<figure><img src="image_9.png" /></figure>

------ : a s.r. set S.

0000 : a S-complete set.
<figure><img src="image_10.png" /><figcaption>DIAGRAM 2 : Ackermann recursion structure.</figcaption></figure>

The domain of (4,0,13) ; numbers are values of the function.

<figure><img src="image_11.png" /></figure>

Transformations µ,ν.

<figure><img src="image_12.png" /></figure>

The set C(3,1,13) , and the corresponding paths P₀, P₁, P₂, P₃.