RIA
laboria

laboratoire de recherche
en informatique
et automatique

Recursive schemes
algebraic trees
and deterministic languages

Bruno
B.Courcelle

Institut de Recherche
d'Informatique
et d'Automatique

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

Rapport de Recherche n° 78

Septembre 1974
RECURSIVE SCHEMES, ALGEBRAIC TREES and DETERMINISTIC LANGUAGES

Bruno COURCELLE

IRIA-Domaine de Voluceau

78150 - Le Chesnay

France.

**Abstract :**

The equivalence problems for uninterpreted recursive program schemes and deterministic pushdown automata are reducible to each other. The equivalence class of a scheme is characterized by an infinite tree which is generated by the scheme as a language by a context-free grammar and which satisfies the equations of the system. Such trees are called algebraic. Roughly speaking, a tree is algebraic iff the set of its finite branches is a deterministic language. The interreducibility of the two equivalence problems for schemes and DPDA's follows.

**Résumé :**

Les problèmes de l'équivalence des schémas récursifs non interprétés et des automates à pile déterministes sont réductibles l'un à l'autre. La classe d'équivalence d'un schéma est caractérisée par un arbre infini que le schéma engendre comme une grammaire algébrique (c'est-à-dire "context free") engendre un langage, et qui satisfait les équations du schéma.

Appelons algébriques de tels arbres. Grosso modo, un arbre est algébrique ssi l'ensemble de ses branches finies est un langage déterministe. L'interréductibilité des deux problèmes considérés en résulte.

**Introduction :**

We define recursive schemes and their semantics in §1 following Milner [6]. In §2 we consider a rewriting system associated with a scheme following Nivat [7] or Rosen [8] and state without proof that two schemes are equivalent iff they are tree-equivalent. In §3 we associate a strict deterministic grammar (Harrison and Havel [3]) with a scheme in order to represent by a language the tree it generates. The equivalence problem for schemes reduces to the DPDA problem. In §4 we prove the converse by introducing special strict deterministic grammars which are as powerful as the general ones and represent, up to an isomorphism, a proper subclass of the class of schemes. We conclude in §5 and relate this result to other, open or solved problems.

§1 Recursive schemes

Let $F$ denote the set of *base function symbols* $f, g, h, \dots$ Each $f \in F$ is given together with an integer $\rho(f) \ge 1$ which is called the *arity* of $f$. Let $x_0, x_1, \dots, y, \dots$ denote *individual variables* and $V = \{x_0, x_1, \dots\}$. Let $M(F,V)$ be the set of *finite terms* written with symbols from $F \cup V$ and well-formed with respect to the arities. Example : $t = f(x,g(x,y),h(y,z))$ with $\rho(f) = 3$ and $\rho(g) = \rho(h) = 2$. Let now $\phi = \{\phi_1, \phi_2, \dots, \phi_n\}$ be a finite set of (unknown) *function symbols* with arity $\rho(\phi_i) \ge 1$ for $1 \le i \le n$.

A *recursive scheme* (or *scheme* for short) on $F \cup \phi$ is a system of $n$ equations :

$$ \Sigma = \left\{ \begin{array}{l} \vdots \\ \phi_i(x_1, \dots, x_{i-1}, x_{i+1}) = t_i \\ \vdots \\ \phi_i(x_1, \dots, x_{i-1}, x_i) = t_i \end{array} \right. $$
where for $1 \le i \le n$, $t_i = \rho(\phi_i)$, $t_i \in M(Fu\Phi, V)$ and is of the form $f(t'_1, ..., t'_k)$ for some $f \in F$. No other individual variables than $x_1, ..., x_n$ may appear in $t_i$.

We define now the semantics of our program schemes. Different notions of domains are available to us : **discrete domains** as in Nivat [7], **complete lattices** as in Scott [10], **complete partial orders** (for short c.p.o.) as in Milner [6]. We will choose this last possibility. For discussion about discrete domains see our conclusion. We prefer c.p.o. to complete lattices because they are much easier to work with. See also [11] for a discussion of this problem.

**Definition:** An *interpretation* for $\mathbb{F}$ is an object

$I = \langle D, \perp, \leq, \mathbb{F} \text{ for every } f \in \mathbb{F} \rangle$ where

i) $D$ is a set called the **domain** of $I$,

ii) $\leq$ is an order relation, $\perp$ is the least element of $D$ and $\leq$ is complete i.e every countable chain $A = \{a_1, a_2, ...\}$ (i.e $a_1 \leq a_2 \leq ... \leq a_n$ ...) of elements of $D$ has a least upper bound denoted $\bigcup A$.

(Complete partial orders are such $<D, \perp, \le>$.)

iii) for $f \in \mathbb{F}$, $\bar{f}$ is a mapping $D^{\rho(f)} \to D$ which is continuous i.e $\bar{f}(\bigcup k_i, ... , \bigcup x_n) = \bigcup f(x_1, ..., x_n)$.

If $D$ and $D'$ are c.p.o's, we denote by $[D \to D']$ the set of continuous functions from $D$ to $D'$. We order this set by $f \leq'' f'$ iff $\forall d \in D$, $f(d) \leq' f(d')$. We denote also by $\perp''$ the function $\lambda d(\perp)$.

**Lemma (Milner [6]):** If $<D, \leq, \perp>$ and $<D', \leq', \perp>$ are c.p.o's, then $<[D \to D']$, $\leq', \perp>$ and $<D \times D'$, $\leq x \leq'$, $(\perp, \perp')$ are c.p.o's.

Let $I$ be an *interpretation* for a scheme $\Sigma$ with unknown functions $\phi_1, ..., \phi_n$. Let $\Delta$ be $[D_1 \to D] \times [D_2 \to D] \times ... \times [D_n \to D]$ where $D$ is the domain of $I$ and $k_i = \rho(\phi_i)$ for $1 \le i \le n$. Then $\Sigma$ defines a mapping $\hat{\Sigma}$ from $\Delta \to \Delta$ which is continuous (see [6]) and has a least fix-point in $\Delta$ which is $\bigcup_{n \ge 0} \Sigma^n(\perp_\Delta)$. For $1 \le i \le n$, we take $\phi_i^I = (\bigcup_{n \ge 0} \Sigma^n(\perp_\Delta))_i \in [D_i \to D]$.

We sometimes call scheme a pair $(\Sigma, \phi)$ of a system $\Sigma$ and a function $\phi$ defined by $\Sigma$.

Two schemes $(\Sigma, \phi)$ and $(\Sigma', \phi')$ are equivalent if for every interpretation $I$, $\phi = \phi^I$; we note this relation $\phi = \phi'$, the reference to $\Sigma$ and $\Sigma'$ being understood.

## §2 Schemes as rewriting systems

We give now a characterization of the equivalence of schemes which will be more informative and manageable than the definition. We consider a scheme $\Sigma$ as a **rewriting system** (this approach arises from [7], [2], and [8]). Take for instance $(\Sigma, \phi)$ where

$$ \Sigma = \begin{cases} \phi(x,y) = g(x,\phi(y,\Psi(x)),\Psi(y)) \\ \Psi(x) = f(x,\phi(x,x)) \end{cases} $$

Starting with $\phi(x,y)$ which we write as a tree : $x \uparrow y^\phi$, and rewriting successively $\phi$ and $\Psi$ according to $\Sigma$, we get the following sequence of terms :

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

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

Note that such a function is monotone, i.e $d_1 \le d'_1, ..., d_k \le d'_k$ implies $f(d_1, ..., d_k) \le f(d'_1, ..., d'_k)$.
iii) for any $\alpha\beta$ in L and $b \equiv a \pmod{\pi}$, there exists some $\alpha\beta'$ in L.

**Sketch of proof** : Necessity clearly follows from our recursive definition of $B(t)$. One proves sufficiency by induction on $h(L) = $ the length of the longest word in L.

If $t$ is an infinite but locally finite tree (i.e through any node passes at least one finite branch from root to a leaf) lemma 1 is still true. For arbitrary infinite trees we need something like the set of all prefices of all branches. Let $Z(F) = \{f_o/f\epsilon F\}$. For $t\in T_n$, let $A_o(t) \subset W(F)^*Z(F)$ be the set of $\alpha f_o$ such that $\alpha f_1$ is left factor of some (may be infinite) branch of $t$. Let $A(t) = A_o(t) \cup B(t)$ and $A_i(t) \subset W(F)$ for $1\le i\le n$ such that $B(t) = \left[\begin{array}{c} n \\ i \end{array}\right] A_i(t)x_i$. Two examples will clarify these definitions :

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

belong to $T_2$. Then $B(t) = \emptyset$ and $A(t) = A_o(t) = f_1^*f_o$. On the other hand, $A_1(t') = g_2^*g_1f_1$, $A_2(t') = \emptyset$, $B(t) = g_2^*g_1f_1x_1$ and $A_o(t) = g_2^*g_o + g_2^*g_1f_o$. Hence $A(t) = g_2^*(g_1f_1x_1 + g_o + g_1f_o)$.

**Lemma 1**' : For any $t$ and $t'$, $t = t'$ iff $A(t) = A(t')$

By taking the partition $\pi$ on $W(F) \cup Z(F) \cup V$ defined by $a \equiv b \pmod{\pi}$ iff $a = b$ or $a = f_i$ and $b = f_j$ and $Z(F) \cup V$ instead of $V$, the three conditions of lemma 2 characterize the languages $A(t)$. (We will refer to this result as lemma 2').

**Lemma 3** : If $t \in T_n$ and $t_1, \dots, t_n \in T_m$, then $A(t(t_1, \dots, t_n)) = A_o(t) + A_1(t)A(t_1) + \dots + A_n(t)A(t_n)$.

This lemma allows us to construct a grammar which generates $A(\phi)$. We take first an example.

$$ \text{Let } \Sigma = \left\{ \begin{array}{l} \phi(x_1, x_2) = f(x_1, \phi(x_2, \psi(x_1))) \\ \psi(x_1) = g(x_1, \phi(x_1, h(x_1))) \end{array} \right. $$

Let $\phi$ and $\psi$ denote a solution of $\Sigma$. Let $\phi_i = A_i(\phi)$ for $i = 0,1,2$ and $\psi_i = A_i(\psi)$ for $i = 0,1$. Then by using lemma 3 we get the following equations :

$$ \left\{ \begin{array}{l} \phi_o + \phi_1 x_1 + \phi_2 x_2 = f_o + f_1 x_1 + f_2 \phi_o + f_2 \phi_1 x_2 + f_2 \phi_2 \psi_o + f_2 \phi_2 \psi_1 x_1 \\ \psi_o + \psi_1 x_1 = g_o + g_1 x_1 + g_2 \phi_o + g_2 \phi_1 x_1 + g_2 \phi_2 h_o + g_2 \phi_2 h_1 x_1 \end{array} \right. $$

According to the definitions of $A_i(\phi)$ and $A_i(\psi)$, they split :

$$ G(\Sigma) = \left\{ \begin{array}{l} \phi_o = f_o + f_2 \phi_o + f_2 \phi_2 \phi_o \\ \phi_1 = f_1 + f_2 \phi_2 \psi_1 \\ \phi_2 = f_2 \phi_1 \\ \psi_o = g_o + g_2 \phi_o + g_2 \phi_2 h_o \\ \psi_1 = g_1 + g_2 \phi_1 + g_2 \phi_2 h_1 \end{array} \right. $$

We know that such a system has one and only one solution in $(W(F) \cup Z(F))^*$, which consists of the languages generated by $\phi_o, \phi_1, \phi_2, \psi_o, \psi_1$ and production rules

$$ \{ \phi_o \to f_o, \phi_o \to f_2 \phi_o, \phi_o \to f_2 \phi_2 \phi_o, \phi_1 \to f_1, \dots \} $$
From now on, a context-free grammar will be considered either as a set of production rules
{$S_1 \to m_{11}$, $S_1 \to m_{12}$, $S_2 \to m_{21}$, ...} or as a system of equations {$S_1 = m_{11} + m_{12}$, $S_2 = m_{21} + ...$}.
We define now $G(\Sigma, \phi)$ in the general case.

Let $\Sigma = \langle \phi_i(x_1, \dots, x_{k_i}) \mid t_i, 1 \le i \le n \rangle$ be a scheme and $\phi = \{\phi_1, \dots, \phi_n\}$. Take $N = |\Sigma| \cup W(\phi)$ as set of non-terminal symbols, $Z(F) \cup W(F) \cup \{x_1, \dots, x_M\}$ (where $M = \max\{k_i\}$) as terminal alphabet. Define now $G(\Sigma)$ as the set of equations $\phi_i, j = \sum A_j(t_i)$ for $1 \le i \le n$ and $0 \le j \le k_i = \rho(\phi_i)^j$. Take as axiom $S$ with equation
$$S = \sum A_j(\phi_i(x_1, \dots, x_{k_i})) \text{. Then } A(T(\sum A_j(\phi_i(x_1, \dots, x_{k_i}))) = L(G(\Sigma), S).$$

From the unicity of the solution of a context-free grammar and Lemma 2', the second part of theorem 2 is proved. As we are interested in the equivalence problem, we will investigate now more closely the grammars which are associated to schemes. We will use the notion of *strict deterministic grammar* introduced by Harrison and Havel [3]. Consider the following properties of a context-free grammar $G(N,X,S)$ given with a partition $\pi$ of XUN :

A) If $\theta \in \pi$, then $\theta \subset X$ or $\theta \subset N$.

B) $\{S\} \in \pi$

C) $G$ is reduced and $\epsilon$-free,

D) for any two rules $S \to \alpha\beta$ and $S' \to \alpha\beta'$ such that $S \equiv S'$ (mod $\pi$), then

i) either $\beta = 1$, $\beta' = 1$ and $S = S'$,

ii) or $\beta \neq 1$, $\beta' \neq 1$ and $\binom{1}{0} \beta \equiv \binom{1}{0} \beta'$ (mod $\pi$).

E) for any rule $S \to \alpha T\beta$ and $T' \in XUN$ such that $T \equiv T'$ (mod $\pi$), there exists a rule $S' \to \alpha T'\beta'$ such that $S \equiv S'$ (mod $\pi$).

**Definition:** $G$ is _strict deterministic for_ $\pi$ (SD for short) iff it satisfies A, D and $X \in \pi$. $G$ is _super strict deterministic for_ $\pi$ (SSD for short) iff it satisfies conditions A to E. Harrison and Havel only introduced SD grammars. From this definition, it is clear that a SSD grammar is SD. We will prove later that SSD grammars are as powerful as SD grammars.

**Lemma 4 (Harrison [4]):** *A SD grammar is LR(o)*

**Theorem 3:** *Given $(\Sigma, \phi)$ and $(\Sigma', \phi')$ one can construct LR(o) grammars $G$ and $G'$ such that $\phi \equiv \phi'$ iff* $L(G) = L(G')$.

**Proof:** From Lemma 2', $G(\Sigma)$ and $G'(\Sigma)$ are easily seen to be SD for the partition $\pi$ of the set of nonterminals defined by $\phi_{i,j} \equiv \phi_{i,j'}$ (mod $\pi$) iff $i = i'$. They are LR(o) from Lemma 4 and $\phi \equiv \phi'$ iff $L(G) = L(G')$ from Lemma 1'.

We introduce now a class of schemes for which the grammar $G(\Sigma)$ can be replaced by a much simpler one.

**Definition:** A scheme $(\Sigma, \psi)$ is *acceptable* if for any $\phi \in \phi$, there exists $1 \le i \le \rho(\phi)$ such that $A_i(\phi) \ne \emptyset$.

**Lemma 5:** *If $(\Sigma, \phi)$ and $(\Sigma', \phi')$ are acceptable, then $\phi \equiv \phi'$ iff $B(\phi) = B(\phi')$.*

**Sketch of proof:** $\phi \equiv \phi'$ implies $B(\phi) = B(\phi')$. As $\Sigma$ is acceptable, for any $\psi \in \phi$, $A(\psi) = \{\alpha f_o / \alpha \in W(F)^*$, $f \in F$ and $\alpha f_l \in B(\psi)\}$. Hence $B(\phi) = B(\phi')$ implies $A(\phi) = A(\phi')$ and $\phi \equiv \phi'$ from Lemma 1. QED.

In fact, acceptable schemes generate locally finite trees for which lemma 1 is still true.

Given $(\Sigma, \phi_1)$ one constructs now a grammar $G'(\Sigma)$ which will generate $B(\phi_1)$. Let $\Sigma = \langle \phi_i(x_1, \dots, x_{k_i}) \mid t_i, 1 \le i \le n \rangle$. We take $W(\phi)$ as nonterminal alphabet and $W(F) \cup \{x_1, \dots, x_M\}$ as terminal one. $G'(\Sigma)$ consists of the set of equations $\phi_i, j = \sum A_j(t_i)$ for $1 \le i \le n$ and $1 \le j \le k_i$ and $S' = \sum \phi_1, \dots, \phi_{k_1}$ for $1 \le i_1 \le \dots \le i_k \le k_1$.

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

For any set of words $A = \{m_1, \dots, m_k\}$, $\Sigma A$ means $m_1 + \dots + m_k$.
Take for example the same scheme $\Sigma$ as before. Then

$$ G'(\Sigma) = \left\{ \begin{array}{l} \phi_1 = f_1 + f_2\phi_2\psi_1 \\ \phi_2 = f_2\phi_1 \\ \psi_1 = g_1 + g_2\phi_1 + g_2\phi_2h_1 \end{array} \right. $$

The language $B(\phi)$ is generated by $S'$ with $S' = \phi_1 x + \phi_2 y$.

If $\Sigma$ is acceptable and each $\phi$ is monadic, then $G'(\Sigma)$ is a simple deterministic grammar, and the equivalence problem is decidable. This case has been already studied in [1].

We have introduced SSD grammars in order to characterize grammars of the form $G'(\Sigma)$ up to an isomorphism. Let $\pi$ be the partition on $W(\phi) \cup W(F) \cup \{x_1, \dots, x_M\}$ defined by $a \equiv b \pmod \pi$ iff $a = b$ or $a = f_i$ and $b = f_j$ for some $f \in F$ or $a = \phi_{k,i}$ and $b = \phi_{k,j}$ for some $\phi_k \in \Phi$.

Conversely, if $\pi$ is a partition of a finite set $X$, we define a set of base function symbols $F_{\pi,X} = \{\theta \in \pi \mid \rho(\theta) = |\theta|\}$.

We can now state:

**Lemma 6** : For any acceptable scheme $(\Sigma, \phi)$, $G'(\Sigma)$ is SSD for partition $\pi$. Conversely, if $G(N,X,S)$ is SSD for $\pi$, one can construct $(\Sigma, \phi)$ on base function set $F_{\pi,X}$ with $\rho(\phi) = 1$ such that $L(G,S) = A_1(\phi)$.

*Proof* : The first part is clear from the definition of $G'(\Sigma)$, lemma 2 and the definition of SSD grammars. Conversely, given $G(N,X,S)$, one takes $\phi = \{\phi \in \pi \mid \phi \subset N\}$ and $\rho(\phi) = |\phi|$. From lemma 2 and the fact that $G(N,X,S)$ is SSD one easily constructs $(\Sigma, \phi_1)$ such that $G'(\Sigma) = G(N,X,S)$ with $\phi_1 = \{S\}$.

*Example* : Let $N = \{R, R', T, T', S\}$, $X = \{a, a', b, b', c\}$ and $G(N, X, S)$ be the grammar :

$$ \left\{ \begin{array}{l} S = aT + aT' + a'R + a'R'c \\ R = a + a'Ra'T' + a'R'c \\ R' = a'Ra + a'Ra'T \\ T = bR + bR' + b'a \\ T' = b'a'S. \end{array} \right. $$

and $\pi = \{(R, R')\}, \{T, T'\}, \{S\}, \{a, a'\}, \{b, b'\}, \{c\}$.

One easily sees that $G(N,X,S)$ is SSD for $\pi$. In order to construct $\Sigma$, we take $\phi = \{\phi_S, \phi_{RR'}, \phi_{TT'}\}$ and $F = \{f_{aa'}, f_{bb'}, f_{c}\}$. Let now $(\Sigma, \phi_S)$ be the scheme :

$$ \Sigma \left\{ \begin{array}{l} \phi_S(x_1) = f_{aa'}(\phi_{TT'}(x_1, x_1), \phi_{RR'}(x_1, f_c(x_1))) \\ \phi_{RR'}(x_1, x_2) = f_{aa'}(x_1, \phi_{RR'}(f_{aa'}(x_2, \phi_{TT'}(x_2, x_1))), f_c(x_1))) \\ \phi_{TT'}(x_1, x_2) = f_{bb'}(\phi_{RR'}(x_1, x_1), f_{aa'}(x_1, \phi_S(x_2))) \end{array} \right. $$

If we take $R = \phi_{RR'}$, $R' = \phi_{RR'}$, $\dots, a = f_{aa'}$, etc then $G(N,X,S) = G'(\Sigma)$.

### §4 DPDA problem reduces to the equivalence problem for schemes.

Let us first recall the following theorem (see [3] and [4] for the proof).

**Theorem** : Each problem of the following list reduces to the other ones :

1) Equivalence of SD grammars,

2) equivalence of LR(k) grammars for each k,

3) $N(A) = N(A')$ for any two DPDA's,

4) $T(A) = T(A')$ for any two DPDA's.
As these problems are equivalent (i.e interreducible) we can call any one of them the DPDA problem. One does not know whether this problem is decidable or not, but it is interesting to know which problems are as difficult to solve. It may suggest new ways of attacking it. In the last section, we have proved that the equivalence for schemes reduces to the DPDA problem. We shall prove now the converse reduction which will follow from

**Theorem 4** : For any two DPDA's $A$ and $A'$, one can construct acceptable schemes $(\Sigma, \phi)$ and $(\Sigma', \phi')$ such that $N(A) = N(A')$ iff $\phi \equiv \phi'$.

We use a three-step construction :

**Step 1** : given $A, A'$ we construct $\underline{A}, \underline{A}'$ such that $N(\underline{A}) = N(A')$ iff $N(\underline{A}) = N(\underline{A}')$

**Step 2** : From $\underline{A}$ we construct a SSD grammar $G$ such that $L(G) = N(\underline{A})$.

**Step 3** : From $G$ we construct an acceptable scheme $(\Sigma, \phi(x_1))$ such that $A_1(\phi) = L(G)$ just by using lemma 6.

It follows from Lemma 5 that $\phi \equiv \phi'$ iff $N(A) = N(A')$ (if $\phi'$ is constructed in the same way from $\underline{A}$'). We describe now step one.

To each prefix-free language over some finite linearly ordered alphabet $X$ we can associate a tree in a natural way : for example if $L = \{aa, aba, abb, bab\}$, then we get

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

Label each node with the set of labels of arcs going from it and leafs by $x$.

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

Take $F = \{(a,b), \{a\}, \{b\}\}$ with $\rho(\{(a,b)\}) = 2$, $\rho(\{a\}) = \rho(\{b\}) = 1$. This tree is an element of $M(F, \{x\})$.

If $L$ is infinite we get an element $T(L)$ of $T_1$. It is locally finite and hence, characterized by $\underline{L} = A_1(T(L))$ which is not exactly $L$. If $L = N(A)$, we shall construct $\underline{A}$ in such a way that $N(\underline{A}) = \underline{L}$. The second and third step will produce $(\Sigma, \phi)$ such that $T(\Sigma, \phi) = T(L)$.

We define now formally the language $\underline{L}$. Let $X$ be a finite alphabet. An arbitrary but fixed linear ordering of $X$ will be given. Let $\underline{X} = \{(a,\alpha) / a \in \alpha < X\}$.

If $L \subset X^*$, we define $\sigma_L : X^* \to 2^X$ by $\sigma_L(w) = \{a \in X / \exists w' \in X^*, waw' \in L\}$. To every word $w = a_1...a_n$ in $L$, we associate $\underline{w} = b_1...b_n$ in $X^*$ such that for $1 \le j \le n$, $b_j = (a_j, \sigma_L(a_1...a_{j-1}))$. Going back to the example, $\underline{aba} = (a, \{a,b\})(b, \{a,b\})(a, \{a,b\})$ and $\underline{bab} = (b, \{a,b\})(a, \{a\})(b, \{b\})$.

Let $\underline{L} = \{\underline{w} \in \underline{X}^* / w \in L\}$.

Let now $F_X = \{\alpha \subset X / \alpha \ne \emptyset\}$ and $\rho(\alpha) = |\alpha|$. Let $\mu$ be the one-one mapping from $W(F_X)$ to $X$ such that $\mu(\alpha_i) = (a_i, \alpha)$ iff $a$ is the $i^{th}$ element of $\alpha$ according to the ordering of $X$.

It is now clear that $\underline{L} = \mu(A_1(T(L)))$. From now on we omit the mapping $\mu$.
In order to do the first step of our proof, we recall some definitions and conventions about DPDA's.
A DPDA in an object $A = \langle X, K, \Gamma, \delta, q^0, Z^0, F \rangle$ (input alphabet, states, pushdown symbols, transition function, initial state, initial pushdown symbol, final states). The transition function $\delta$ is a partial function from $K_x(X \cup \{\epsilon\}) \times \Gamma$ to $K \times \Gamma^*$ such that for $a \in X$, $\delta(q, a, Z)$ and $\delta(q, \epsilon, Z)$ are not together defined. A configuration of $A$ is an element of $K \times \Gamma^* \times \Gamma^*$; an initial configuration is any of the form $(q^0, u, z^0)$; in a current configuration $(q, u, Z_m)$ we write the top symbol of the stack on the left and call $(q, Z)$ the mode of the configuration; we call $(q, Z)$ a reading mode ($\epsilon$-mode) iff $\delta(q, a, Z)$ is defined for some $a \in X$ (for $a = \epsilon$). Between configurations, we define the relation $c \prec c'$ by $(q, u, Z_m) \prec (q', u', m')$ iff $\delta(q, a, Z) = (q', m')$, $m' = m'm$, $a \in X$ implies $u = au'$ and $a = \epsilon$ implies $u = u'$. We denote by $\delta^*$ the transitive and reflexive closure of $\prec$.

The deterministic prefix free languages (PFDet for short) are the sets $N(A) = \{u \in X^* / \exists q \in K(q^0, u, Z^0) \delta^*(q, 1, 1)\}$.

The deterministic languages are the sets $T(A) = \{u \in X^* / \exists q \in F \text{ and } m \in \Gamma^* (q^0, u, Z^0) \delta^*(q, 1, m)\}$

**Lemma 7:** Let $L = N(A_O) \subset X^*$ a PFDet language. One can construct a DPDA $A = \langle X, K, \Gamma, \delta, q^0, Z^0, q^f \rangle$ such that :

$i) L = N(A)$,

ii) if $\delta(q, \epsilon, Z)$ is defined, then $\delta(q, \epsilon, Z) = (q', 1)$ for some $q' \in K$,

iii) if $(q^0, u, Z^0) \stackrel{*}{\prec} (q, 1, m)$ there exists $v \in X^*$ such that $(q, v, m) \stackrel{*}{\prec} (q^f, 1, 1)$.

Notice that if $m = 1$ in condition iii), we have $q = q^f$.

**Proof:** By adding a bottom stack symbol, one can build from $A_O$ a DPDA $A_1$ such that $(q^0, u, Z^0) \stackrel{*}{\prec} (q, v, 1)$ implies $q = q^f$ and $N(A_1) = N(A_O)$. We construct now $A_2$ from $A_1$ by modifying the transition function $\delta$ of $A_1$ in such a way that $N(A_2) = N(A_1)$ and $A_2$ satisfies ii). For any $\epsilon$-mode $(q, Z)$ such that $\delta(q, \epsilon, Z) = (q, 1, m)$ and $m \neq 1$

either i) for some $q' \in K$, $(q, 1, Z) \stackrel{*}{\prec} (q', 1, 1)$, then take $\delta(q, \epsilon, Z) = (q', 1)$,

either ii) for some $q' \in K$ and $Z'm \in \Gamma^+$ such that $(q', Z')$ is a reading mode $(q, 1, Z) \stackrel{*}{\prec} (q', 1, Z'm')$, then take $\delta(q, \epsilon, Z) = \emptyset$ and, for $a \in X$, $\delta(q, a, Z) = (q'', m''m')$ whenever $\delta(q', a, Z') = (q'', m'')$,

iii) neither of i) and ii) occur, then put $\delta(q, \epsilon, Z) = \emptyset$.

(Note that one can decide which of these cases occur. See [5]).

We construct now $A$ from $A_2$ such that $N(A) = N(A_2)$, ii) is still true and iii) is satisfied; we do this by extending the pushdown alphabet in such a way that we know just by looking at the mode whether the stack can be emptied or not.

Formally, we take $K$ as new pushdown alphabet and will define $\delta$ in such a way that any attainable configuration is of the form $(q_1, u, [Q_1, Z_1, Q_2], [Q_2, Z_2, Q_3], \dots, [Q_k, Z_k, \{q^f\}])$

where i) for $1 \le i \le k$, $Q_i \ne \emptyset$

ii) $Q_1 = \{q \in K / \exists v \in X^*(q, v, Z_1, \dots, Z_k) \stackrel{*}{\prec} A_2 (q^f, 1, 1)\}$

For any $Z \in \Gamma$ and $Q \in 2^K$, define $F(Z, Q) = \{q \in K / \exists u \in X^* \exists q' \in Q, (q, u, Z) \stackrel{*}{\prec} A_2 (q', 1, 1)\}$.

This function is computable. See [5]. We define the transition function $\delta'$ of $A$ in terms of $\delta$, the one of $A_2$. For $a \in X_u(\epsilon)$, $\delta'(q, a, [Q, Z, Q']) = (q', 1)$ iff $\delta(q, a, Z) = (q', 1)$ and $q' \in Q'$. For $a \in X$, then $\delta'(q, a, [Q, Z, Q']) = (p, [Q_1, Z_1, Q_2], [Q_2, Z_2, Q_3], \dots, [Q_1, Z_1, Q'])$ iff $\delta(q, a, Z) = (p, Z_1, \dots, Z_1)$, $p \in Q_1$, $Q_1 = F(Z_1, Q') \ne \emptyset$, and for $1 \le i \le 1-1$, $Q_i = F(Z_i, Q_{i+1}) \ne \emptyset$.

We take $[Q_o, Z^o, \{q^f\}]$ as a new initial pushdown symbol with $Q_o = F(Z^o, \{q^f\})$. It is easy to check that $A$ satisfies the required conditions. QED.

**Proposition 1:** Given a PFDet language $L$, one can construct a DPDA $A$ such that $N(A) = L$ and $A$ satisfies the conditions of Lemma 7.

**Proof:** Let $L = N(A)$ for some DPDA $A$ satisfying lemma 7. We define $\underline{A} = \langle X, K, \Gamma, \delta, q^0, Z^0, q^f \rangle$ from $A$ by taking

i) $\underline{\delta}(q, \epsilon, Z) = \delta(q, \epsilon, Z)$

ii) $\underline{\delta}(q, (a, \alpha), Z) = \delta(q, a, Z)$ iff $\alpha = \alpha_{q, Z} = \{b \in X / \delta(q, b, Z) \text{ is defined}\}$,

iii) $\underline{\delta}$ is undefined in all other cases.
**Observation 1** : If $(q^0, u, Z^0)^* \tilde{A}^* (q, 1, m)$ and $(q, Z)$ is a reading mode, then $\alpha_{q, Z} = \sigma_L(u)$. This is true from the fact that $A$ satisfies condition iii of lemma 7.

We can prove now that $\underline{L} = N(\underline{A})$. Let $w = a_1...a_1$ belong to $N(A)$ and $(c_j)_{0 \le j \le 1}$ be the corresponding computation of $A$. Let $\underline{w} = b_1...b_1$. If $c_j = (q, a_i...a_1, m)$ define $\underline{c}_j = (q, b_1...b_1, m)$. We prove by induction on $j$ that for $0 \le j \le 1$, $\underline{c}_0^* \underline{A}^* \underline{c}_j$.

It is clear for $j = 0$. If $c_j \underline{A}^* c_{j+1}$ is an $\epsilon$-transition then $\underline{c}_j \underline{A}^* \underline{c}_{j+1}$ is an $\epsilon$-transition of $\underline{A}$. If not, $c_j = (q, a, u, m)$ and $c_{j+1} = (q', u, m')$ with $w = \text{vau}$ for some $v \in X^*$. Then $\underline{c}_j = (q, (a, \alpha)u, m)$ with $\alpha = \sigma_L(v)$. From observation 1 and the definition of $\underline{A}$ we get $\underline{c}_j \underline{A}^* \underline{c}_{j+1} = (q', u', m')$. Hence $\underline{L} \subseteq N(\underline{a})$.

Now let $b_1...b_1$ be in $N(\underline{A})$ and $(c'_j)_{0 \le j \le 1}$ be the corresponding $\underline{A}$-computation. Let $c_j = (q, a_i...a_1, m)$, if $c'_j = (q, b_i...b_1, m)$ and $a_i'$ is the first component of $b_i'$, for $i \le i' \le 1$. By induction on $j$, one sees that $\underline{c}_0^* \underline{A}^* \underline{c}_j$ and for $0 \le i \le 1$, $a_i = (b_i, \sigma_L(a_1...a_{i-1}))$ that is $b_1...b_1 = \underline{a}_1...\underline{a}_1$ and $N(\underline{A}) \subseteq \underline{L}$. QED.

The same proof shows that if $\underline{L}$ is simple deterministic (regular) then $\underline{L}$ is simple deterministic (regular). But if $\underline{L} = \{w \in \underline{w}^c / w \in \{a, b\}^*\}$ which is context-free, prefix-free nondeterministic, then $\underline{L}$ is **not context-free**.
We begin now the second step of the proof of theorem 4.

We define on $Y = \underline{X}$ a partition $\pi$ by the following equivalence relation : $(a, \alpha) \equiv (b, \beta)$ iff $\alpha = \beta$.

**Proposition 2** : Let $\underline{L}$ be a PFDet language. One can construct a SSD grammar $G$ for the partition $\pi$ of $\underline{X}$ such that $\underline{L}(G) = \underline{L}$.

**Proof** : One constructs $G$ from the automaton $B = \underline{A} = \langle Y, K, \Gamma, \delta, q^0, Z^0, q^f \rangle$ obtained in Proposition 1. Note that $B$ satisfies the three conditions of lemma 7 and the following one
iv) $\forall a, b \in Y, \delta(q, a, Z)$ and $\delta(q, b, Z)$ are both defined iff $a \equiv b \pmod \pi$.

Let $G_o$ be the canonical grammar of $B$ (see [3]) which is intended to generate $N(B)$ by taking
1) $Y$ as terminal alphabet,

2) $N_o = K \times \Gamma \times K$ as non-terminal alphabet (we denote its elements by $\overline{qZq'}$),

3) $q^0Z^0q^f$ as axiom,

4) a set $P_o$ of production rules consisting of

$\overline{qZq'} \rightarrow$ a whenever $\delta(q, a, Z) = (q', 1)$,

$\overline{qZq'} \rightarrow$ 1 whenever $\delta(q, \epsilon, Z) = (q', 1)$,

$\overline{qZq'} \rightarrow$ a $\overline{pZ_1q_1}$ $\overline{q_1Z_2q_2}$ $\dots$ $\overline{q_{k-1}Z_kq'}$ whenever $\delta(q, a, Z) = (p, Z_1 \dots Z_k)$ and $q_1, \dots, q_{k-1} \in K$.

Let $f : N_o^* \rightarrow \Gamma^*$ be the homomorphism defined by $f(\overline{qZq'}) = Z$. Let $H(p, q) = \{\overline{pZ_1q_1} \overline{q_1Z_2q_2} \dots \overline{q_kZ_{k+1}q} / k \ge 0, Z_i \in \Gamma \text{ and } q_i \in K\}$. The following lemma shows how $G_o$ simulates $B$.

**Lemma 8** : For any $u \in X^*, q, q' \in K, Z \in \Gamma$ and $\alpha \in N_o^+$, then

i) $\overline{qZq'} \xrightarrow{\underline{\underline{\underline{\underline{\gamma}}}}} u \alpha$ iff $\exists p \in K$ such that $\alpha \in H(p, q')$ and $(q, u, Z) \xrightarrow{\underline{\underline{\underline{\underline{\gamma}}}}} (p, 1, f(\alpha))$ ($\xrightarrow{\underline{\underline{\underline{\underline{\gamma}}}}} L$ means left-most derivation)

ii) $\overline{qZq'} \xrightarrow{\underline{\underline{\underline{\underline{\gamma}}}}} u$ iff $(q, u, Z) \xrightarrow{\underline{\underline{\underline{\underline{\gamma}}}}} (q', 1, 1)$.

The reader will find a proof of this lemma in Harrison and Havel [3], lemma 3.3. From this lemma we get $N(B) = \underline{L} = L(G_o)$.

**Observation 2** : Given a configuration $(q, u, m)$, there exists at most one configuration $(q', 1, Z'm')$ such that $(q, u, m) \xrightarrow{\underline{\underline{\underline{\underline{\gamma}}}}} (q', 1, Z'm')$ and $(q', Z')$ is a reading mode.

**Observation 3** : If $\overline{qZq'} \rightarrow 1$, there is no other production of form $\overline{qZq''} \rightarrow m$ in $G_o$.

We now transform $G_o$ into a reduced $\epsilon$-free grammar $G$ :

**first step** : for each $\overline{qZq'}$, if $L(G_o, \overline{qZq'}) = \emptyset$ delete from $G_o$ any production which contains $\overline{qZq'}$.

**second step** : for each $\overline{qZq'}$, if for no $u$ and $v \in X^*$ $S_o^* \underline{G_o}^* u \overline{qZq'} v$, delete from $G_o$ any production which contains $\overline{qZq'}$.

**third step** : for each $\overline{qZq'}$ such that $\overline{qZq'} \rightarrow 1$, delete it from $G_o$ and replace $\overline{qZq'}$ by 1 in right handsides of rules of $G_o$.
Now, G is a reduced grammar in Greibach Normal Form which is equivalent to $G_0$. Let $N \subset N_0$ be the set of its non terminals.

Let $\pi$ the partition of $N$ defined by the equivalence relation $\overline{pZp'} \equiv \overline{qRq'}$ iff $p = q$ and $Z = R$. We have already defined the partition $\pi$ on $Y$ and, we just have to prove that $G(N,Y,S_0)$ is SSD for $\pi$.

From observation 3 and the construction of G, G clearly satisfies conditions A and C of the definition of SSD grammars. From lemma 8 ii) and the fact that B satisfies condition iii) of lemma 7, $q^oZ^oq^*_G$ implies $q = q^f$. It means that $\{q^oZ^oq^f\}$ is a class of $\pi$. Hence condition B is satisfied. We check now condition D : let $\overline{qZq'} \to \alpha\beta$ and $\overline{qZq''} \to \alpha\beta'$ belong to P. If $\alpha = 1$ and $\beta = 1$, then $q' = q''$ and $\beta' = 1$ from observation 3. If $\alpha = 1$ and $\beta \neq 1$, then $\beta' \neq 1$ (from the preceding case) and $\beta$ and $\beta'$ begin with conjugate terminal symbols (from condition iv) on B and the construction of G). Assume now that $\alpha \neq 1$. Let $u \in Y^*$ such that $\alpha_A \xrightarrow{u} \alpha$ and $\beta = \overline{pZ'}p' \in N) \beta'$ cannot be 1, else one would have $(q,u,Z) \xrightarrow{\beta} (q'',1,1)$ contradicting observation 2. Then $\beta' = \overline{rZ'}r' \in \overline{rZ'}$ but the same argument yields $(q,u,Z) \xrightarrow{\beta} (r,1,Z''m'')$. As $(r,Z'')$ is not an $\epsilon$-mode and using observation 2 we get $r = p$ and $Z' = Z'',$ which means $(1)_{\beta} = (1)_{\beta'}$. If $\beta = 1$, $\beta'$ must be 1 from the same argument ; lemma 8 yields $(q,u,Z) \xrightarrow{\beta} (q',1,1)$ and $(q,u,Z) \xrightarrow{\beta} (q'',1,1)$ and observation 2 gives $q' = q$". QED.

We check now condition E :

Let $\overline{qZq'} \to \alpha T\beta$ be in P and $T' \equiv T \pmod \pi$ with $T' \neq T$. Assume first that $\alpha \neq 1$ and take $T = \overline{rSr'}$, $T' = \overline{rSr''}$. The given production rule comes from some rule in $P_0$ of the form $\overline{qZq'} \to \alpha' \overline{rSr'} \beta'$ (where $\alpha'$ and $\beta'$ have been reduced through step 3 of the reduction of $G_0$). Let $u \in Y^*$ be derivable from $\alpha' \overline{rSr''}$. Then using lemma 8 and the fact that G is reduced, one can find $v \in Y^*$, $m \in \Gamma^*$ such that $(q^o,vu,Z^o) \xrightarrow{\beta} (q,u,Zm) \xrightarrow{\beta} (r'',1,Z_1...Z_k m)$ with $f(\beta') = Z_1...Z_k$. From condition iii on B, there exists $w$ such that $(r'',w,Z_1...Z_k m) \xrightarrow{\beta} (q^f,1,1)$. Clearly, there exists $r_0,r_1, \dots, r_{k+1}$ in K, $w_1, \dots, w_k$ factors of w such that for $o \le i \le k$, $(r_i, w_{i+1}, Z_{i+1}) \xrightarrow{\beta} (r_{i+1}, 1, 1)$ and $r_0 = r$". Consider now the production rule $\overline{qZr_{k+1}} \to \alpha' \overline{rSr'' r''Z_1 r_1 r_1 Z_2 r_2 \dots r_k Z_k r_{k+1}}$ of $P_0$.

During the first step of the reduction of $G_0$, it cannot be deleted since each of its nonterminals generates a non empty language (clear for those of $\alpha'$ and for $\overline{rSr''}$ from hypothesis, it follows from lemma 8 for the others). It is not deleted during the second step because $(q^o,vuw,Z^o)\xrightarrow{\beta} (q,uw,Zm)\xrightarrow{\beta} (r_{k+1},w',m)\xrightarrow{\beta} (q^f,1,1)$ for some right factor $w'$ of $w$ and lemma 8 gives $\overline{q^oZ^oq^f} \xrightarrow{\beta} \overline{vqZr_{k+1}} w'$.

This production rule can be simplified during the third step of the reduction and becomes $\overline{qZr_{k+1}} \to \alpha \overline{rSr''} \beta''$ which was to be shown. Assume now that $\alpha = 1$. Then $T = a$ and $T' = b$ is some terminal symbol conjugated with a. From condition iv on B (see the beginning of this proof), there exists some transition $\delta(q,b,Z) = (p,Z_1...Z_k)$.

The same argument as before shows that for some $v,w \in Y^*$, $m \in \Gamma^*, (q^o,vbw,Z^o) \xrightarrow{\beta} (q,bw,Zm) \xrightarrow{\beta} (p,w,Z_1...Z_k m)$ \qquad $\xrightarrow{\beta} (q^f,1,1)$. Hence, some production $\overline{qZq''} \to \overline{b\beta}$ belonging to $P_0$ has not been deleted during the two first steps of the reduction. It may have been simplified giving $\overline{qZq''} \to \overline{b\beta''}$ as desired. QED.

We can sum up our results by stating

**Theorem 5** : The following problems are equivalent to the DPDA problem :

i) equivalence of superstrict deterministic grammars,

ii) equivalence of schemes (that is tree-equivalence of [8]),

iii) equivalence of acceptable schemes.

**Remark** : By using the method of §3, one could study the slightly more general class of schemes, such that $\rho(f)$ and $\rho(\phi_i)$ may be 0, and a scheme is any system $\langle\phi_i(x_1, \dots, x_1)\rangle = t_i$, $1 \le i \le n$ such that for $1 \le i \le n$, $t_i \in M(F, \{x_1, \dots, x_1\})$ and $1_i = \rho(\phi_i)$.

Theorem 5 is true for this class of schemes.
§5 Conclusion

As program schemes are intended to represent real programs, it is of interest to interpret base functions as much as possible. But if we interpret too much, decision problems become undecidable. For instance if one decides to interpret base functions as partial mappings from $D^k$ to D (for some domain-set D) and certain 3-adic base functions as conditional operators (that is $g(x,y,z) = \text{if } p(x) \text{ then } y \text{ else } z$), then the equivalence problem becomes undecidable. If one restricts to monadic such schemes (with monadic base functions), the equivalence problem is equivalent to the DPDA problem (E. Friedman [12]).

It is also possible to interpret a little more than we did by using *discrete interpretations* (see Nivat [7]). A discrete interpretation is an interpretation in our sense such that $<D, \leq, \top>$ satisfies $\forall x \forall y, x \leq y \iff x = y$ or $x = \top$.

Let $\equiv_d$ be the equivalence relation between schemes corresponding to discrete interpretations. As before, for schemes $(\Sigma, \phi)$ and $(\Sigma', \phi')$, $T(\Sigma, \phi) = T(\Sigma', \phi')$ implies $\phi \equiv_d \phi'$ but the converse is not true and we cannot reduce the equivalence of schemes to the equivalence of grammars as we did. Other methods must be introduced.

### Acknowledgments :

I express my gratitude to Gilles Kahn and Ronald Rivest for reading the manuscript.

### References :

[1] B. Courcelle, J. Vuillemin : Semantics and Axiomatics of a Simple Recursive Language. Proceedings of 6th Annual ACM Symposium on Computing, Seattle (1974) pp 13-26.

[2] B. Courcelle, J. Vuillemin, M. Nivat : In preparation.

[3] M. Harrison, I. Havel : Simple Deterministic Grammars, in J.C.S.S. (vol 7) n°3 June 1973 pp 237-277.

[4] M. Harrison, I. Havel : On the Parsing of Deterministic Languages, submitted for publication.

[5] J. Hopcroft, J. Ullman : Formal languages and their Relation to Automata, Addison-Wesley, 1969.

[6] R. Milner : Models of LCF. Memo AIM/CS332 Stanford (1973).

[7] M. Nivat : On the Interpretation of Recursive Polyadic Program Schemes, to appear in Atti del Convegno di Informatica Teorica, Roma, 1973.

[8] B. Rosen : Program Equivalence and Context-free Grammars, (revised) IBM Report RC 4822, April 1974.

[9] B. Rosen : Tree Manipulating Systems and Church Rosser Theorems, J.A.C.M. 20 (1973) pp 160-187.

[10] D. Scott : Outline of a Mathematical Theory of Computation, Memo Oxford PRG-2 (1970).

[11] J. Vuillemin : Syntaxe, Sémantique et Axiomatique d'un Langage de Programmation Simple, Thesis to appear.

[12] E. Friedman : Relationships between Monadic Recursion Schemes and Deterministic Context-free Languages. This Symposium.