Wednesday, September 30, 2009

Conferences: Category Theory 2010 (CT2010)

Next years International Category Theory meeting will take place in Genoa, Italy.
Dates: Sunday, 20 June, to Saturday, 26 June 2010.

The Organizing Committe is:
Marco Grandis, Sandra Mantovani, Eugenio Moggi, Giuseppe Rosolini, Robert Walters.

Further details will be posted here, and naturally elsewhere, when available.

Labels: ,

Saturday, September 26, 2009

A blog worth visiting - The Stubborn Mule

The Stubborn Mule's Perspective is a blog of Sean Carmody, whom I knew as a student in Sydney. In fact his fourth year thesis was the extension of the Todd-Coxeter procedure to categories and functors. The blog involves also other students I knew in Sydney.

One of the main activities of the blog is the display of economic and other measurements pulled out of the net.

I always liked the subject of display of data since I read (?) the book by Edward Tufte, The Visual Display of Quantitative Information. In particular I liked the famous representation by Charles Joseph Minard of the Russian campaign of Napoleon. (Actually, now that I think about it, another amazing work of graphical represntation is Gray's Anatomy,)

On the Stubborn Mule you will see the advances in representation of data produced by computer technology.

I am hoping we will also see more conclusions, concentration of information, and identification of underlying causes.

Labels: ,

Thursday, September 24, 2009

Cospan-span article posted at arxiv, 24 September 2009

I have just posted our new article on
Title: Cospans and spans of graphs: a categorical algebra for the sequential
and parallel composition of discrete systems
Authors: L. de Francesco Albasini, N. Sabadini, R.F.C. Walters
on arxiv.

I might write some blogs explaining the ideas behind this paper, possible expanding this post.

Two points in the paper: I have been thinking for years about the relation between sequential and parallel operation in discrete systems. It is somehow the relation between time and space.
The earliest ideas are in my book "Categories and Computer Science (Cambridge)", where I emphasised distributive categories. But finally this summer with Nicoletta we have become convinced that the algebra is one of lax double categories of cospans of spans (or spans of cospans).
The distributive law plays a fundamental role in the paper.

More later. Or see the paper.

Labels: ,

My Number Theory book

My Number Theory book (Carslaw Publications) is currently being translated into Japanese and will be published in Japan, I guess early next year, by
Iwanami Shoten, Publishers
2-5-5 Hitotsubashi, Chiyoda-ku
Tokyo 101-8002 JAPAN

Labels:

Wednesday, September 23, 2009

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

Labels: , , ,

Monday, September 21, 2009

What do I believe of physics?

A depressing thought struck me recently. As a student many many years ago my view of the world was shaped by courses on physics and chemistry.

And most of the things I learnt then I still believe.

For example, Newton's law of gravitational attraction.
(Most of my life has been a struggle against gravity, and gravity has usually won!)

The question is: what of the things I have been told by physicists since then do I really believe?

For example, I do believe the experimental evidence for quantum mechanics, and that there is something profound involved. I don't believe in many worlds.

I don't believe in black holes (at least, as described by physicists).

The problem is that I don't even know what physicists really believe. Do they believe with Tegmark in multiverses? Do they believe in 10 or 11 dimensional space?

I am reminded of an article by Lord Kelvin: On the Age of the Sun’s Heat, Macmillan's Magazine, vol. 5 (March 5, 1862), pp. 288-293, in which after discussing the meteoric theory for the origin of the sun's heat he says:

"That some form of the meteoric theory is certainly the true and complete explanation of solar heat can scarcely be doubted, when the following reasons are considered:

(1.) No other natural explanation, except by chemical action, can be conceived. (my bold face).

(2.) The chemical theory is quite insufficient, because the most energetic chemical action we know, taking place between substances amounting to the whole sun’s mass, would only generate about 3,000 years’ heat.[9]

(3.) There is no difficulty in accounting for 20,000,000 years’ heat by the meteoric theory."

Labels:

Interdisciplinary research 1969-1989-2009

I realized just now that this year has a certain significance for me. I finished my PhD in 1969 (submitted January 1970). For 20 years I taught mathematics and did research in category theory (I had written two papers on number theory before that, and my book on number theory is being translated into Japanese at the moment.)

In 1989 I gave my first course on categories and computer science. So for 20 years I have been doing research on computer science. (I am now professor of computer science in Como, and have taught operating systems for 8 years.)

The point of this post is that I feel to be at last a interdisciplinary researcher in depth, even though I am still much better accepted in the category theory community than in the computer science community. (I think that is partly due to the delay in the acceptance of ideas - my papers of the 1970's are still quoted, so that my categorical work has had 40 years of exposure.)

I am curious to know if my computer science research will be quoted in 20 years.

Labels: , ,

Wednesday, September 16, 2009

The responsibility of referees, 12 May 2009.

The responsibility of referees, 12 May 2009.
(transferred from my departmental home page)

Refereeing is an onerous and thankless task. In these days of the degeneration of the processes of scientific research the job has become an almost impossible one. My impression now is that almost no-one reads papers, refereeing jobs are given to students, etc, as a result of the enormous boom in publication of articles with little original content. This boom is fed by the adoption of mechanical means of judging worth, for example paper numbers, impact factor, Hirsch index, etc.

We seem to have abandoned our responsibility to make judgements.

The result is that referees now tend to write superficial reports, while, being anonymous like drivers on the highway, retaining the right to abuse the authors on the basis of prejudice.

I don't exclude myself from these comments.

It is not just referees but editors who need to consider their responsibilities. There has been a case discussed recently, about which I have only a vague opinion (not having studied the case), of the journal Chaos, Solitons & Fractals. Though much criticism has been made of the publishers, and the founding editor, none has been made of the Associate editors or honorary editors which include such respectable names as R.M. May and G. Casati. It is clear that there has been a separation of responsibility, probably also as a result of the boom in publication.

I have a final point to make: to put the responsibility clearly on referees and editors I want to make public when a paper of mine is rejected. This makes it possible over time to make some comparison between accepted and rejected papers, something which is not available at the moment.

As a first example, CALCO09 rejected our paper "L. de Francesco Albasini, N. Sabadini, R.F.C. Walters, The compositional construction of Markov processes, arXiv:0901.2434v1, 2009."

Labels: , , ,