18—
On the Theory of Relational Structures and Schemata for Parallel Computation:
With A. R. Bednarek (LA-6734-MS, May 1977)

This report is about a combinatorial study of relations between compositions of transformations and "projective algebra" forming foundations of mathematical logic. It also contains proposals to utilize such ideas for parallel computation machines. (Author's note.)

Abstract

This report will outline an area of work which, so far theoretical, will indicate some applications for construction and operation of computers which should be able to perform simultaneous operations, i.e., computations in parallel, particularly as these concern the composition and/or iteration of functions or, more generally, relations.

I—
Introduction

This report will deal with indications of usefulness of parallel and series machines for several areas of mathematical constructions. [For example, such is the case in the Monte Carlo method, where a great number of independent samplings with low or medium arithmetical precision (not requiring very many decimals) may considerably speed

up and enlarge the area of this application. In the Monte Carlo procedures the results are gathered not by a small number of very precise (many digit accuracy) calculations, but rather by obtaining statistics of very many independent or semi-independent histories of typical patterns or processes (to be developed in subsequent paragraphs). Thus, in the study of parabolic differential equations, a method of operating simultaneously on many channels would be useful. Similarly, in the discussion of hyperbolic differential equations or integral equations leading to or equivalent to such, we encounter a similar situation: Outside the cone of influence there is an independent or semi-independent development of disturbances and this can be studied all at once on a one-, three-, or multidimensional grid.]

Given two functions f and g, it would be nice to obtain the function f(g), all at once by a single order, including the case when the two functions are given numerically, graphically, or tabulated. The present machines compose them serially, point by point, with very great speed to be sure. If we had at our disposal a machine combining the digital and analogue features, we could envisage this most important and powerful algorithm of analysis to be effected as fast as possible with only one computer. After all, it is the facility of differentiating a composite function that increases the power of the infinitesimal calculus.

In particular, we outline a method of composing functions and relations, using a novel, parallel, i.e., "all at once" computing scheme. We concern ourselves with a two-track theoretical investigation, namely: (1) studies of the role of composition, particularly as far as its simultaneous or parallel realization is concerned, in mrathematical schemata. Here our concern is to encompass the standard operations of algebra and analysis in terms of composing point or set-valued functions (relations); (2) assuming a mechanism for effecting composition in a nonserial manner, we will study the advantages of such in computer organization, the modelling of neurological like phenomena such as iterative searches, memory building, "pattern recognition," processing of operations of the visual retina, etc.

Prelimlinary engineering studies (at the University of Florida) have established the feasibility of the fabrication of a computational element effecting instantaneous composition using existing solid state technology or some combination of optical and acoustical phenomena. However, our study is restricted to the theoretical imnplications of the existence of such a computer component.

II—
Functional and Relational Composition

We have observed that in some early work of A. Tarski²⁷ there was given a set-theoretic formula for the composition RoS of two relations which involved projections. In particular, RoS={(R x X)n (X x S)} where 7r is the projection 7r(x, y, z) = (x, z). Technically speaking there should be included in the formula the morphisms ((x, y),z) --- (x, y,z) and (x, (y, z)) -+ (x, y, z)). The following schematic should aid in the visualization of this formula.

Subsequent discussions with electrical engineers and materials scientists have established the physical realizability of this operation employing existing solid state technology or some combination of optical and acoustical phenomena in a three-dimensional homogeneous medium. Some such schemata will be discussed in Appendix B.

Motivated by the above, our aim is to study mathematical operations and algorithms which would utilize parallel work and simultaneous operations on computing machines-be it on a single large computer with such facility, or on a number of smaller computers connecting together and operating simultaneously and largely independentlyas far as arithmetical or Boolean operations are concerned. In particular, assuming the facility to effect the operations of composition of functions and relations in a parallel ("all at once") fashion, our concern is to encompass the standard operations of algebra and analysis in terms of composing point or set-valued functions.

In the following section we describe some specific mathematical investigations now under way. In Sec. IV we illustrate some of the possible implications and/or applications of the anticipated results.

III—
Some Studies of Relational Structures

There are basically two directions in our study. The interconnection between composition and projection suggests the first of those, namely, the algebraization of the operations of projection and the construction of product sets. This corresponds to a (finite) model of the logical quantifiers; that is, the "there exists" and the "for all" operators. These, in addition to the usual Boolean and arithmetical orders on present day computers, would enlarge, even though modestly at first, the scope of theoretical mathematical investigations amenable to study on electronic machines. The second direction concerns the operation of composition of functions and transformations and, more generally, the composition of relations. In addition, we propose to study the interrelation of those two approaches-the algebraic and combinatorial properties of these.

Delineated below are some specific researches which we have undertaken.

(a) In Ref. 12 there was initiated the study of projective algebrasan initial step in the development of algebraic versions of logic from which have evolved the cylindric and polyadic algebras. Extending the work in Ref. 12, McKinsey²⁰ showed that every projective algebra was isomorphic to a certain kind of class of binary relations. There are many open problems (see, for example, Ref. 28) concerning these algebras, but in particular we are concerned with those that are isomorphic to specific relation algebras. Recently it has been observed that the projective algebras BN of all binary relations on a finite set can be generated by a single element. We have characterized those algebras corresponding to BN. The "projection" and "direct product" operators in the axiomatization of projective algebras can be replaced by a multiplication (composition). Is it possible to characterize those algebras that may be isomorphic to some class of topological relations; e.g., under suitable conditions, the "clopen" relations on a compact, totally

disconnected space? Do there exist "Stone-type" theorems identifying spaces whose suitably associated algebras are isomorphic? Given a class of subsets, say, for example, in the plane, under what condition can this family be projectively generated? Recently V. Faber and J. Larson¹³ established the existence of a countable collection of sets in the plane that could not be embedded in a finitely generated algebra.

McKinsey²⁰ gave postulates for a calculus of binary relations. We have been able to show that every such structure is a complete atomic projective algebra and, conversely, that there can be introduced into particular, complete atomic projective algebras a multiplication making these algebras of binary relations. This replacement of projections

by a multiplication may result in a more amenable (for machine purposes) model of the first-order predicate calculus.

(b) At the other end of the algebraic spectrum we have started to investigate various semigroups (under composition) of functions or relations. The object of this line of research is to see how much information is carried by the multiplicative structure of the algebras in question; that is, to what extent can the Boolean operations on the objects be supplanted by the multiplicative substitute for the logical quantifiers? The results reported in Refs. 1 and 2 show, for example, that for some classes of spaces, the spaces are determined by these semigroups. In this connection we propose to investigate and extend the results in Refs. 4 and 26 concerning the finite generation of these semigroups. Connected with these problems are questions of the most economical and shortest expressions involving the minimum number of compositions of the base elements to produce all given ones. That such extensions are possible has been confirmed by our recently noticed theorem that all closed relations on the unit interval can be approximated by the composition of three fixed relations.

The applications of such algorithms may be interesting for the study of models of memory building (see Refs. 9 and 21) by constructing trees (with some loops) or coding visual and aural impressions by a process of composing existing codes in the nervous system or memory storage.

(c) Focusing on the operation of composition there is a class of problems concerning fixed points of transformations as well as properties of their iterates.* Given the possibility of simultaneous or parallel effectuation of composition there is open an entire avenue of investigation concerning such questions not only for transformations but for multivalued transformations; that is, relations. As observed in Ref. 28, computations on existing computers are particularly well suited for the display of asymptotic properties of iterates. However, to tabulate only the interesting points it would be preferable to have a visual evaluation of the iterated properties of the many (or all) points. We propose to study the implications of the possibility of nonserial composition for investigations, qualitative as well as quantitative, of fixed-point problems, mixing phenomena in hydrodynamics, topological features of force fields, etc.

(d) Two relations R and S on a set X are product-isomorphic if there exists a bijection ) : X -- X such that the transformation

* Schemata for such were discussed with John Pasta some years ago.

(x,y) -* (/(x), (y)) takes R onto S. Employing composition this is equivalent to R = QoSo°^-1 . Of course the original definition can be extended to n-ary relations. Is there an analogous compositional identity? It was noted in Ref. 28 that the notion of product isomorphism has an interesting relation to isomorphism in certain algebraic structures. In particular, if one associates with a group G the ternary relation {(x, y, z) I xy = z} then two groups are isomorphic if and only if their associated relations are product isomorphic. We propose to investigate the possibility of associating with structures, such as groups, a binary relation (or relations) so that these representations would be product isomorphic. Such representations coupled with the ability to compute rapidly via the compositional identity above would provide a useful tool.

The concept of weakly product-isomorphic²⁸ for binary relations is equivalent to the assertion that R = 'oSoA^-1 for a pair of bijections. Numerous extensions of the above will be investigated. Recent investigations by A. R. Bednarek and Gian-Carlo Rota have revealed a connection between the concepts of weakly product-isomorphic functions or relations and flows.

A more extensive discussion of these concepts and problems is contained in Appendix A.

(e) Another problem to be investigated is that of the classification of "complexity" of sets under the usual operations of the type mentioned earlier; that is, Boolean, projection, and composition. Here we mean "complexity" in the sense defined in the paper by Beyer, Stein, and Ulam.⁵ Also of concern is the relation of this complexity to "entropy" of such sets and the connected combinatorial problems.

(f) As mentioned earlier we have proved recently that all of the closed relations on the unit interval can be "approximated" by three such. Of course this approximation is dependent on the existence of an appropriate metric. In the case in question we used the Hausdorff metric. We are studying the question of possible metrics for various spaces of relations. For example, when there is an underlying metric, as there was above, on the space on which the relations are defined, then the Hausdorff metric is a natural choice. If, however, the subsets (relations) are subsets of a measure space then the Steinhaus distance m(A(A,B))m(A)+ m(B) ' where A denotes the symmetric difference between sets, may be more natural. The particularization of the above (or possible alternatives)

in the case when the underlying space is finite and the relations are therefore directed graphs will be studied.

IV—
Possible Applications of Results on Relational Structures

In this section we wish to indicate some of the directions for possible applications of results realized from the theoretical investigations outlined in Sec. III.

For example, in the last-mentioned item in the preceding section we mentioned the study of possible metrics. In the "recognition" of figures, some kind of "distance" must be used to examine similarity or analogy between them. The nervous-system conversion behind the retina might operate using some schemata involving such abstract distances; see, for example, Ref. 21.

In speculating on how nonserial (parallel) composition might play a role in effecting some of the standard operations of analysis we make the following observation. Suppose X = [a, b] is a real interval LetH = {(x,y) I x >y}CXxX C RxR. Nowiff : X - X, thenthe composition f OH is the set f OH = {(x, y, )I f(x)>y}. Schematically: Given instant composition and, for example, optical display of the same, if the luminosity of A C X x X is A(A), then bA(f H)J, fd^ A(X x X)• Studies concerning the further role of composition in integration (summation) are under way.

In another direction, one can explore the relation of the facility to compose in a nonserial fashion to, among other things, the recent work of N. Metropolis and Gian-Carlo Rota¹⁸ on "significance arithmetic."

We speculate on some of the possible applications to problems of "information retrieval." To make the situation more concrete we employ a simple situation basic to some existing retrieval systems.

First, we assume the existence of a finite collection W = {wk, w2, .., wN of words and a finite collection 1 { = {d _l,d ₂,..., dk} of documents, where each document di is a vertex of the N-dimensional cube; that is, di is a sequence of length N with its jth entry 1 or 0, indicating that word wj occurs or does not occur in the document. Of course we are not here concerned with how such a determination is made. A typical example is "key word in title indexing" of some collection of journal articles with the totality of "key words" constituting the collection W.

Given this situation, immediately there comes to mind two relations D, W, on the sets of documents D and words W, respectively. Namely D C D x D where (di, dj) e D iffdi and dj have a common non-zero entry and W c W x W where (wi,wj) eW iff wi,wj occur together in some document.

Of course the composition D°D[WoW] yields all those pairs of documents [words] that are correlated to a third document [word]; that is, for example, (d, d')eDoD iff there exists a document d* such that (d, d*)eD and (d*, d')eD. The process can be iterated with D^[1 = D, D[² ] = D D and D[^n] = D[^n-1 ] D.

Given a word w*eW, consider the composition Wo(w*,w*)oW which consists of all pairs (w,w') related through w*; that is (w,w') e Wo(w*, w*)oW iff (w, w*) e W and (w*, w') e W. In general, given a subset Wo c W, we let A\w = {(w,w) IweWo}. Then WoAwooW = {(w, w') l there exists a woe W such that (w, wo), (wo, w') e W}.

Given the relations D and W there is much interest in clusters; that is in the maximal complete subgraphs of D and W. Many algorithms exist for the determination of these (Refs. 3, 6, and 23). To our knowledge none of these focuses on composition. What is suggested is, given a reflexive-symmetric relation R on a finite set X, can one find more efficiently those subsets C of X maximal with respect to C x C C R? Similarly, can searches in more sophisticated retrieval systems be conducted more efficiently given the facility to compose relations all at once? What role, if any, does relational composition play in the design of an adaptive retrieval system, that is, one of the form Q x G-— G where the "inputs" are questions and G the "states"are admissible file organizations, with the transition resulting in file reorganizations that take into account the "information" carried by the queries presented?

It appears that some of the lines of research delineated above make contact with the recent work of L. N. Cooper (Refs. 9 and 21) concerning development of feature-detecting cells in visual cortex as well as possible organization of animal memory and learning. These connections were discussed by S. M. Ulam and L. N. Cooper at a recent

meeting on Quantum Biology and it is expected that our researches will result in a strengthening of these connections.

We include here also an account of some work concerning simple preliminary experiments of pattern recognition. These were performed in 1970-71 by Robert Schrandt and Ulam in Los Alamos on one of the Los Alamos Scientific Laboratory computers.

It is proposed to extend these studies on a more general basis using variety of different notions of a metric distance between two sets of points in the plane or between two classes of such sets (or "pictures") on a screen.

It is speculated that analogous schemata may be operating in the nervous system, specifically, in the visual brain, on the layers behind the retina.

As will be seen later, the operation of composition of sets may play a role in the production of "examples" which are variations of one or a few impressions stored in the brain, to be compared with a new impression confronted by the nervous system (or by the computer).

A subsequent report will contain a discussion of distances to be used in purely mathematical investigations concerning the degree of a quantitative measure of analogy or similarity between mathematical structures, i.e., between relation sets, i.e., graphs, groups, and some other mathematical structures. The behavior of such distances as regards relational composition has been studied by A. Bednarek in his work on relation theory.

The following account summarizes work done in 1970-71 in Los Alamos by Robert Schrandt and Ulam.* The computations were done on the CDC 6600. Specifically we experimented with schemata for an automatic recognition by an electronic computer of visual data, i.e., pictures such as presented on a screen or on the retina of an optical system. The idea involves "teaching by examples." The simplest instance considered by us was to present the computer with data describing a handwritten letter "a" in a large number of examples, then present the machine with a number of examples of the letter "b." After this, a letter was written again and the machine was to decide whether it was "a" or "b." The visual system of a living organism contains ways to abstract from size, from translation and from rotations through small angles, at least. We should stress right away that rotations through larger angles, say, 900, are not yielding equivalent impressions, so for example, N and Z are equivalent by a 90^° rotation, but are perceived as different objects. The invariance then obtains

* We want to acknowledge also the interest and helpful suggestions of Professor Jan Mycielski.

only for "group neighborhood" small-angle rotations. A larger class of transformations which does not affect the notion of the same object is, of course, small deformations. [The notion of an object to be perceived, that is to say, a class of two-dimensional sets must involve abstraction from small changes, for the problem of recognition amounts to ways of distinguishing classes of two-dimensional sets when it comes to establishing visual memory (one-dimensional sequences for auditory impression, perhaps three-dimension ones for tactile ones)]. The main tool in our approach is the definition of a distance or, really, several distances between classes of sets. We shall indicate some plausible such metrics and speculate on the way these are coded and registered in the nervous system and the brain. Later on we shall speculate on iteration of such procedures, that is to say, families of classes which we can call ideas or notions of the first order for coding and registering those, etc.

In our simple-minded experiments we attempted to imitate the various versions of a handwritten letter as follows. An example of the letter a was written by hand and the points forming it were registered on a 64 x 64 grid in the computer in such a way that a unit square was touching the extremities of the set. Instead of writing a number of other examples by hand and putting the resulting pictures into the memory of the computer, which would be laborious and timeconsuming, we write down once and for all, two transformations of the unitsquare into itself, call them S and T, which are a little different from identity transformations, and we apply in succession various compositions of these two, obtaining a number of transformations of the given first example. In our case if we wanted, say, 128 examples, we would take all possible compositions of seven transformations S and T, e.g., STSSTST, TTSSTST, etc., each giving an image of the original set. Clearly, if one wanted, say, 1024 examples, we would take compositions of 10 of these transformations. If T and S differ sufficiently little

from the identity, the resulting transformations would be still "small" deformations. We have taken, for T and S, the following: I 1 x' = x + el4y(1 - y)el = - or 1 T 10 16 y' = y + l4x(1 -x) = ~ 2 1 1 S x = x + 2y^e2= 8 or -2 y+ = y + E2³

It was rather surprising to watch the images of the letter a (and similarly for b) as they appeared after these transformations, they gave the

impression of being handwritten, too, sometimes by a shaking hand showing a variety of different styles.

We now want to discuss a way to code numerically each of the resulting sets of points and explain our criteria for comparing a new example with our two sets of examples to decide whether the new picture should belong to the first or to the second set. The unit square is divided successively into four, then 16, then 64.. .subsquares. We denote these by, Qi, Q2, Q3, Q4, then by Qll, Q12, Q13, Q14, Q21Q24,Q23, Q24, ..., and so on. Let Z1, Z₂, ..., ZN be the sets of points corresponding to our examples where N was, say, 128. Given a set Z, we associate with it a sequence of numbers which are binaries in O's and 1's as follows:

In the intersections of Z and Qi we will write a 1 or a 0 depending on whether Z has points in common with this set or not. We continue, in this way, obtaining a sequence of "the characteristic functions of a given set Z."

We shall now consider weights assigned to the successive coordinates of the sequence, giving more importance to the large squares and diminishing it successively for the ones corresponding to the smaller squares. This is to stress the "global" properties of the set Z more than the "smaller details." In our procedure we gave to the four first squares, Qi ... Q4, a weight of 1/4 each, to the next batch a weight of 1/16, and so on. We now assign a distance, p, between two sequences coding the two sets Zi and Zj as follows: If the sequences are X= (X1,2, ..., X128) and = (y1, 2, , Y128) we put P( ) = ^xl - Yl + _. X4 - 4 I 5 - 5 +.. l X128- Y128 4 4 16 128

In this fashion we obtain two finite sets of points A and B corresponding to the examples of the letter a and the letter b, respectively, each a set of 128 points. Given now a "problem," that is to say, a new example of a letter written by hand, we have a single new point p in this metric space.

We can now compute the distances from p to all the points of A and the distance from p to the points of B. If the sum of the distance from p to the points of A is smaller than the sum of the distance from

p to the points of B, the computer decides that "the point p is more like the letter a."

In our experiments we have produced, as problems for the machine, by actual writing, a variety of letters a and b, imitating different styles of handwriting, and obtaining points pl .. .pk. In each case the computer has made a decision whether the letters were a or b. The results were over 80% correct!

The first experiment was based on the rather crude metric pi, defined above.

A more suitable metric, which we shall call p2, would be based on a more precise way of coding the visual picture by a numerical sequence. Instead of merely noting the presence (1) or absence (0) of the given set in any of our squares of the subdivision of the screen, one could write down a real number, S1, 0 < S1< 1, describing the proportion of the number of points in the given set S to the total number of points in the subsquare in question. In this fashion a picture or set Z would be coded by a sequence of real numbers S1, S₂ ,..., SN. Again, one should use weights for the sets of squares-larger ones for the more "global" or "gross" features of the set.

Still another distance, P3, could be defined to correspond to the "Hausdorff" distance between sets. This distance, PH, introduced by Hausdorff, between closed sets A, B in a compact metric space E is defined by PH = Max MinpE(x,y) + Max MinpE(x,y), xeB yeA xeA yeB PE being the metric in E.

In our case PE would be the ordinary (euclidean) distance between the points in our unit square. p3 would be defined by computing the distances between the sets of our two pictures in each of the squares of the subdivision, again giving weights to each square, larger ones to the larger squares, diminishing for the "small detail squares."

Still another distance, P4, would be defined analogously but starting with the "Steinhaus distance" ps instead of the Hausdorff one. The Steinhaus distance between sets A, B is based on the measure (in our case simply the number of points, of course) ps(A,B) =m(A B) m(A)-+-m(B)' A denoting the symmetric difference between the sets A, B.

To obtain p4 we would again compute the distances between the sets in each square of the subdivision separately, keeping track of the weights of the squares as above.

We plan to undertake the corresponding experiments with these "more precise" distances.

Our crude beginning attempts referred to two letters only. For "reading" a text, the computer would have to possess in its memory sets of examples for each letter, of course.

One can now speculate about the building of memory in a living organism--in the nervous system connected to retinal impressions. There might exist a "wiring" system of nerves and their connections behind the retina, allowing us to abstract from orientation, size, translation of the picture presented. In addition, we might perhaps venture to postulate a system of "deformation" of a given picture (object) by a mechanism not unlike our composition of two fixed transformations providing a set of equivalent impressions.

The way to compute a distance or degree of analogy could be based not on our numerical procedure but could perhaps utilize a system of finding an analogous set in a collection of sets by a method similar to the one which astronomers use to scan a set of photographs of a region of the sky to discover a new or variable star by flipping a number of these in succession in that the eye, disregarding the rejective pictures, reacts to a point which "jumps out" on a background of constant impressions.

This could be imagined as follows: The more "global" parts of the code evoke from the memory places where these "trunks" of the nervous connections go. A set of pictures which are then compared modulo 2 with the impression received, that is, the overlap of the pictures is "dark"--when the total intensity of the symmetric difference is sufficiently small-the picture is examined in more detail until it is finally recognized or else put in the memory in the new place (together with all the "small deformations" of the new picture).

A more economical and efficient method of operating by the nervous system and the brain should be, of course, to keep in the memory just one example (or a few examples). Presented with a letter as a "problem" the brain can obtain very quickly from any example it has many deformed ones and compare the one to be recognized with this whole class in the manner described above. This avoids the loading of memory with unnecessary variants of a given "picture."

The next step is to devise, in an analogous manner the recognition of classes of sets of pictures which are not variants of one of them. The following may serve as a case of the general problem. Given are, say, 10 pictures representing various animals-a dog, a cat, a horse, etc. Given

is a set of points representing another animal. One is to decide whether this new picture belongs to this class K or whether it represents, say, a tree, of which we also have in the memory a number of examples, forming a class. The problem deals obviously with variables of a higher class-families of sets-instead of sets individually.

The sets of each class have only some properties in common; they are not variables of just one set as before. The problem of recognition of a class would be attacked by considering functionals of sets. One set of functionals can be the Fourier, or rather Rademacher or Walsh coefficients, describing a two-dimensional set. These, by the way, should be weighted, as in our previous discussion. But there must be several or many other sets of functionals, including one dealing with individual points, for example. The functionals whose sequence is put in the memory must overdetermine the sets which we consider and which our experience builds up gradually from childhood. Perhaps a hundred or more collections of sets of functionals are gradually acquired.

We shall now tentatively describe a possible mechanism of discerning whether a single set S should be put in the class of sets R or in the class U. For simplicity of explanation let us assume that the class R consists of two sets R₁ and R ₂ and the class U of sets U₁ and U₂ .

We examine functions F₁ ... FN for the sets U₁ and U₂ and find out which among them are the same or have close values for the sets R₁ and R ₂. This is a collection forming a subset of the sequence F₁ ... FN, call it F ... F.1 . Analogously for sets U₁ and U₂ . these might be F 2 ...F . For our "problem" presented by the set S we look at these functionals for the set S and find out whether the values of S are closer to the F¹ collection or else to the F ² collection. We make our decision accordingly. (If none is sufficiently close we will decide that the set S has neither the "property" R nor U.)

In our next report we shall examine a possible way to scan this procedure, which, in the case where R and U contain a sizeable number of sets each, will be more "economical."

As a final example of a situation in which the type of computational facility we have alluded to might play a role, we outline a very general formulization which we label the "graph of mathematics." The iterative searches in this graph that might recognize "deep theorems," given the complexity of the graph, would involve the ability to make rapid computation on "parallel" searches over a great multitude of paths.

The idea is to consider a formal system of mathematics as a collection of groups of signs and symbols starting with a list of symbols, then selecting a system of axioms, for example Godel's, (really for the first attempt taking a much more restricted and simpler one), we start

with axioms which are groups of signs. We have rules of combination of these and rules of deduction which are formalized. These are not written down, but given a single group of formulae we consider joining them to others by the rules of procedure which include the symbols for Boolean operators, and, or, quantifiers, and substitutions. Therefore our graph has a form of a "pair tree," that is to say, from pairs of such formulae or from pairs of collections of symbols, we get new ones. In some cases, from a single one by "mitosis," we get another one (by omission or restriction, or some suitable "erasures" allowed by our procedures). We obtain a graph which bears a resemblance to "genealogical" graphs. These graphs can be characterized by the property that, going "backwards" from single points, or single individuals considered as vertices, one obtains two parents, ancestors of the individual. A single person has thus at most two, sometimes only one ancestor. (Allowing procreation by "mitosis.") These graphs form a natural generalization of graphs which are called trees, for which a considerable theory exists. Much less is known about graphs defined in the above way. A theory of such "pair trees" in analogy to the existing body of knowledge about tree graphs remains to be developed.

There are many problems which have been considered for trees. For example the reconstruction problem which has been solved for trees could be studied for pair trees. (A list of such problems will be appended later on.)

The graph of mathematics as we call it, is not the same as a genealogical tree since a given formula or a theorem can be derived by our procedures from different pairs of ancestors. (It could be considered as a pair tree with colors.)

It is possible to attempt to define the "value" or "interest" or "importance" or "depth" of a theorem, or a formula. This, roughly speaking, should have the following characteristics: some of the formulae are obtained only by a long train of successive pairs of ancestors and deductions. If they happen to be relatively short we consider them the more valuable. The really interesting ones are such which in their "neighborhoods"* have many others easily deducible from them. For example, the fixed point theorem of Brouwer has this property (the consequences of the "deep theorem" need not easily lead back to the "important" or "deep" formula or theorem.) One could try to define

* Having a pair tree, one can define a distance between any two formulae or two theorems by the length of the shortest connection between them through the chain of "ancestors." This will always be a metric. In this metric it makes sense to define "proximity" of a vertex to other vertices and to define what a neighborhood means.

what might be called a surprising formula or a surprising theorem. These could be such that can be deduced by a perhaps complicated sequence of operations from the starting list of symbols and axioms but are such that the path or a band of paths leading to them comes from a rather remote, "sidewise" located collection upstairs.

V—
Relation Algebras: Some Examples

In the next to the last application of the preceding section attention was focused on a particular "distance" between classes of planar patterns (relations). While we have given several possible metrics for such objects, no systematic investigation of such spaces appears to have been made. At the algebraic end of the spectrum though, some attention has been paid to relational structures (pattern algebras); for example, the earlier mentioned calculus of relations of McKinsey,²⁰ the relation algebras and algebras of relations of Tarski²⁷ and others. To illustrate the character of these investigations, we summarize here results obtained relative to some of the more general of the relational structures, namely, semigroups of relations. Our focus throughout is on those questions of interest to anyone concerned with algebras of patterns, particularly those algebras including the iteration or composition of these patterns as one of the basic operations.

The family of all binary relations on a nonempty set X is a semigroup under the operation of composition. We denote this semigroup by Bx. There has been increased interest in these semigroups due in part to a resolution, by Montague and Plemmons,¹⁹ of a problem of Schwarz²⁵ concerning the character of the maximal subgroups of Bx and due further, to the interesting results obtained in a topological setting by K. D. Magill, Jr. and his students.

In particular, Montague and Plemmons¹⁹ showed that every finite group is isomorphic to a maximal subgroup of some Bx. Later Plemmons and Schein²⁴ (see Ref. 7 for a particularly elegant argument) extended this result to arbitrary groups.

In another direction attention has been focused on the morphisms of Bx. In 1964, Crestey^l° showed that every automorphism of Bx which preserves finite unions is inner. One year later Zareckii³⁶ showed that every automorphism of the subsemigroup of Bx consisting of all relations with domain and range equal to X are inner. Finally, Magill,¹⁶ and independently, Gluskin,¹ 4 showed that every automorphism of Bx is inner. Beginning with the work of Clifford and Miller⁸ and pursued by Magill and his students, in the topological case, investigations of the endomorphisms of ³ x are under way.

Obviously, there are many interesting questions one may ask about Bx, but the sampling of results above is intended to only indicate some of the possibilities. Furthermore, one could argue that all of this could be subsumed within the framework of transformation semigroups since Bx is isomorphic to the semigroup of all additive set functions of X that fix the empty set (define .:8x -4 Hom(2X,2X) by O(R) = FR, where FR(A) =RA = {x I (x, a) e R for some a e A} for all A e ₂ X). This argument, however, loses some of its attraction particularly when one attempts to choose a proper topology to insure, for example, that the subsemigroup of all closed relations on some "nice" space is isomorphic to the semigroup of all continuous selfmaps of 2^X.

At the other end of the spectrum; that is, when X is finite, too little attention has been paid to Bx. It appears that aside from some characterizations (Magill¹⁷ ) no systematic investigation of ³ x has been undertaken and some very basic questions remain unanswered. (By way of illustration we include the multiplication table for B₂; that is, the semigroup of all binary relations on a two-element set. We are grateful to M. Stein of the Los Alamos Scientific Laboratory for the computation of this table.)

Multiplication Table for B₂

We do not mean to imply by the above that the semigroup of relations on a set is the proper relation or pattern algebra to study. Quite the contrary, while the calculus of relations of McKinsey may represent too stringent an axiomatization, the disregard of the Boolean operations, particularly the natural order induced by them, errs in the other direction. This judgment is confirmed to some extent by an examination of some of the characterizations of semigroups of relations (Magill¹⁷ ) which reveal the presence of an order defined in terms of the multiplication. Although considerable insights can result from a study of semigroups of relations we feel that the multiplicative structure must be complemented by some additional structure; for example, some order respected by the multiplication. A variety of such algebras will be investigated.

In yet another direction, almost no attention has been paid to topological relational structures; that is, to relational algebras topologized in such a way as to insure the continuity of the operations involved.

Of fundamental interest in any algebra of patterns are the questions of generation; that is, the construction of the patterns from basic units using admissible operations. We illustrate these ideas with some recent results on generators and embeddings for semigroups of relations. These results, most of which have not appeared in the literature, are suggestive of questions that may be asked for any structure purporting to be a "relational structure."

Recently E. Howorka has proved the following: Theorem. (Howorka). If X is a set then a relation R on X is of the form f-¹ g, where f and g are functions iff card R< card X. As an immediate corollary we have that every binary relation on an infinite set is of the form f-l'g; that is, every relation is the composition of the inverse of a function and of a function. In addition, Howorka¹⁵ observed, extending the results in Ref. 4, that the calculus of relations 3N, that is, the calculus of all relations on a finite set of card N could be generated by a single element. This followed from the proposition.

Theorem. (Howorka). Let B, denote the collection of all binary relations on the set X = {1,2,...,n}. Let R = {(1,2),(2,3),..., (n- 1, n)} and S = {(n, 1)}. The subsemigroup [R, S] of Bn generated by R and S under relational composition contains all of the atoms of Bn.

By observing that S = [R ² U (RoRC) U (RCoR)]c, where Rc denotes the complement of R in X x X, we then know that the relation R generates all of ³ n under the Boolean operations and composition.

Very little was known until recently about generators of finite semigroups and, in particular, about generators of BN. Recently E. Norris²² proved the following:

Theorem. (Norris). The semigroup ³ x satisfies (*) below iff X is finite. (*) For all R,SeBx, R°S = A implies R^-1 = S where S is a permutation on X.

This implies that 3N cannot be generated by a pair of generators. It is not known how many generators are required for BN.

There follows an example of a result similar to those suggested in Ref. 28 for projective algebras.

T. Evans^T l showed that any countable semigroup can be embedded in a semigroup generated by two elements. S. Subbiah²⁶ gave an elegant constructive proof of the fact that any countable collection of transformations on the set of natural numbers N was contained in a subsemigroup of TN, the full transformation semigroup on the natural numbers, generated by two such transformations. Since any countable semigroup can be embedded in TN, Evan's result was an immediate consequence of Subbiah's theorem.

A minor modification of Subbiah's proof permits the following extension of her theorem to relations on the set of natural numbers.

Theorem. If {Rn} is any countable family of relations on the natural numbers N, then there exist two relations on N that generate a semigroup containing {Rn}.

Proof. As in Ref. 26 we let An {2n(2m^- 1)^- 1}m1 for n =1,2, 3,... Now let X and T be relations on N defined as follows: = {(x,2x) I xeN}, and T = {(x,x - 1) I x even}U U {xX ( x + 1) + )Rn I xeAn} n=l where we note that, in general, for any relation R, by xR we mean the set xR = {y I (x,y)eR}.

Assert that Rn = bTn"T² , where juxtaposition denotes relational composition.

Suppose (x, y)eRn, then (x,2x)eO(2x, 2x- )eT, (2x -1, 2n(2x -1)) eoⁿ , (2"(2x - 1), 2n(2x - 1) - l)eT. Note 2n(2x - 1)- leA so that (2n(2x - 1)- 1) x (1/2n+1((2n(2x - 1) - 1+ 1) + 1/2)Rn is contained in T. But 2+1 (2n-(2x-1)-1 + 1) + ) =n xRn so that 2n+i 1\_ _ _ ((2 (2- 1) - 1,y) eT Thus Rn C OTqnT² .

Suppose (x, y)eqTcnT² , then (x,a)eo, (a, b)eT, (b, c)eqn, (c, d)eT and (d, y)eT, for some a, b, c, deN. So a = 2x, b = 2x-1, c = 2n(2x1), d = 2"(2x - 1)- 1. Since d =2n(2x - 1)- 1eAn, we have ye (2n+i (d+l)+Rn =xRn Hence qT5nTT² C Rn, and therefore Rn = oT'TnT² If the family {Rn} is a family of functions then the relation T is a function so that the result particularizes to that of Ref. 26.

This completes our illustration of the character of the results and problems that might be of concern to investigators of "algebras" purporting to be algebras of patterns, particularly two-dimensional patterns. Generalizations to higher dimensions of some concepts and problems considered are given in Appendix A.

Appendix A

Examples of Combinatorial and Set-Theoretical Problems Concerning the Operation of Forming Product Sets

The theory of relations, the theory of graphs, also the theory of projective or cylindric algebras have as their bases the following settheoretical setup:

Let E be an abstract set, finite or infinite. By Eⁿ we understand the set of ordered n-tuples: Eⁿ = E x E x ..., E, the elements being (el, e2, ..., en) where el e E for i = 1...n. E° denotes the set of infinite (countable) sequences (el, e2, ..., en...).

For the study of binary relations, we consider E² and associate with the given relation R between pairs of elements x, y, a set of edges; the edges correspond to certain pairs of elements of E, namely those pairs which are R-related.

In this way a given relation R, or a graph G, can be associated with a subset, call it A of E² .

(More generally, in a study of other algebraical or combinatorial notions, for example in ternary relations, say a group H we might associate with it a subset of a higher direct product. Thus for a group operation, defined on an abstract set E, we might consider in E³ the set of such triplets (el, e₂ , e₃ ) such that el o e₂ = e₃ where o denotes the group operation. Analogously when we deal for example with rings, we could consider in E⁶ a subset ofsixtuples (el, e₂ , e3, e₄ , e5, e₆ ) where e1+e2 = e3, e4⁰ e5 = e₆ where + and o denote the two arithmetic operations defining the ring. For infinite operations, i.e., in some topological theories, say, in considering Frdchet spaces where the fundamental notion is that of convergence of a sequence: (el, e2, ..., en, ...) to an element eo, we may "represent" the topological space by a subset of E° consisting of the sequences: (eo, el, e2, ..., en, ...).

We introduce now a general notion of product isomorphism and product homomorphism which subsume the notions of isomorphism, and homomorphism used in these theories.

Two subsets A, B contained in E² are called product isomorphic if there exists a one-one mapping T(E) and the mapping T² defined by T² (x,y) = (T(x), T(y)) maps the set A onto B: T(A) = B. Analogously a product homomorphism S² (E) is defined by a not necessarily one-one mapping S(E) = E by (x,y) - (S(x), S(y)).

In complete analogy one defines a product isomorphism Tⁿ of Eⁿ onto itself by Tn(Eⁿ ) = En through (x1, x2,..., xn) - (T(xl), T(x2), ..., T(xn)) and two subsets A,B of En are called product isomorphic if there exists a T and Tn(A) = B.

Similarly we define the product homomorphism Sn. B is called product homomorphic to A if there exists an S such that Sn(A) = B. n can be any finite integer or n = oo.

It is obvious now that two relation sets R₁ and R ₂, or two graphs G₁ and G2, are isomorphic to each other in the usual sense if and only if the "representations" of them as defined above are product isomorphic in our sense.

Similarly, the isomorphism of two groups H₁ and H ₂ is equiva-

lent to the product isomorphism of the subsets "representing" them in our sense. Analogously, homeomorphism of two topological spaces is obviously equivalent to the product isomorphism of their "representations" in E°. It is equally clear that homomorphisms, algebraically or topologically translate into homomorphisms of the representations.

We shall now present a few examples of combinatorial problems arising in the theory of properties of the product isomorphisms. The first questions concern the enumerations.

(1) How many nonproduct isomorphic sets can one have in Eⁿ or equivalently, of course, how many classes of product isomorphic sets are there? (Product isomorphism is a transitive relation, so the classes are disjoint.) The asymptotic estimates are known for E² --that is to say for the number of nonisomorphic relations or nonisomorphic graphs, in case of E, finite. (For E countably infinite the number is of the power of the continuum.) Much less if known for n = 3 or higher, i.e., the number of non-isomorphic general ternary relations, for example.

(It is of the order of 2(3),N being the cardinality of E; it is obviously = c for cardinality of E equal R.)

(2) Analogous problems concerning product homeomorphisms. Less is known for this case. The question is how many sets can one have in Eⁿ so that none of them is a homomorphic image of the other? (Recently, E. Howorka and, independently, J. Mycielski showed a continuum set of graphs such that none is a homomorphic image of any other in the set.)

(3) Questions concerning the existence of "universal" countable subsets of En, i.e., such sets A in Eⁿ that every countable subset X in Eⁿ should be isomorphic to a subset of A; this, of course, in the case when the cardinality of E is that of a continuum.

(4) Problems concerning the existence of "economical" bases for a given class (e.g., a countable one of subsets A₁, A₂, ..., Am, ... of En). This means, for instance, furnishing finite number of sets B₁, B₂, ..., Bj such that by the operations of Boolean algebra and of projection and direct product formation one can obtain, among others, all the sets A₁ , ..., An... (There is a whole class of problems of this sort, mainly still unresolved.) For the case of K finite can the base be formed with just 2 sets? The problem is of interest when the cardinality of E is say of the power of continuum or higher-the class of given sets may then be uncountable.

(5) Problems of the above sort become more difficult when their analogs are stated for the notion of "equivalence" of two sets A, B through a decomposition.

We illustrate this notion for subsets of E² . Two subsets A, B of E2 are called equivalent by finite decomposition if: A =Al A 2 U ... U Ak B =B B ₂ U U  U Bk Ai n Aj = 0 for i # j Bi n Bj = 0 for i :j and each Ai is product isomorphic to the corresponding Bi-the product isomorphism depending in general on i that is A = T(B): through a transformation Ti.

In the case when the cardinality of E is finite the problem concerns for example the number of sets nonequivalent by a decomposition into two subsets. If E is infinite, e.g., of the power R of the continuum or higher, one can ask about the possible number of sets nonequivalent by decomposition even into a countable number of sets:

00 00A= U Ai, B= U B. n=1 n=l (6) A notion of "weak" product isomorphism: e.g., for n = 2. For subsets A, B C E₂ , we call these weakly product-isomorphic if there exist two transformations T₁ and T₂ of E onto itself. Such that the transformation T₁,₂(E² ) ~* E ₂ defined by (x,y) - (Ti(x), T₂(y)) carries A onto B: T, ₂(A) = B.

(7) A definition of "iteration" of subset A C En. This will be a subset ² A of E2n defined as follows:

² A consists of all sequences of elements (el, e ₂, ..., en fi, f2, , fn), where (el, ..., en) and (fi, ..., fn) were arbitrary elements of A.

Suppose ² A is product isomorphic to ² B; under what conditions can one assert that A is product isomorphic to B? In all generality this

is not true. For example, Fox constructed, in an answer to a problem posed by one of us, an example of two topological spaces S1 and S2, and the S2, and S2 are homomorphic (in the usual topological sense) but S₁ and S2 are not. For algebraic or combinatorial structures, the answers are in general negative-but true for special classes, e.g., finite groups, graphs of special character, etc. When can we assert that if ² A₂ is a homomorphic product image of ² A₁ then A ₂ is a homomorphic image of A ₁?

The above will merely serve as isolated specimens of a great class of problems formulable in the spirit of combinatorial set theory from a unified point of view.

Appendix B

Physical Realizations of Nonserial Compositions

In this appendix we consider the possibilities for the physical realization of nonserial composition.* In particular, in A there is described the preliminary engineering design of a device that effects this operation. One could consider the problem of more efficacious designs along these lines with the objective of possible fabrication of a pilot model to serve as a heuristic aid in early theoretical studies, but the interconnection problems preclude a system of even modest capability.

In part B we describe possible lines of investigation of threedimensional computing in a homogeneous medium. While presenting many interesting possibilities, particularly in the elimination of the size restriction inherent in A, this endeavor faces many unsolved problems in the area of materials science. What is considered here is an initial assessment of physical phenomena that might be exploited to effect the realization of the principal processes of cylindrification, intersection, and projection, the processes basic to nonserial composition.

A—
Discrete Systems

Here we are concerned with the preliminary engineering design of a discrete composition machine, in particular the logic, memory, inputoutput, control, and size. The cube of Fig. 1 is referred to in the description of this proposed hardware.

* We are particularly grateful to Derek Dove, Professor of Materials Science and Engineering, University of Florida, for generous discussion of the schemata that follow.

This machine is described as a cube with three relevant working surfaces, A, B, and C, where pairs of indices (i, j, k) describe locations on each surface as indicated in Fig. 1, with each index having n possible values. In this description, surfaces A and B are thought of as being the input mappings to be composed, with the results projected on surface C.

The logic of the composition is described as a two-level AND-OR array. A typical cell on surface A is associated by logic AND with each of the n cells on the same row of surface B, with the result projected to a row of internal points. For instance, typical internal point cijk holds the results of the logical AND of cells aik and bjk, as Cijk = ik A bjk -

Now the projection upward onto the C surface is taken as follows. Each cell on the C surface, 2n-1 Cij = V Cijk k=o where Cij is a typical cell in the C surface and where the recursion operator indicates a logical OR in the k direction of all the cij elements below it.

A possible realization to illustrate this idea is as follows. Each of the n" AND gates can be realized by a transistor such that transistor conduction indicates a logic 1, occurring if the voltage on the base is high AND, and the voltage on the emitter is low. As shown in Fig. 1, variable ik is a bus bar which supplies base current from surface A to any number up to n transistors. Variable jk is a similar bus bar from the B surface. Each bar is programmed, at surfaces A or B, by connection to a voltage supply.

The recursion OR, operating in the k direction, can be considered as a bus bar connecting together all the collectors of the transistors in each level below it which have the same (i, j) coordinates. The display cell on each cell of the C surface is a lamp, which is on if one or more transistors below it are turned on by the (ik, jk) coincidence.

One of the system requirements is that a result of a composition displayed on surface C needs to be mapped back onto surface A in order to provide the capability of several iterative compositions with a fixed mapping on B. This can be accomplished with an n x n array of flip-flops on each of the two surfaces A and C, where one of the surfaces would required dual rank flip-flops.

Logical AND at each Cijk = aik A bjk 2n-1 Logical OR vertically Cij = Cij = V Cijk k=O A possible cell realization: ILAMP "TIED OR" Fig. 1. Schematic for a discrete composition machine.

18 On the Theory of Relational Structures and Schemata for Parallel Computation

B—
Homogeneous and Partially Parallel, Partially Serial Systems

Here we consider physical phenomena that might be possibly exploited to effect a realization of the processes of projection and intersection.

Several major types of systems may be envisaged. The projection path may be delineated by some physical structure such as an electrical conductor, and intersection may be realized by the use of discrete components as in A. We may refer to such a system as a discrete system. Alternatively, projection may be carried out by the motion of an advancing wave front, while intersection in such a case may involve the interaction of wave fronts in a homogeneous medium. Evidently these two examples represent the extremes of completely discrete and completely homogeneous systems.

The present status of such arrangements may be summarized briefly by noting that while the technology exists for the construction of an entirely discrete system, such a system suffers from an inefficient use of elements and presents interconnection problems of extreme difficulty for a system of even modest capability. Modern high-density fabrication techniques lend themselves naturally to two-dimensional organization.

Three-dimensional computing in a homogeneous medium, while an exciting possibility, presents unsolved problems in both mechanisms of defining a vector or scalar wave property over a large region of space and in choice of wave/wave interaction phenomena.

This part of the appendix is concerned with the exploration of the implications of function composition for parallel computing schemes, and with the preliminary assessment of the potentialities and limitations of homogeneous medium interactions. Finally a study is proposed of partially parallel, partially serial systems, based upon modern high density solid state optical sensor arrays.

1.Homogeneous Medium. Wave front delineation: The spatial limitations imposed upon a wave front by diffraction effects are, of course, well known; the resolution with which a desired image may be reproduced may be readily evaluated from a knowledge of wave length, system observations, and effective aperture.

The process of projecting a two-dimensional image "intact" through a region of space can only be carried out with a resolution far inferior to the two-dimensional resolution capabilities of the system. In optical terms an extreme depth of field requires a very small beam divergence which in turn limits lateral resolution.

One would need to examine the information packing density that may be "projected" using optical, holographic, acoustic, and electron beam techniques.

Interaction in Medium. In order to carry out the intersection process utilizing the influence of two projected wave fronts, it is necessary that the intersecting wave fronts produce an effect that may be detected by a third orthogonal wave front and that may in addition be distinguished above the background "noise" level due to the nonintersecting wave fronts.

Particular attention needs to be given to an evaluation of known optical and acoustic phenomena for their potentialities for the present applications. Examples are (i) Photochromic effects in which a beam of one wavelength produces a coloration in a crystalline or glassy medium, a second beam of different wavelength produces a bleaching or other change of the colored region. (ii) Quenched fluorescence, a phenomena where the fluorescence produced by light of a particular wavelength may be locally quenched by light of another wavelength. (iii) Acoustic beams, that may give rise to a stress-induced birefringence. By suitable summation of local stress fields, a change may be made that is detectable by a polarized light beam. Evidently each phenomenon offers certain potentialities and limitations.

The phenomena need to be evaluated for signal/noise ratio, information packing density, and the inherent natural lifetimes associated with them.

2. Parallel/Serial Image Processing. A promising compromise approach to a machine permitting functional composition is one employing solid state imaging technology. Such a system might consist of two planar input optical sensor arrays, a cathode ray tube output display, and line and frame scan circuitry.

Each sensor array consists of n rows of sensors, each row containing m sensors connected in a charge transfer chain. Thus the charges produced upon a line of sensors may be stepped sideways simultaneously by simple scan circuitry. As the charges reach the end of the row they activate further circuitry controlling, for example, the intensity of an electron beam being scanned synchronously across a phosphor screen. Thus in a solid state television system, the sensor array is exposed to an optical image, giving rise to greater or lesser charge buildup in the individual sensors. The charges are then read out by stepping the charges in each line along each row in sequence. This information is used to modulate a scanning electron beam and so the image is regenerated upon a phosphor screen.

In the composing system an input image is presented to a lineorganized sensor array, and a second image is presented to a similar second array. In order to form an image of the mapped intersection of the projection of the two arrays as described earlier, the information content of the first array is stepped along a row by one unit, all rows stepping simultaneously. The row output signals enter a chain-of-logic elements. The second sensor rows are now stepped continuously in synchronism with a scanning electron beam and are compared with the first column of signals of panel 1. The row output signals enter the chain-of-logic elements and, if an output signal is encountered on any corresponding rows of the two arrays, then the intensity of the electron beam is modulated.

The information of the first array is now stepped again, the electron beam is displaced one unit sideways, the second array is re-exposed if necessary and a new line is scanned.

In this way an image is built up on a display screen having the required properties. By using a storage display tube this image may be retained and used to expose the first sensor array, light output and optical sensitivities being quite compatible in this regard.

The two sensor arrays, scanning circuitry, and logic chain may be fabricated upon one silicon single-crystal wafer, using the state-of-theart photolithograph techniques. It is not unreasonable to contemplate arrays of 500 x 500 elements.

Path of Electron Beam I Output Plane 4 Bright Spots

The logic chain gives a signal if and only if a signal is present on both input terminals. The information in plane 1 is stepped sideways; i.e., change in column 2 is moved to column 3 one step at a time. At

each step an electron beam sweeps along a line and plane 2 is stepped through 1 to 5. If a signal is present on both inputs of the chain of comparators at some step, then the intensity of the electron beam is increased.

In a simpler scanning arrangement the two images may be mechanically scanned, one slowly, one rapidly and repetitively, across two columns of photosensors, for example, by rotating or oscillating mirrors. The scan rate of the images is synchronized to the faster scan of the electron beam of a display tube as before. Signals are compared as before and coincident signals give rise to a brief increase in intensity of the electron beam. Such devices are fully within the present state of the art of silicon microelectronic technology.

f Column of Photo Detectors for Image 1 Photo Detectors for Image 2 ElectronBeam Controls Brightness of Electron Beam Image Stepped Slowly Image Scanned Quickly

18On the Theory of Relational Structures and Schemata for Parallel Computation

References and Related Publications

1. A. R. Bednarek and K. D. Magill, Jr., "Q-Composable Properties, Semigroups and CM-Homomorphisms," Trans. Am. Math. Soc. 171 (1972), 383-398.

2. A. R. Bednarek and K. D. Magill, Jr., "Semigroups of Clopen Relations," submitted.

3. A. R. Bednarek and 0. E. Taulbee, "On Maximal Chains," Rev. Roum. Math. Pures Appl. 11 (1966), 23-25.

4. A. R. Bednarek and S. M. Ulam, "Generators for Algebras of Relations," Bull. Amer. Math. Soc. 82 (1976) 781-782.

5. W. A. Beyer, M. L. Stein, and S. M. Ulam, "The Notion of Complexity," Los Alamos Scientific Laboratory report LA-4822 (December 1971).

6. R. E. Bonner, "On Some Clustering Techniques," IBM J. Res. Dev. 8 (1964).

7. A. H. Clifford, "A Proof of the Montague-Plemmons-Schein Theorem on Maximal Subgroups of the Semigroup of Binary Relations," Semigroup Forum 1 (1970), 303-314.

8. A. H. Clifford and D. D. Miller, "Union and Symmetry Preserving Endomorphisms of the Semigroup of All Binary Relations on a Set," Czech. Math. Journ. 20 (95) (1970), 303-314.

9. L. N. Cooper, "A Possible Organization of Animal Memory and Learning," Nobel Symposia 24 (1973), 252-264.

10. M. Crestey, "Applications Multiformes Partielles," Collectanea Mathematica, Univ. of Barcelona 16 (1964), 111-126.

11. T. Evans, "Embeddings for Multiplicative Systems and Projective Geometries," Proc. Amer. Math. Soc. 3 (1952), 614-620.

12. C. J. Everett and S. M. Ulam, "Projective Algebra I." Am. J. Math. 68 (1946), 77-88.

13. B. Faber and J. Larsen, Private communication.

14. L. M. Gluskin, "Automorphisms of Semigroups of Binary Relations." Ural. Gos. Univ. Mat. Zap. 6, tetrad 1 (1967), 44-54.

15. E. Howorka, "Generators for Algebras of Relations. Preliminary Report," Notices Am. Math. Soc. 24 (1977), A-4-A-5.

16. K. D. Magill, Jr., "Automorphisms of the Semigroup of All Relations on a Set," Canadian Math. Bull. 9 (1966), 73-77.

17. K. D. Magill, Jr., "Isomorphisms of Triform Semigroups," J. Australian Math. Soc. 10 (1969), 185-193.

18. N. Metropolis and Gian-Carlo Rota, "Significance Arithmetic on the Algebra Binary Strings," in Studies in Numerical Analysis, B. K. P. Scaife, Ed., (Academic Press, New York and London, 1974) pp. 241-252.

19. J. S. Montague and R. J. Plemmons, "Maximal Subgroups of the Semigroup of Relations," J. Algebra 13 (1969), 575-587.

20. J.C.C. McKinsey, "Postulates for the Calculus of Binary Relations," The Journal of Symbolic Logic 2 (1940), 85-97.

21. M.M. Nass, and L. N. Cooper, "A Theory for the Development of Feature Detecting Cells in Visual Cortex," Report, Center for Neural Studies, Brown University.

22. E. N. Norris, "A Characterization of Finiteness," unpublished.

23. R. E. Osteen, "Clique Detection Algorithms Based on Line Addition and Line Removal," Siam J. Appl. Math. 26 (1974), 126-135.

24. R. J. Plemmons and B. M. Schein, "Groups of Binary Relations," Semigroup Forum 1 (1970).

25. S. Schwarz, "On the Semigroup of Binary Relations on a Finite Set," Czech. Math. J. 20 (1970), 632-679.

26. S. Subbiah, "Another Proof of a Theorem of Evans," Semigroup Forum 6 (1973), 93 94.

27. A. Tarski, "On the Calculus of Relations," The Journal of Symbolic Logic 3 (1941), 73-89.

28. S. M. Ulam, A Collection of Mathematical Problems (Interscience, New York, 1960).

29. S. M. Ulam, "Computers," Sci. Am., Vol. 211, No. 3 (1964), 203216.

30. S. M. Ulam, "Computations on Certain Binary Branching Processes," in Computers in Mathematics Research, (North Holland Publishing Company, Amsterdam, 1968). 31. S. M. Ulam, "Electronic Computers and Scientific Research, (Parts I and II)," Comput. Autom., Vol. 12, No. 8, 20-4 (Pt. I); Vol. 12, No. 9, 35-40 (Pt. II), 1963.

32. S. M. Ulam, "General Formulations of Simulation and Model Construction " in Prospects for Simulation and Simulators of Dynamic Systems, (Macmillan & Co., Ltd., London, New York, 1967).

33. S. M. Ulam, "Generalizations of Product Isomorphisms (Resume)", in Recent Trends in Graph Theory 186, Lecture Notes in Mathematics, Springer, 1971.

34. S. M. Ulam, "On Some Possibilities in the Organization and Use of Computing Machines," International Business Machines report IBM-RC-68, 1957.

35. S. M. Ulam, "Some Ideas and Prospects in Biomathematics," Annu. Rev. of Biophys. Bioeng., 1 (1972), 227-292.

36. K. A. Zareckii, "The Semigroup of Completely Effective Binary Relations," Theory of Semigroups and Appl. I (Russian), Izdat., Saratov. Univ., Saratov (1965), 238-250.