Large Systems and their Regular Expressions: An Approach to Pattern Recognition

LARGE SYSTEMS AND TIIEIR REGULAR EXPRESSIONS: AN

APPROACH TO PATTERN RECOGNITION

David C. Rine Statistics and Computer Science Department West Virginia University Morgantown, West Virginia U. S. A.

Abstract.

Systems theory deals with classes of identi­ fiable parts each interacting in such a way that a given claas exists together to satisfy certain specific requirements; these parts can be thought of an conponents of the system, some of which are permanent and some not. In analyzing a given system (see (13)) one usually offers up an m­ tuple consisting of devices to be analyzed, f!!­ mitives to represent any device, allowable com­ positions, concepts of simulation, and theorems that tell how the devices are to be analyzed.

Category theory serves as an organizational tool for large systems.

J whose morphisms are natural transformations between functors. We call a universe whose objects are node labels and whose morphisms are edge labels. Functor theory, having now reached a level of variety and depth in descriptive power, stands ready to help the systems theorist characterize those states which are important in the study of a particular system.

A computer with a TV camera is a tissue scanner whose job is to verify homogeneity. That is, it detects flaws or holes in a tissue. It is well know that when two topological spaces are homeomorphic, then their fundamental groups are isomorphic. The job of the functor 1T" is to "record holes" in spaces.

Zeeman's (38) concept of a tolerance space is useful when dealing with visual acuity, while Wallace's (35) concept of a separation space is helpful in recording the position of patterns.

The algebraic 1T -structure of certain spaces has already been characterized; take, for example, compact connected 2-manifolds.

functors mapping into vector spaces (See Kelly and HacLane (17)) (groups) and Morph~~ just those natural transformations between linearfunctors (group functors).

If G, F £. J ~ , then G .2l...F is called an expression. An expression "\ is a category­ regular expression if the following hold:

1. ;3 large system A · (obJ~. MorphJi4.'t"A) so that ""\ £. MorphJ' 7A;
2. c (3) 3 s 0 £ Ob ~ , so that [s 0 ,· 1 E obJ/A;
3. 3. t!J A S obJ 7A subcollection of functors;
4. 3 F E. JjAso that [s 0 , · 121-F is a natural equivalence.

It is natural to define what one means by

acceptance. An acceptor is denoted by A ·

An example of an acceptor appears within the structure of Give'on's (11) study w systems. LetJ be the category with fixed input monoid W. Also, of transition of aemimodules let s:J~ ~ be the forgetful functor with Mw the semi­ module whose states are W and whose transition is determined by multiplication of W. Then, there p-1 is a natural equivalence [Mw,·] ----s; hence, we have an important acceptor of the form A ·

The following theorem of Mitchell (23) is going to see more use in systems theory. Theorem (M). Let~ be a cocomplete abelian category and let R be any ring (commutative with unity). Then, we have an additive, colimit preserving, covariant bifunctor

and a natural equivalence of trifunefo,..,

Moreover, Rine(30) has coined the concept of an R-linear separated system, having some non-linear characteristics, and proved, using Mitchell's theorem, this theorem.

Theorem. Let <Jt · be an R-linear separated transition system.

be a linear interpretation with compiler WR{Y)-- ~U ~ (Y CJ (R,+ 1 ) * in..tf~ Let VR i; ·[X, xJ=:rv*t.:J [o,lj ,v*l.J [o,lj J be an arbi-"" trary loading morphism. Assume that d H "- h Cl( and a will not execute Q(. · Then, there exists a corrected R-linear separated transition system < U ,X,~ tt > that will execute Cl( ·

In automata theory the weakest algebraic structure permitted is usually the semigroup, and when B £ Ob C one has no reason to believe that [s 0 , B) is a semigroup.

If~ is a category and [A,B]~ is a semi­ group, the semigroup structure may arise in several somewhat unnatural ways. This must first be clarified in the following proposition.

Proposition. Let s 0 £ Ob ~ projective generator forb and lr:/ A, B E. Ob !:' [A, B) a semigroup; then [s 0 ,·] is an embedding into the category of aead­ groups, preserving and reflecting monies and epics.

Hence, we shall assume the hypothesis of this proposition and call such a (:admissible' for semigroup (category)-regularity.

Hence, we call "1 £ MorphJ ~ regular if

(l) "1, is category-regular with respect to some

acce~tor A · ~(S0 ,·],obdr~· Morpher;;~,

--r;A.JrA);

1. ~ is admissible;
2. v s 0 ..f.....B in b isomorphism, then P(S 0 ).£ (f) --.F(B) is a v&riables-isomorphism, where variables d~enda upon those things A is obsering (veetor spaces, top. spaces).

Proposition. [s 0 ,·]2l!..r £ L(A, JJA ), r 1 ~ r 2 natural equivalences so that F · r 1 and r 2 E. iJ A implies "'1 0 'Y)_ E L(A, if A).

Moreover, for arbitrary "'\..· 'I.. 'tA([s 0 ,· ), "f\ o 'Y\ ) · 1: A ( 't A ([so, · ), '\'j D ) , "1. ) is defined.

Let ~ · I be a small category. Then, we will call nodes (states)D:I -J diagrams. ~ £. MorphJ 'g is small category-regular if (1) ~ is category-regular with respect to ~ and (2) b is a small category.

The corresponding A · ( [s 0 , · ) , Ob~, MorphJ~, "'[A ,/JA) is called a small system. Proposition. lrl small category-regular implies that the coordinates class of ~ has cardinality.

yt is small regular if (1) "Y'\. is small category-regular, (2) I is admisSible, and (3) ~ s 0 ~B in I isomorphism, then F(S0)~F(B) is a variables-isomorphism.

Proposition. V f £ [s 0 , B) bijection 3 semi­ f· group isomorphism [S 0 , s 0 )~[s 0 ,B) , where lo , 0 -f-1 "o" is composition and (f · ) (x o y) · (f ·) (x) o 1 r (f. )(y).

In the following diagram '1$ , "'1 B need not 0 be semigroup isomorphisms, ao that variablesisomorphism may only be bijective.

Let 'C: · I be a finite category where I · fis u fmj · Then, we will call L£0bl "" ( M·rp.,l finite J state (nodes) D:I graphs and s 0 · i 0 E Obi a point (points are not identically the same as nodes or states). � 1 ~� 2 EJ.Ifir~ite is finite category-regular if (1) '1. is small category-regular with respect to I, and (2) I is a finite category.

The corresponding A · (lie, · ) , ObJ4_, Morp~lA, TA , tJA) is called a graph system. 'Y\. is finite regular if ( 1) ""\ is finite cate­ gory-regular, (2) !finite is admissible, and (3) 't;/ i 0 -.f..-b in I isomorphism, then F(i 0 )Ei:f2rcb) is a variables-isomorphism.

Remark. In applications to programming D(i 0 ) can be thought of as a subroutine reached from [i 0 ,

Remark. One might try to think of the automorphism functors as something that changes properties being considered. Can one think of it as being a rearrangement of subroutines, a switch in control, a new sorting level, sorting level, sorting routine, scanning, searching!

Shaw (34) has considered the parsing of graph-representable pictures and gives a picture parsing algorithm that is an n-dimensional analog of a classical top-down string parser, and an application of an implemented system to the analysis of spark chamber film.

Remark. One can show how the abstract notion of category theory, in particular taking limits of diagrams in complete (colimits in cocomplete) categories (Mitchell, 23), attacks these problems .

ACCEPTANCE

In the last section we introduced the notion of ACCEPTORS; we now consider acceptance.

As was mentioned previously, one of the important natural phenomena that cocomplete (complete) category studies handle is the notion of sorting. With this in mind, let us turn to Berthiaume's (4) definition of cofinal functor.

Let A , {B be small categories with ~ A , ffi -cocomplete; then, there is a natural transformation ( eB L ~~* ~) & 0 (· .......,._...(b Co ·M ~ ) between functors with FI (D) · D o F for any D E.. ~ ~ D o F is a "subfunctor" of D.

Let '1-j. , )( 1 , X Z., ··· , X" be a sequence of small categories, and let position of n functors where X X~ k- 2, ... ,n. 1(-1 s 1 s 2 ··· sn be a com­ s1£~Xland Sk£

Let b be X,; ... , X l , ~ -cocomplete; then, there exist natural transformations I b ~ I colim(S 1 ...·· Si) ~colim, colim(S 1 .···. Sj) E kl I ...-.-.--colim(S 1 ··· Sj 1 ) so that &'· · C" . €. I - . L ~~/ ~ where i · l, ..· ,n and j · 2, ··. ,n+l. If each Sk is cofinal (If s 1 s 2 ·.. Sn£ ~)::"is cofinal), then, by Berthiaume's (4) proposition,each ~ I( ( ~" ) is a nat ural equivalence.

Let us define s 0 · colim(S 1 ·.. Sn) 1 so that One can now give another definition of acceptance and (colimit) category-regular expression. Let s 0 (n) · s 0 arise from a sequence s 1 , ··. ,Sn of functors as before, and let b satisfy the necessary cocompleteness properties. We admit a

5-tuple A · < s 0 (n), l}Acl'\y where JJ A (n) point one should substitute for b the category of sets J Then, lookinR at some sequence of functors of length m, a natural question to ask is whether or not s 0 (m)(D) is a semigroup, group, or whatever. Thus, the notion of variables mentioned earlier becomes a search for properties after a certain level: semigroups, groups, ···

There are two ways to approach a problem (analysis and synthesis). One notion, like "sorting", is given F · co lim, then find s 0 ; this seems to be what category theory is all about at this point, i.e. that of synthes:s or putting things together. The other notion, like "listing", is given s 0 , then find F · colim; this is more the notion of analysis or seeing how things are put together; for example, what pictures are described by a given picture description grammar, or what languages can be written down by a given finite state acceptor (automaton, directed graph with entry point); language theorists call an analysis a parse. We include one more theorem about these very general acceptors.

Theorem. System B · ( [j 0 , · ),~ ,£) 8 C. obJI ,-c 6 ) can simulate system A · ([i0 , · 1./}ft..iJA C. obJ 1 ,1;A> if and only if j! functor to functor correspondence by natural transformations between J)A and/)8

The study of systems with foundations in category theory is not entirely new (see 10, 11, 12, 33); but, a general theory of abstract systerns using simulation as a category morphism in order to better understand coordination problems is new (27, 28, 29).

SYSTEMS TIIEORY

We refer the reader to (4) for definitions of connected category and cofinal functor. Berthiaume (4) proves the following proposition. Proposition (B). If F:pt-- (B is cofinal, D: (B-~ and colim D exists in (; then 0 (D) is an isomorphism. If ~ is r:EJ -CO­ complete, then 0 is a natural equivalence.

Moreover, the following theorem is due to

Mac Lane ( 17) · ~ ..:A" ,-v * Theorem (M). T 0 :/\~<,4) is confinal.

We now extend the Kan category to a more I general form; let~ ~ ~ be a aubcategory of ;4-. Then, let <,c4-' ·A) be the category I of abstract systems with inputs from A and state-outputs from~· We define the general­ ized Kan category over the pair~ ·JDt by con­ sidering pairs as follows.

,..,.

of cofinality is satisfied, but it is not apparent that for every a E. [A I · Ar4 :.A-) a/Bo ·­ is connected. The same difficulty is encountered in the more restricted "classical" definition of cofinality mentioned in (17,4). Moreover , MacLane's proof for T 0 cofinal does not work when trying to show B 0 ' cofinal.

A good discussion of classical inputoutput systems motivated from differential equations can be found in references (36, 3, 22), especially where Zadeh and Polak discuss consistent abstract objects (36). We are making much use of the following notion. Let us consider the binary form of a general system (21); this is a relations=: U x Y. The u's are in US and the y's in YS. Let Z be a set and Sz a function mapping any subset of Z x U into Y

(not nee. US' YS), denoted (Z xU)~~ Y.

Z represents the initial global state object for S if SZ(z, u) ~ function (U) · · Y<=::=> (u,y) E. s~ ui!!--=+Y. s - U acceptable by S if and only if z s. 'V u sa. z 3. E. z z E. z u·: 3

Consider the following two explicit repre-

represent these two devices. We will say that S~ 0 simulates S~ 0 if there is an en­ coder H and a decoder h so that the following diagram is commutative.

This means that h(y 2) · y 1 · .,( o E + E * ul and y 2 · {3 0 E + E * H(u 1 ) · {3 0 E + E * u 2 · S · U 51!- (S is a relation and Sa a funcZ

tion) forms the class of objects of a category, where Si!! is mapped to 5~ if there exists a 1 2 pair (H, h) such that the following diagram com-

i · ~ ~ 1 5; moreover, (X) is just a set, whereas it may turn out that the ~i have more structure. For example, each ~i might be a monoid with left cancellation; these monoids are important to automata theory (10, 11). All told, we have a class~ · U x Y ,,! · US tl. (usually finite), D( u ;.. and categories (general system) SCI( · z Si! . Proposition. Le~ be a category with products and finite intersections, and let D be a diagram in.9'\-- over a scheme (I, m, d). Then, a limit for D is given by the family of compositions

where d(m) · (j, k), and pi represents the ith projection from the product.

Let W E. i'Y"\ (monoids) and S £ ~ . A function s E. [W, S]J is called an abstract ma· chine. A simulation relation can be established between two abstract machines s 1 , s 2 by the fol­ lowing commutative diagram where H is a monoid morphism and h is a function.

It is obvious that two such relations (H', h'), (H, h) can be composed in a natrual way; but, it is also obvious that a single relation can have many domains and codomains. Hence, the usual procedure is to replace each (H, h) by a triple (s, (H, h),t) to establish a morphism from s to t; we therefore can extend the class of machines and relations to a category of machines and morphisms that we denote by ( i'Y\ , J ) .

Proposition. i'"v\. has (equalizers, finite pro­ ducts, pullbacks),~ has (co-equalizers, finite co-products, pushouts), and ( -rvt , J ) has (equalizers, pullbacks).

Moreover, since 1yt has limits and J has colimits every connected diagram of abstract machines has a best possible representation in (~ .J ).

Lawvere and Berthiaume (16,4) have used the notion of comma category: if (8 _E__.. b A fJ is a pair of functors, then an object in the comma category (F,G) is a triple (B,c,D), where c F(B)----+G(D), and a morphism (B,c,D)-------+ (B',c',D') in (F, G) is a pair (B~B', o....!!.... D') such that G(d)c · dF(b), i.e. (c,b,d,c').

contravariant) pair of functors. Hence, assume Go 1 the pair (B F b ~ ~where_s4- has limits andA has colimits. Moreover, let F be limit preserving and G 0 colimit preserving where (B,c,D)(F(b),Go(d))(B',c',D'). Thus, we have a "twisted coi!IDa category", denoted (F, G 0 ); and, we have the following theorem. Theorem.

• I Hypothesis : (1) Let A- S A be a subcategory of A and let {8, ,tf) be connected, small categories with infinite products;
• (F, G 0 ) ia a twisted comma "category;

• Conclusion: (1') (F, G 0 ) can be extended to a category;

Assertion. Let I be a small category with infinite products (a scheme). Let I 0 be the dual of I; I x I 0 is the scheme whose objects are \"\"\ i E. I; if i ~j is a morphism, then a morphism (,... , rn·) o in I x I 0 is denoted i-j. Hence , i · m jm and I is equivalent to I x I 0 · (I, I 0 ). Corollary. Let ( -r{ ; S', T'; ,4-', fEJ 1 ) be an adjoint situation and let co-( 1rL ;S, T; -4 , {B ) be a co-adjoint situation where A'~ A- , (£3'!;: (£ , S' · S/.74' , and I r-J' T' · T/ (8' , into (3 and .TT"" respectively. ( ...If I S, T ; _.,..,.... Th th i t ( ( ~ I ' "Y\ ) ,· en, ere ex s s . L L 74->.<(8'.(8 )) adjoint situation .

I Freyd (9) !\as showh that P4- ~ JZ4- subcategory is coreflective (relfective) if and only if its inclusion functor has a left-adjoint (right-adjoint).

( 7'4- . ~ ) is a reflector if and only o 71 0 (J. I): <54 ·A >-<A:' ·A-> 0 0 1 sion functor has a right-adjoint R. - References if I · ,...., inclu-

1. R. H. Anderson, "Syntax-directed recognition of handprinted two-dimensional mathematics," Ph. D. thesis in appl. math., Harvard U., Cambridge, Mass., 1968.
2. M. Arbib, "Theories of Abstract Automata," Prentice-Hall, Englewood Cliffs, N. J., 1969.
3. R. B. Banerji, "The state space in systems theory," Information Sciences, 1(19 , 335342.
4. P. Berthiaume, "The Functor Evaluation," Lec­ ture Notes in Mathematics 106, Springer­ Verlag, New York, 1961.
5. R. M. Burs tall, P. J. Landin, "Programs and their proofs: an algebraic approach," Machine Intelligence, 4(1961), 17-43. --
6. M. Eden, "On the formalization of handwri­ ting," Proc. Symposia in ~- Math. (1960), 12, Amer. Math. Soc., Providence, R. I., 1961, 160-166.
7. T. G. · Evans, "A grammar-controlled pattern an­ alyzer," Information Processing 68, Proc. IFIP Congr. 1960, Morrell, A. J. H. (Ed.), 2 (Hardware, Applications), 1592-1598 (North­ Holland, Amsterdam, 1969).
8. P. Freyd, "Abelian Categories," Harper and Row, New York, 1964.
9. Y. Give'on, "On some categorical algebra as­ pects of automata theory: the categorical properties of transition systems," Technical Report, The University of Michigan, Ann Arbor, 1966.
10. Y. Give 1 on, "Categories of semi modules: the categorical structural properties of transi­ tion systems," Mathematical Systems Theory, 1(1967)' 67-78.
11. J . A. Goguen, "Categorical foundations for general systems theory" (to appear).
12. 13, G. R. Joubert and L. 0. Stander, "A new ap­ proach to the presentation of computer sci­ ence courses," The Computer Bulletin, 14 (1970)' 342-343.
13. R. Kirsch, "Computer interpretation of Eng­ lish text and picture patterns," IEEE. Trans. EC - )3, 4 (Aug, 1964), 363-376. -- ---
14. J. Lambek, "Completions of Categories," Lec­ ture Notes in Mathematics, Springer-Verlag, NewYork, 1966,
15. F. W. Lawvere, "Functorial Semantics of Al­ gebraic Theories," Thesis, Columbia Univer­ sity, 1963.
16. S. Mac Lane and G. M. Kelly, "Coherence in closed categories," Journal of Pure and ~­ plied Algebra, 1(1971), 97-140.
17. 17! S. MacLane, "Categorical algebra," Bulletin of the~~. 71(1965), 40-106.
18. W":- 5.""Massey, "Algebraic Topology: An In­ troduction," Harcourt, Brace, and World, New York, 1967.
19. M. D. Mesarovic, D. Macko, Y. Takahara, "Theory of Hierarchical, Multilevel, Sys tern," Academic Press, New York, 1970.
20. 11·~· D. Mesarovic, "Auxiliary functions and constructive specification of general systems," Mathematical Systems Theory, 2 ( 1968), 203-222.
21. M. D. Mesarovic, "On some metamathematical results as properties of general systems," Mathematical Systems Theory, 2(1968), 357361.
22. M. D. Mesarovic, "Controllability of general systems," Technical Report, Systems Research Center, Case Western Reserve University, Cleveland, 1970.
23. B. Mitchell, "Theory of Categories," Academ­ ic Press, New York, 1965.
24. R. Narasimhan, "A linguistic approach to pattern recognition," Rep. No. 21, Digital Computer Lab., U. of Illinois, Urbana, 1962.
25. R. Narasimhan, "Syntax-directed interpreta­ tion of classes of pictures," Comm. ACM 9, 3(March 1966), 166-173. -- --
26. T. W. Pratt, "Semantic Modeling by Hierar­ chical Graphs," Technical Report, The Uni­ versity of Iowa, Iowa City, (May, 1970).
27. D. C. Rine, ''A categorical characterization of general automata," Information and Con­ trol, 19(1971).
28. D:"'C". Rine, "A theory of abstract systems and limit preserving functors" (submitted publication).
29. D. C. Rine, "Algebraic techniques in linear systems theory" (submitted for publication).
30. J. P. Roth, "Algebraic Topological Methods in Synthesis," Proceeding of.!!.!! International Symposium~ the Theory of Switching 29(1959)' 57-73
31. A. Salomaa, "Theory of Automata," Pergamon Press, New York, 1969.
32. C. P. Schnoor, grammars," Information and Control, 14 (1969), 252-277.
33. A. C. Shaw, "Parsing of graph-representable pictures," J. ACM 17(1970), 453-481.
34. A. D. Wallace .~eparation spaces," Annals of Mathematics, 42(1941) 1 687-697. --­
35. Zadeh and Polak, "System Theory," McGraw - Hill, IUES vol. 8, New York, l969.
36. J. Zapletal, "Distinguisl ing subsets of semigroups and groups," Arch. Math. (Brno) 4 (1968)' 241-251. -- --
37. E. C. Zeeman, "The Topology of the Brain and Visual Perception, " in "The Topology of )-manifolds" (M.K. Fort, Ed.), pp. 240-256.