Life in Italy 6: Student fees

Recently there has been protests from the students at the University of Insubria because they say their fees have increased, in some cases by a factor of three, owing to a new method of calculating fees.

The pro-rector of the university, Giorgio Conetti, is quoted as follows in the Corriere di Como:
«A causa della grave limitazione del finanziamento pubblico alle Università, l’impegno per il mantenimento invariato dell’offerta didattica sarà particolarmente gravoso e la componente della contribuzione studentesca al bilancio universitario diverrà più significativa».

This maintenance of the courses is in the face of the reform which (you may have seen below) requires that the faculty of Science in Como will require 112 staff instead of the present 84 or so.

A student in a course for which there are many enrolled might be tempted to think that she is being required to pay for the luxury of other courses which have very small enrollment.

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.

Borromean Rings

The ticket to enter the castle, the Rocca Borromeo, in Angera has a mistaken picture of the Borromean rings.

Life in Italy 5: Escamotage continued

The Italian phrase is: "Fatta la legge, trovato l’inganno".
That is, as soon as the law is made, we will find the loopholes.

Instead of reacting to a new law (for example the reform of the University system) by seeking a rational response, that is, a response to the substance and the intention of the law,  we look first for the loopholes.

The result is a mess.