Let array z of order a x d exist such that, by using column catenation, [mathematical expression not reproducible] for some integers [k.sub.1], [k.sub.2], m, and n.

Two partial arrays A and B of same order are called conjugate if there exist partial arrays X and Y such that A [subset] XY and B [subset] YX using row catenation or column catenation.

If A and B are conjugate, then there exists partial array C such that AC [up arrow] CB, either by column catenation or by row catenation.

Suppose A and B are conjugate and let X, Y be partial arrays such that A [subset] XY and B [subset] YX either by column catenation or by row catenation; then AX [subset] XYX and XB [subset] XYX.

Two partial arrays A and B of same order are k-conjugate, if there exist nonnegative integers [k.sub.1][k.sub.2] whose sum is k and partial arrays X and Y such that [mathematical expression not reproducible] with row or column catenation.

Notice that we do not need all of the information contained in configurations, just those labellings that can be changed by future catenations. By Proposition 7, instead of (x, y) we can consider a reduced configuration defined as a pair [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Another direction for further study is the behaviour of infinite catenations, like the usual infinite word asymptotics (cf.

This paper deals with the problem of making persistent list catenation efficient.

Steques with catenation are the same as stacks with catenation, since catenation makes inject (and push, for that matter) redundant.

Our main result is a real-time, purely functional (and hence confluently persistent) implementation of deques with catenation. Our data structure is both more efficient and simpler than previously proposed structures [Buchsbaum and Tarjan 1995; Driscoll et al.

Section 2 surveys previous work dealing with problems related to that of making lists persistent and adding catenation as an efficient list operation.

Let us put aside catenation for the moment and consider the problem of making noncatenable lists fully persistent.