Old posts: Max Kelly 2007

With the closing of our offices in via Carloni the web server of the old department was offline for a time and I suspect will not be reliable in future. I have decided to transfer material from the server to this blog or to the Como Category Archive.
The first item is a post made when Max Kelly died in 2007.

Read more »

Old post: Why are we concerned? F.W. Lawvere

This is an old post of Friday, March 31, 2006 taken from the Categories mailing list.

F.W. Lawvere: WHY ARE WE CONCERNED? I
Categories Mailing List
Sun, 26 Mar 2006 16:43:31 -0500 (EST)
Read more »

Old post: reviews of my book, Categories and computer science

As I mentioned earlier I am gradually moving stuff from my old department page, principally because we have changed department under some relentless pressure in Como to close the computer science course there.

Reviews of Categories and Computer Science, Carslaw Publications 1991, Cambridge University Press 1992.

Telegraphic Reviews by Gian-Carlo Rota
The Bulletin of Mathematics Books, issue 9, page 16, Sept 1994.

Categories and computer science, R.F.C. Walters, Cambridge University Press, 1991, 166 pp.
This is probably the clearest introduction to category theory written to date. The author's secret,what distinguishes this presentation from most other presentations of the subject, is not to be afraid to take known mathematical facts as motivation, even when these facts might threaten the beauty and independence of the subject. Other authors have followed the opposite course, with disastrous consequences: they pretend that everything in mathematics is to be kept in a state of suspended animation until the reader has mastered category theory, or what they present as category theory. It is also clear from reading this book that the main customer of "pure" category theory is not algebra, nor algebraic geometry, but computer science. A similar fate befell lattice theory some forty years ago, when it was realized that lattices had very little to do with the classification of algebraic systems, but had much to do with combinatorics.

The American Mathematical Monthly

Nice, crisp introduction to category theory, motivated by examples and use in computer science. Mathematical sophistication blends nicely with fundamental concepts and examples to make the connections (and usefulness) understandable to good undergraduates.

Computing reviews

Categories and computer science
Walters R. Cambridge University Press, New York, NY, 1992.
Reviews by: David B. Benson Nov 1993
About 35 years ago I had a discussion with some graduate students at my alma mater about problems I was having formulating questions about function composition in relationship to Algol. They said that little was understood about such general compositions. At that time hardly anyone knew about category theory and Kan had only just published his seminal paper on adjoint functors [1]. Today the effectiveness of category theory in explicating concepts based upon composition is widely recognized. The applications range from dynamical systems through rewrite rules and programming languages to structures within logic that profoundly alter our conceptions of constructive foundations.

As computation is so deeply intertwined with the very conception of composition, the universals that arise in the study of categories apply to all technical aspects of computer science, computer engineering, software engineering, and all other technical forms of computer practice. In any discipline, appropriate theory codifies the experimentation and practice. We now understand the role of categories and category theory in providing a clean, uniform, cohesive framework giving great insight into appropriate computational structures.

Lawvere and Schanuel

F. William Lawvere’s Ph.D. dissertation originated the categorical view of algebras that strongly influenced the development of abstract data types. He invented distributive categories as an explication for aspects of computation. His work with Myles Tierney gave rise to the great foundational explorations of toposes. Written by masters, Conceptual mathematics is for all of us who want to learn a new, clear, clean, crisp, and wonderfully refreshing way of looking at the world. Not specifically just for computer scientists, this elementary text could serve as the lecture notes for a freshman course. It offers a perspective upon the world that, provided you persevere, will enable you to see order and beauty where previously there was none. The book is full of the beginnings of topics that are ordinarily considered advanced but are not actually that difficult, as this book demonstrates. These topics include the important notions of inverse images and fibers, but also factorizations and a touch of toposes. Categories of structured sets and universal mapping properties are introduced.
All of this is done for beginners with small, well-motivated examples. The book has lots of discourse with students, plenty of repetition, and ample examples. This gem is suitable for self-study or the classroom, and for the sheer joy of discovery I had trouble putting it down.
Walters

Many years ago, Alfred North Whitehead wrote in The aims of education [2] that the step in learning after discovery was to build toward mastery. Walters’s text, a reworking of lecture notes for a junior course at the University of Sydney, continues the discovery of the applicability of categories in computer science and begins building toward mastery. The examples are drawn from elementary topics in circuits and flowcharts and also in automata and formal languages. They build toward the distributive categories just touched upon in Lawvere and Schanuel’s work. Within the setting of distributive categories, nicely explained here, one sees data structure abstractions done properly. The example of queues is the most compelling in that all of the structure of distributive categories is used.
The concept of freedom is central to the understanding of many matters in category theory and in computer science. This concept, closely akin to generating graphs, is explicated well here. Perhaps one needs to carefully remember the distinction between a category and the presentation of a category via multidigraphs and relations. The automata and formal language concepts fit in beautifully here. Kleene’s theorem requires but a page for statement and proof after the categorical background perfectly sets the stage.
The concluding chapter takes on two procedures of great import: Knuth-Bendix and the left Kan extension. Both are explained well. The left Kan extension has many important uses within computer science as well as computer and software engineering--vastly more than the text hints at. Programs in the book and correction details for the book are available by anonymous ftp from maths.su.oz.au:pub/sydcat.
Conceptual mathematics and Categories and computer science have been used together for an upperclass or graduate course for computer scientists to good effect. I strongly recommend both books.

Pierce

The next volume for our growing mastery of the subject is Basic category theory for computer scientists. This pleasant little volume introduces more of the universal constructions than the previous two books, as well as introducing adjoints. There are many examples of adjoints. For example, the two books reviewed above contain many instances of adjoints without defining the concept. The applications discussed in this volume are all closely related to programming language semantics, but even if this topic does not particularly appeal to you, I recommend this book; the uses of Cartesian closed categories and recursive domain equations, both treated here, extend throughout computation studies and will amply repay the effort. The book closes with an extremely useful chapter about other textbooks, introductory articles, reference books, and some selected research papers. Pierce writes in the preface that he wrote this book as a graduate student, and I think that is an appropriate audience for this friendly, helpful book with lots of examples. This book is also recommended as an introduction for all computer scientists who want to read either of the next two books in this review.

Barr and Wells

Rather more mature as a text, and so requiring greater maturity and thought from readers, is Category theory for computing science. Here one sees Cartesian closed categories from a different perspective, and is introduced to sketches and to locally Cartesian closed categories. The chapter on fibrations harkens back to ideas not seen in the volumes in this review since Conceptual mathematics, as does the chapter on toposes. This chapter provides a brief, clear introduction to the important concept of sheaf. For more on this subject, try MacLane and Moerdijk [3] or Barr and Wells[4].
Fibrations and the Grothendieck construction of fibrations are important ideas. A fibration is a generalization of the inverse of a function. The generalization occurs repeatedly in the structuring of data and programs. With mastery, obtainable by the study of this volume, you will recognize fibrations and the Grothendieck construction again and again in computational settings.
This is the first book in this review to treat the concept of “triple,” also called “monad” by computer scientists following the usage in MacLane [5]. This concept is a vast generalization of the idea of an algebra, in the sense of universal algebra. So the “abstract data types” are often monads; various domain constructions are monads; certain topological concepts are monads; and so on. A more advanced discussion may be found in Barr and Wells [4].
This book lightly treats many other ideas having applications in software engineering and computer science. I consult it frequently for both areas. I recommend it highly for the more mature and patient readers who are ready to draw diagrams, do exercises, and otherwise attend to the discipline of learning a science from the writings of masters.
The book is maintained with a list of errata and additions available by postal service or email from the authors via barr@triples.math.mcgill.ca or cfw2@po.cwru.edu.

Asperti and Longo

This text is the most advanced of these five books. It treats, with thorough rigor, all the previously mentioned topics except distributive categories and sketches. This text uses indexed categories rather than fibrations. As this book is a semantically and foundationally oriented advanced text, readers should be aware that, in an important foundational sense, indexed categories need to be replaced by fibrations. Making this (not difficult) mental change as one reads will make the close relationship between indexed categories and fibrations completely clear.
The authors emphasize internal category theory, that is, categories within categories as foundations. This beautiful idea from topos theory helps to build the deep and interesting understanding of types as objects. This is the purpose of the second half of this book. Finally, at the end, we see internal models for types-as-objects done in a way that appears to provide satisfying closure about this aspect of expressibility. Once one has read the book, there is more food for thought, including predicates as fibrations (see Pavlovic [6]) and subtyping judgments for object languages and databases.
Comparison

Having fully mastered this part of conceptual mathematics, we can bring our mastery to bear upon important, practical questions of the day. For some, the first two volumes of this review series will suffice. Others may want to continue further with MacLane and Moerdijk [3], Lambek and Scott [7], and Barr and Wells [4], perhaps contributing to applications of categories by writing their own book, exemplified for the purposes of this review by Gunter [8], Manes [9], and Bloom and Esik [10]. Many topics in object databases, distributed computation, logic programming, and document preparation systems exist for which such books could be written.
I will conclude with a word about errors and notations. Every one of these books surely contains errors. Every one contains a few quirks of notation or terminology peculiar to the author or authors. The closest thing to a standard in this field is MacLane [5], and even that volume has a few mistakes. The important thing about categories is the concepts; they are what makes studying categories so refreshing.

Review #: CR117439 Review by: David B. Benson

REFERENCES
[1] Kan, D. M. Adjoint functors. Trans. Am. Math. Soc. 87 (1958), 299–329.
[2] Whitehead, A. N. The aims of education and other essays. Macmillan, New York, 1929.
[3] MacLane, S. and Moerdijk, I. Sheaves in geometry and logic: a first introduction to topos theory. Springer-Verlag, New York, 1992.
[4] Barr, M. and Wells, C. Toposes, triples, and theories. Springer-Verlag, New York, 1985.
[5] MacLane, S. Categories for the working mathematician. Springer-Verlag, New York, 1971.
[6] Pavlovic, D. Predicates and fibrations. Ph.D. thesis, Rijksuniversiteit Utrecht, Utrecht, The Netherlands, 1990.
[7] Lambek, J. L. and Scott, P. J. Introduction to higher order categorical logic. Cambridge University Press, New York, 1986.
[8] Gunter, C. A. Semantics of programming languages: structures and techniques. MIT Press, Cambridge, MA, 1992.
[9] Manes, E. G. Predicate transformer semantics. Cambridge University Press, New York, 1992.
[10] Bloom, S. L. and Esik, Z. Iteration theories: the equational logic of iterative processes. Springer-Verlag, New York, 1993.
E-mail: Webmaster

Old posts 4: The hundred errors of CCS - (Begun 19 December 2007, last addition 8 September 2008)

(with Nicoletta Sabadini)

The hundred and one errors of CCS, Comment commenced 19 December 2007

I have been thinking a bit more about CCS. I agree that processes are fundamental.
A mathematical theory of such is of great importance, perhaps equal to the importance of a theory of functions. One of the main issues is the parallel composition of processes.

This means that the attempts to develop such a theory should be subject to the fiercest debate. Any mistake at the beginning would lead to endless confusion.

In this spirit I would like to argue that there are many misdirections taken in the theory proposed by Robin Milner. Perhaps not 100 mistakes but many. In this page I would like to record my opinion. So far I have described only 20 errors (by 30th December 2007) but the page will gradually be updated.

I am very happy to receive corrections and comments on my list: in particular with respect to my misconceptions about CCS, but also with regarding divergence of opinion about the nature of processes.

I can immagine that this list may be regarded as solely negative; "it is easy to criticize".
Instead it should be understood as taking the programme of Milner and others seriously; an attempt to help in understanding the fundamental notion of "process", and parallelism; a program initiated and researched mainly by the concurrency community.

Mistake 1. The parallel communicating composition of processes should not involve broadcast as the basic communication method.
One consequence of broadcast is that parallel composition (even of two atomic processes) needs to be complicated in order to be associative.

Mistake 2. A theory of processes should begin with a clear model.
Syntax should come second. This applies even at the stage of developing a theory of processes.

Mistake 3. Interleaving is a mistake.

Mistake 4. In CCS it is impossible to say that a process returns to the same state it was in previously. This means that it is impossible to describe even finite automata.
Added 8 September 2008 Suppose we regard CCS expressions as states of processes. Then it would seem that we could describe automata by expressions, for example the process p which is the solution of p=ap would give rise to the automaton with one state p, and one transition a:p->p. Let's look at processes q and r
which are the soluions of q=aaq and r=a(ar+nil). The automata corresponding to q and r are isomorphic:
a:q->aq, a:aq->q
a:r->(ar+nil), a:(ar+nil)->r.
However the two automata corresponding to aq and ar are NOT isomporphic.
The automaton corresponding to aq has two states:
a:aq->q, a:q->q
The automaton corresponding to r has three states:
a:ar->r,a:r->ar+nil, a:ar+nil->r.

Mistake 5. In CCS there is no distinction between channel and signal on a channel.
What does the handshake - channels or signals?

Mistake 6. The geometry of processes should be explicit and distinct from states of processes.

Mistake 7. In CCS there is no distinction between fx1:AxA->AxA and f:A->A.
As a result there is no distinction between fxg:AxA->AxA and gf:A->A such that gf=fg.
Hence any meaning of causality is lost.

Mistake 8. P || Q should not be equal to Q || P; at most they should be isomorphic.

Mistake 9. There is no distinction between non-communicating parallel and communicating parallel.

Mistake 10. Composition should hide the interface of communication.


Mistake 11. Lack of Zero communication. There is a single tau, but it does not play the role of indicating that two processes have zero communication.

Mistake 12. n processes should be able to synchronize in a single action. This is related to the following:

Mistake 13. There should be processes for each channel which are the identity with respect to parallel
- that transmit at the same time as they receive.

Mistake 14. The simplest examples of processes are functions.
So the category of sets and functions should be an algebra of processes. It has sequential and parallel composition which are related through a distributive law.

Mistake 15. The relation between sequential and parallel should be a distributive law/exactness condition.

Mistake 16. The operation of hiding a channel has the effect of preventing action, not just hiding.
This seems to me to be unphysical, very difficult to implement. Seems a purely mathematical operation.

Mistake 17. The only notion of cycle is through recursion. Real processes cycle through returning to the same state.
Recursion is a different phenomenon, also important. An algebra of processes should have both.

Mistake 18. A process which consists of an infinite number of processes in parallel may be defined.

Mistake 19. The meaning of a CCS term is given by a behaviour, not a process.
A process should have a behaviour, but not just be a behaviour.

Mistake 20. Programs should be expressions in the algebra of processes. Instead, in process algebras programs come first (that is, the free algebra comes first), and processes are defined to be elements of a quotient algebra.

Expanded comment on Mistakes 4 and 17., 10 April 2008
My first problem with a compositional semantics of CCS in terms of automata (abstract labelled transition systems) is as follows:

If you only want automata up to bisimulation you can do it because every automaton is bisimilar to its unfolding tree - but in this case you never can say you returned to the same state - which is one of my basic requisites for state.

Instead a real compositional semantics in terms of transition systems/automata would involve:
(i) defining the automaton A(t) (with initial state) corresponding to a term t by developing rules, (states being terms), (I notice that you only get reachable automata that way)
and
(ii) defining abstract operations on automata, and

(iii) proving that A preserves operations from terms to automata.

If you try to do that then a parallel operation on automata is plausible.
The one I have more difficulty with is instead P+Q.
The only abstract operation on automata I can imagine is gluing the two automata only on the initial state. There is no information to form some kind of union.

However the non-initial part of A(P+Q) can't be the disjoint because at the level of terms we can't distinguish between some identical terms and not others.
How can we tell if states as terms are equal without examining the terms?
The usual LTS of P+Q is not the abstract operation on automata discussed above.

It seems to me you are forced to look at trees instead of automata - that is to deny that you can return to the same state. OR you take automata modulo bisimulation which is the same thing.
In my view, trees and bismulation may be used (and perhaps originated so) to fix a
broken theory. Of course bisimultaion is fundamental as an adjunction to a correct theory.

After writing the above I found in Winskel and Nielsen (Models for Concurrency, 1993) some similar remarks, though they do not arrive at the same conclusions.

"Unfortunately the relationship between the transition systems obtained denotationally and operationally is a little obscure. There are several mismatches.
One is that the categorical sum makes states of the two components of a sum disjoint, a property which cannot be shared by the transition system of the operational semantics, essentially because of incidental identifications of syntax. Furthermore, the transition system for recursive processes can lead to transition systems with transitions back to the initial state. As we have
seen this causes a further mismatch between the denotational and operational treatment of sums. Indeed the denotational treatment of recursive processes will lead to acyclic transition systems, which are generally not obtained with the present operational semantics. Less problematic is the fact that from the very way it is defined the transition systems obtained operationally must consist only of reachable states and transitions. This property is not preserved by the categorical operation of restriction used in the denotational semantics.
Of course, if we use a coarser relation of equivalence than isomorphism then the two semantics can be related. In the next section, it will be shown that, given any term, there is a strong bisimulation (in the sense of [55]) between the reachable states of the transition system obtained denotationally and those got from the operational semantics.

[55] Milner,A.R.G., Communication and concurrency, Prentice Hall,1989."

Mistake 21. (5 May 2008) There is nothing canonical about the parallel operation.
There have been many suggested alternatives, also non-canonical.
At this level of abstraction in mathematical development we seek canonicity.

Mistake 22. (5 May 2008) The fact that CCS is built on Kleene's algebra of behaviours, has permitted the development of an algebra of behaviours without systems.
This is already a conceptual error in Kleene's theorem - which should express the fact that actual behaviour is a morphism of algebras from systems to possible behaviours, together with the fact that every system is generated in the algebra of systems from some particularly simple ones.
The problem with Kleene is that not all automata are given by Kleene expressions.
This has permitted a looseness of ideas in CCS, namely that we are only talking about systems up to bisimulation. Which looseness has of course been justified philosophically.

Mistake 23. (5 May 2008) In my view the principal error (and the chief obstacle to my understanding) of CCS has been the reliance on giving meaning to expressions by means of the primitive methods of SOS.
If instead a system had been associated compositionally to a CCS expression, "operational semantics" would then be straightforward.
It is a delusion to immagine that SOS gives meaning.

Mistake 24. (28 May 2008) The tau action seems to me to be a bad idea, because it is not just the absence of a signal on the boundary, but a positive signal which prevents other synchronizations occurring simultaneously.

Mistake 25. (4 June 2008) A big problem is the lack of appreciation of reflexive graphs, that is of the reflexive transition of a state.
The reflexive edge means lack of communication, not like tau which means positive communication of internal transition.
The reflexive edge allows true concurrency. Tau forces interleaving.
In the presence of reflexive transition there are two possible meanings for restriction,
that of CCS which prevents transmission of signals externally but also prevents some internal transitions, and an alternative, the projection of signals onto the reflexive edge, which is a pure restriction of transmission of signals (the physical cutting of a channel).

Mistake 26. (29 July 2008)
In CCS there are no names for entities, just names for states of entities.
This follows from a decision made by Milner not to distinguish states and agents:
From Communication and Concurrency, Prentice Hall 1989, pages 18,19: "We may loosely think of agent expressions like C and C'(x) as standing for the different possible states of an agent; in general there will be many states which an agent may traverse.
Rather than distinguishing between two concepts - agent and state - we find it convenient to identify them, so that both agent and state will always be understood to mean an agent in some state."
"Truth will sooner come out of error than from confusion." - F. Bacon

Old posts 3: Random finite sequences (8 September 2008)

Random finite sequences, 8 September 2008

Kolmogorov's definition of random finite sequence has the devastating defect that it does not enable one to decide if a given sequence is random or not (except perhaps for the sequence consisting of a single element).

The problem is that the definition is not invariant under change of language.

The truth is that notion defined by Kolmogorov is random_L where L is a computer language. It is simply dishonest to remove the dependence on L.

Old posts 2: History of an equation - (1 tensor delta)(nabla tensor 1)=(nabla)(delta) (15 February 2006)

This is a personal history of the equation (1 tensor delta)(nabla tensor 1)=(nabla)(delta) now called the Frobenius equation, or by computer scientists S=X.

1983 Milano Worked with Aurelio Carboni in Milano, and later in Sydney, on characterizing the category of relations.
1985 Sydney We submitted to JPAA on 12th February the paper eventually published as A. Carboni, R.F.C. Walters, Cartesian bicategories I, Journal of Pure and Applied Algebra 49 (1987), pp. 11-32.
The main equation was the Frobenius law, called by us discreteness or (D) (page 15). 1985 Isle of Thorns, Sussex: Lectured on work with Carboni concentrating on importance of this new equation - replacing Freyd's "modular law". Present in the audience were Joyal, Anders Kock, Lawvere, Mac Lane, Pitts, Scedrov, Street. I asked the audience to state the modular law, Joyal responded with the classical modular law, Pitts finally wrote the law on the board, but mistakenly. Scedrov said "So what?" to the new equation and "After all, the new law is equivalent to the modular law". Nobody ventured to have seen the equation before.
(I asked Freyd in Gummersbach in 1981 where he had found the modular law, and he replied that he found it by looking at all the small laws on relations involving intersection, composition and opposite, until he found the shortest one that generated the rest. We believe that this law actually occurs also in Tarski, A. Tarski, On the Calculus of Relations, J. of Symbolic Logic 6(3), pp. 73-89 (1941) but certainly in the book "Set theory without variables" by Tarski and Givant, though not in the central role that Freyd emphasised.)
At this Sussex meeting Ross Street reported on his discovery with Andre Joyal of braided monoidal categories (in the birth of which we also played a part - lecture by RFC Walters, Sydney Category Seminar, On a conversation with Aurelio Carboni and Bill Lawvere: the Eckmann-Hilton argument one-dimension up, 26th January 1983). This disovery was a major impulse towards the study of geometry and higher dimensional categories.
1987 Louvain-la-Neuve Conference I lectured on well-supported compact closed categories - every object has a structure satisfying the equation S=X, plus diamond=1. Aurelio spoke about his discovery that adding the axiom diamond=1 to the commutative and Frobenius equations characterizes commutative separable algebras, later reported in A. Carboni, Matrices, relations, and group representations, J. Alg. 136:497–529,1991 (submitted in 1988).
After Aurelio's lecture Andre Joyal stood up and declared that "these equations will never be forgotten". At this, Sammy Eilenberg rather ostentatiously rose and left the lecture - perhaps the equation occurs already in Cartan-Eilenberg? Andre pointed out to us the geometry of the equation - drawing lots of 2-cobordisms. During the conference in a discussion in a bar with Joyal, Bill Lawvere and others, Bill recalled that he had written equations for Frobenius algebras in his work F.W. Lawvere, Ordinal Sums and Equational Doctrines, Springer Lecture Notes in Mathematics No. 80, Springer-Verlag (1969), 141-155.
The equations did not incude S=X, diamond=1, or symmetry, but the equation S=X is easily deducible (see Carboni, "Matrices, ...", section 2). Bill's interest, as ours, was to discover a general notion of self-dual object. In Freyd's work there is instead the rather non-categorical assumption of an involution satisfying X^opp=X.
2004 Joachim Kock's book I jump to this because it enables me to discuss quickly later developments. The fronticepiece of the book Joachim Kock, Frobenius algebras and 2D topological quantum field theories, Cambridge University Press 2004 is a picture of our equation S=X in the geometric form pointed out to us by Andre Joyal in 1987, the form which suggests the name S=X (maybe Z=X might be more suggestive but I prefer S=X). Kock discusses Lawvere's work on page 121, but, unaware of our introduction of the equation in 1985, he states that "The first explicit mention of the Frobenius relation, and a proof of 2.3.4, were given in 1991 by Quinn" in Frank Quinn, Lectures on axiomatic topoogical quantum field theory, in Geometry and quantum field theory, American Mathematical Society, 1995. Kock's very pleasant book is a readable account of the relation between the algebra and the geometry of the Frobenius equation. It does not describe the physical intuition behind topological field theory, a concept introduced by Witten in 1988 in Edward Witten, Topological quantum field theory, Communications in mathematical physics, 117, 353-38, 1988.

For another account of the history of category theory from an Australian point of view see the article Ross Street, An Australian conspectus of higher categories, Institute for Mathematics and Applications Summer Program: n-categories: Foundations and Applications, June 2004.

Curiously, this article does not mention our discovery of the Frobenius equation.

Old posts 1: My interest in monoidal bicategories (7th April 1997)

I am gradually importing old posts from my department pages.
I fear that very shortly I will lose my departmental page at the University of Insubria and hence I am starting to move my old posts to this blog spot.  The department which was originally formed at request as a kernel of a possible Arts faculty in Como seems to have lost support at all levels (and is under attack by other departments) - this all in the context of university reforms. I regret the situation since I think this department could have been an interesting and productive collaboration, of considerable value to Como.
An old article first posted in 1997

My interest in monoidal bicategories.
RFC Walters 7th April 1997

1966-70 In my PhD thesis (ANU) about category theory and universal algebra I used the 2-category structure of Cat to define things and hence became interested in pasting cells.
1970 I visited Mac Lane (Chicago) as research associate and discovered that the category PA of presheaves on a small category is 'total' which lead to a collaboration with Ross Street beginning in 1970 of the 2-categorical properties of yoneda yA:A->PA. We were trying to characterize Sets in Cat but in analogy to studying 2 in Sets by looking at arrows A->PB (here PB means subsets of B) we studied functors A->PB.
1974 I spoke on his work at a conference at UNSW organized when Peter Freyd was here by Max Kelly. The paper appeared much later in "Yoneda structures". The beginning of the study of Mod and Rel was already there.
1980 I visited Milan and discovered that the sheaf condition can be expressed in terms of Cauchy completeness of categories enriched over a bicategory of 'relations' - this work appeared in Cahiers. A group of us studied categories enriched over bicategories, and bimodules between them. We looked at properties which lifted from the base bicategory to the bicategory of bimodules.
1982 Lifting the tensor product lead to my idea with Lawvere and Carboni that the classical treatment of this in terms of symmetry could be explained in terms of a tensored one-object bicategory and a Eckman-Hilton argument - I gave a lecture on this on 26th January 1983 which inspired Ross to discover braided monoidal categories with Joyal (whose motivation was different).
1983 I began the study with Carboni of Rel as a monoidal bicategory in Milan December 1983. It was completed in January 1985. Aurelio had previously done work in the direction of Freyd on relations regarding Rel as a category and using the mysterious 'modular law'.
1985 I believe I lectured on Rel at Sussex. The paper had been submitted some time before and Scedrov had written a report recommending rejection, but it was eventually accepted. A third strand was that Mike Johnson and I had begun work (ask Mike when he began as my student) on an alternative version of the n-category generated by an n-simplex - the higher associative laws. (I had suggested to him originally a different problem: describing cech cocyles as categories enriched over an n-category.)
1985 Mike and I presented this at Bangor. At around that point I began to be interested in computer science. I gave a couple of lectures in the Sydney Category Seminar. I occasionally tried to get divert Mike's attention in this direction. That took me off into distributive, extensive categories, only to return to monoidal bicategories (now with feedback) in 1994.
1992 I began the study of concurrency with Nicoletta Sabadini.
1994 After a visit of Bloom, seeing his work on iteration theories I gave a lecture at the Sydney Half-hour Seminar on machines as arrows (29th April). Since then Giulio Katis, Nicoletta Sabadini and I have worked extensively on this idea, one result being the 1997 paper "Bicategories of Processes". An earlier version of the paper was written presented at CATS '94. The work with Henry Weld on circuits, and the earlier work with Wafaa Khalil on 'functional processes' have been very influential - in fact there is an exercise in the 1992 Cambridge version on my book which appropriately interpreted is about the monoidal bicategory of Elgot automata.