Date: Sun, 13 Oct 1996 10:43:39 -0300 (ADT)
Subject: 2-categories without the interchange law
Date: Sun, 13 Oct 1996 14:32:23 +0900
From: miyoshi@ccb.shukutoku.ac.jp
Dear colleagues:
I am looking for any information or reference about
2-categories *without* the well-known interchange law:
when a,b,c,d are 2-cells and compositions are defined,
(d | c) o (b | a) = (d o b) | (c o a).
In paticular, I am interested in the treatment of (weighted) limits.
And 3-dimensional structures in which
3-cells represent the only one direction of this law:
(d | c) o (b | a) => (d o b) | (c o a).
are also interesting for me.
Any advice is welcome. Thank you in advance.
----
Hiroyuki Miyoshi
The College of Cross-Cultural Communication and Business, Shukutoku Univ.
miyoshi@ccb.shukutoku.ac.jp
Date: Mon, 14 Oct 1996 10:01:51 -0300 (ADT)
Subject: Re: 2-categories without the interchange law
Date: Mon, 14 Oct 1996 17:27:11 +1000
From: Ross Street
A response to the questions of Hiroyuki Miyoshi
>The College of Cross-Cultural Communication and Business, Shukutoku Univ.
>miyoshi@ccb.shukutoku.ac.jp
These "2-categories without the interchange law" are categories
enriched in Cat with a "funny" closed structure: the internal
hom [A,B] of two categories A, B is the category whose objects
are functors f: A --> B and whose arrows s : f --> g are families
of arrows s_a : fa --> ga in B (no naturality requirement!).
Strangely J.G. Stell and I seem to have independently come up with
the same name for them: sesquicategories. (In earlier work Sammy
Eilenberg and I were doing on rewriting systems, Sammy was calling them
one-and-a-half-categories or 3/2-categories.) See my paper
Categorical structures, Handbook of Algebra, Volume 1 (editor M.
Hazewinkel; Elsevier Science, Amsterdam 1996) 529-577
and
J.G. Stell, Modelling term rewriting systems by sesqui-categories,
Technical Report TR94-02 Dept Computer Science, Keele University.
Carolyn Brown and Doug Gurr also used them in studying Petri nets
(see Lecture Notes in Comp Sci 616 &/or 623 1992).
Also relevant are:
A.J. Power & E. Robinson, Premonoidal categories & notions of computation,
Math Struct in Comp Sci 11 (1993).
John Power, Premonoidal categories as categories with algebraic structure,
(preprint, but ask ).
Also the category 2-Cat of 2-categories and 2-functors has various tensor
products. The one originally described by John W. Gray in SLNM 391 is
what you need for your 3-cell (d | c) o (b | a) => (d o b) | (c o a).
That is, again your notion is an enriched category. If you are happy
with this 3-cell to be invertible (which you probably are not), this
gives what we call Gray-categories which feature in
R. Gordon, A.J. Power and R. Street, Coherence for tricategories,
Memoirs of the American Math Society 117 (1995) Number 558 (ISSN 0065-9266)
where you will find other references.
So this indeed means that the theory of weighted limits applies to all
these structures. But I don't know of anyone who has developed the
specific properties of weighted limits in these cases along the lines
of my old paper
Limits indexed by category-valued 2-functors, J. Pure Appl. Algebra 8
(1976) 149-181; MR53#5695
in the case of 2-categories.
Best wishes,
Ross
Date: Mon, 14 Oct 1996 15:19:22 -0300 (ADT)
Subject: Re: 2-categories without the interchange law
Date: Mon, 14 Oct 1996 15:15:27 +0100
From: Rudger Kieboom
A response to the questions of Hiroyuki Miyoshi
>The College of Cross-Cultural Communication and Business, Shukutoku Univ.
>miyoshi@ccb.shukutoku.ac.jp
In addition to Ross Street's response, it might be useful to mention that
sesquicategories (and other kinds of relaxed 2-categories) are also used in
categorical homotopy theory, for instance in
Marco Grandis, Homotopical Algebra in Homotopical Categories, Appl.Categ.Struct.
2 (1994),pp.351-406.
Best wishes,
Rudger Kieboom.
Date: Tue, 15 Oct 1996 21:08:38 -0300 (ADT)
Subject: Re: 2-categories without the interchange law
Date: Tue, 15 Oct 1996 14:18:41 +0100
From: Marco Grandis
Rudger Kieboom quoted my paper
Marco Grandis, Homotopical Algebra in Homotopical Categories,
Appl.Categ.Struct. 2 (1994), pp.351-406
in connection with Hiroyuki Miyoshi's question on "2-categories without the
interchange law", and 3-dimensional structures in which the interchange
equality is replaced by a 3-cell.
In my paper, some relaxed versions of 2-categories are studied, abstracting
the 2-dimensional properties of and
other situations where homotopy arises.
Loosely speaking, the main notion can be described as a "2-category relaxed
up to an equivalence relation between 2-cells (homotopies)"; this
truncation allows one to avoid 3-cells (homotopies of homotopies) and their
operations. The interchange law, as well as the associativity of the
vertical composition of 2-cells, are only assumed up to this equivalence
relation.
Some weighted (co)limits are studied, namely *homotopy pullbacks* (comma
squares, with a strict 1-dimensional universal property and a relaxed
2-dimensional one).
The category of chain complexes (over any additive category) is a simple,
algebraic example of such a structure, which is also a sesquicategory in
the sense of Ross Street (here, the vertical composition of homotopies is
strictly associative) and actually a "sesquigroupoid", since 2-cells have
strict inverses re vertical composition. But the interchange law only holds
up to second order homotopy.
Finally, I would like to add that, if one does want to treat higher order
cells (homotopies), it may be useful to introduce the *cylinder*
endofunctor and its powers (or, dually, the *path* endofunctor), to reduce
cells of any order to ordinary maps, and their operations of any order to
the basic, low order ones; some preprints on such a setting -which goes
back to a classical Kan's paper- have been announced here.
With best regards,
Marco Grandis
Date: Tue, 15 Oct 1996 21:07:46 -0300 (ADT)
Subject: Re: 2-categories without the interchange law
Date: Tue, 15 Oct 1996 07:43:03 +0200
From: Giulio Balestreri
Good Morning,
I'm a Phd student in Rome.
I'd likeonly to say that in the paper
of Grandis an h-categorical approach
is used to homotopical algebra.
I've used it to represent
a kindof reduction between terms
LNCS 1128
Thank a lot. Nice to hear You.
giulio balestreri
Date: Wed, 16 Oct 1996 11:57:10 -0300 (ADT)
Subject: Re: 2-categories without the interchange law
Date: Wed, 16 Oct 1996 15:00:11 +0900
From: Hiroyuki Miyoshi
Dear colleagues:
I am glad to receive many response.
Most people refered to sesqui-categories or Gray-categories.
Therefore I would like to reply by this (long) message.
These categories are interesting and important, I think.
Indeed, I've already used them in my work on
categorical model of rewriting logic
(a brief description will appear in ENTCS Vol.4).
And I had some interesting information on them, especially concerning
with homotopy theory, and hope the thread on them to be continued in
this mailing list.
But what now I want is slightly different and rather simple-minded.
The important point is that a sesquicategory (and a Gray-category)
don't have the horizontal composition of 2-cells.
So we cannot describe both sides of the interchange law.
--- o ---
I would mention my simple motivation. In the paper:
C. Brown and D. Gurr,
Timing Petri Nets Categorically,
in Proc. of 19th ICALP, LNCS.
authors say about a 2-category with the "lax" interchange law
(d o c) * (b o a) =< (d * b) o (c * a)
for the time structure of Petri nets.
But they did not give precise definition,
and I did not know this categorical structure.
When we generalaize the categorical model of Petri nets to the
2-categorical model of rewriting in the Meseguer-Montanari style,
for example, we can think of horizontally composable 2-cells as to be
executed in parallel.
Here we will consider durations of rewriting. we assign a nonnegative
real number to each rewriting. Roughly thinking, if we compose
2-cells vertically, the duration of the composed 2-cell is the sum of
two duration, and when composing 2-cells horizontally, the duration is
the maximum of two durations.
According to the time-as-monoid view, we can think a 2-graph structure
for time:
- 0 and 1-cell is respectively only one.
- the homcategory is monoid.
Unfortunately, this structure should not be a 2-category in the
meaning of duration. When a, b, c, d are 2-cells, and the
sequential composition is o and parallel one is *, then
(d o c) * (b o a) and (d * b) o (c * a) should not be equal in general.
But anyway some horizontal composition corresponding to parallel
computation is needed.
--- o ---
Thus, to consider this time-structure,
we take an equational presentation of 2-categories in e.g.:
A. J. Power adn C. Wells
A Formalism for the Specification of Essentially-Algebraic Structures
in 2-Categories, MSCS Vol.2, 1-28, 1992.
which is :
A0,A1,A2: Sets corresponding to 0,1,2-cells.
Ax1: A category structure consisting of A0 as objects and A1 as arrows
(called the horizontal category. domh, codh and idh are
domain, codomain and identity-cell functions. Its composition is o).
Ax2.:A category structure consisting of A0 as objects and A2 as arrows
(called the vertical category. domv, codv and idv are
domain, codomain and identity-cell functions. Its composition is *).
Ax3: When alpha in A2,
domh alpha = domh (idv (domv alpha)) = domh (idv (codv alpha)), and
codh alpha = codh (idv (domv alpha)) = codh (idv (codv alpha))
Ax4: When A in A0,
idh A = idv (domv (idh A))
(idh A = idv (codv (idh A)) is also ture.)
Ax5: When alpha and beta in A2, if codh alpha = domh beta, then
idv ( domv (beta o alpha)) = idv (domv beta) o idv (domv alpha)
idv ( codv (beta o alpha)) = idv (codv beta) o idv (codv alpha)
Ax6 (interchange law): When alpha, beta, gamma, delta in A2,
(delta o gamma) * (beta o alpha) = (delta * beta) o (gamma * alpha)
if all compositions are defined.
Here, if we omit Ax6, then we have a weakened structure of 2-cateogry.
I think that this reflexive 2-graph is *the* structure which is a
2-category without interchange law. This structure cannot be a
category enriched in Cat which has only exactly two symmetric monoidal
closed structures; but it satisfies requirements of the time-structure
for concurrent rewriting.
I don't know whether this structure has been known to the category
theory community. And I would like to use some limit construction
like inserters in this structure. So I sent my previous message.
Again, any comment is welcome. Thank you.
Yours scincerely
P.S.
To Dr. J. Power: Shukutoku University is near to Tokyo.
I will visit you and Kinoshita-san at ETL. Thank you.
----
Hiroyuki Miyoshi
The College of Cross-Cultural Communication and Business, Shukutoku Univ.
1150-1 Fujikubo, Miyoshi-machi, Iruma-gun, Saitama 354, Japan
Mail: miyoshi@ccb.shukutoku.ac.jp
Tel: +81 492 74 1511
Fax: +81 492 74 1525
Date: Wed, 16 Oct 1996 13:24:37 -0300 (ADT)
Subject: Re: 2-categories without the interchange law
Date: Wed, 16 Oct 1996 17:22:45 +0200
From: Pierre Ageron
The "funny" monoidal closed structure on Cat mentionned by Ross Street is known
in France as "maigre". Besides the cartesian closed structure, it is the only
monoidal closed structure on Cat (this was proved by Lair and Foltz in the seventies
as an application of sketch theory). The same thing is true for the category Gmul of
multiplicative graphs in the sense of Ehresmann (also known as elementary sketches),
but this last category has also has a lot of (non necessarily monoidal) closed
structures : 42, if I remember Coppey's work correctly.
Enriched multiplicative graphs were studied extensively by Florence Cury in several
papers, culminating in her work about "suffisante completude connexe", a very
long paper she wrote in the last years of her life and that recently appeared in
Diagrammes. Multiplicative graphs (resp. categories) enriched in Gmul (resp. Cat)
with the "maigre" closed structure are called "amphi-graphes"
(resp. "amphi-categories") in that paper (instead of "sesqui-"...).
For the purpose of rewriting theory in the essentially algebraic context,
she also introduced "amphi-syntaxes" generalizing Coppey's "syntaxes".
The connections of her work with Stell's paper are very interesting.
Pierre Ageron
Date: Mon, 21 Oct 1996 11:52:25 -0300 (ADT)
Subject: 2- and sequi-categories for computer science
Date: Mon, 21 Oct 1996 15:26:54 +0200
From: gadducci@DI.Unipi.IT
Dear colleagues,
let me add my two cents on the applications of 2- and sesqui-categories to
computer science. Maybe I got carried away, and I expressed my point of
view on the topic with too much details: I apologize in advance for the
lenghty mail.
Please note also that my papers can be found at
http://www.di.unipi.it/~gadducci/papers
Best regards,
Fabio
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
It is well known since the work of Rydeheard and Stell [RS87] and Power
[P89] that cartesian 2-categories are a suitable model for term rewriting
systems.
The underlying 1-category is just the standard algebraic theory over a
signature \Sigma, while for each basic rule r: s --> t of the rewriting
system we introduce a cell r_a: s_a --> t_a on the associated elements of
the algebraic theory, then freely generating the cells starting from these
basic cells.
The resulting 2-category is an adequate model for term rewriting, in the
sense that there exists a (finite) derivation s --> t in the rewriting
system iff there exists a cell with source s_a and target t_a.
An an example, if we have the rules r_1: a --> b and r_2: f(x) --> g(x),
then we have the derivations
(\lambda, r_1): f(a) --> g(a)
(1,r_2): g(a) --> g(b)
where the first components indicates the position in the term at which the
rule is applied; and the corresponding cells
id_a o r_1 : a o f --> a o g
r_2 o id_g : a o g --> b o g
Of course, 2-categories offer a somewhat more abstract characterization
than the set-theoretical derivation relation, since the coherence axioms
equate derivations which can be considered different for the order in which
they execute "independent" rewrites.
If we consider instead a sesqui-category built from a rewriting system, the
resulting sesqui-category is still an adequate model for the rewriting
system relation, even if less derivations are equated, since the
interchange axiom is dropped.
In recent years there has been in Pisa some interest for these models, due
to their link with rewriting logic [M92], and some algebraic properties of
these equivalences have been studied.
In [LM96] it is shown that the equivalence associated to 2-categories
corresponds to the well-known "permutation equivalence" introduced by Le'vy
for \lambda-calculus, while in [CGM95] we axiomatize an equivalence over
derivations, that we called "disjoint", which corresponds to the
equivalence induced by sesqui-categories.
Moreover, in [CGM95] we show that, if we consider, for any term t, the
class of cells starting from the associated element t_a, this class fails
to form a prime algebraic domain (that is, a finitary distributive complete
partial order). This is disappointing from a concurrent point of view,
since this requirement is considered a fundamental one in order for a model
to describe reasonably the behaviour of a distributed machine implementing
the reduction process. Instead, this class is indeed a pad in the
sesqui-categorical case.
We argued also that neither this case was satysfying, since dropping the
interchange axiom limits too much the parallelism of the underlying
machine, and we suggested a 2-categorical structure with a kind of weak
cartesianity. Some preliminary result can be found in [G96], while in
[CGM96] we show that a kind of "weak" algebraic theories we called
s-monoidal theories are in fact able to describe term graphs: terms are not
considered trees anymore, but instead graph structures, able to distinguish
between sharing of subterms. We first introduced an alternative description
of cartesian categories (along the line of [J93]) as symmetric monoidal
categories with two natural transformations
! : 1 --> 0
D : 1 --> 2
and then we dropped their naturality, resulting e.g. in
(s \times s) o D \= D o s for s: 1 --> 1
The s-monoidal 2-categories then are able to describe a more refined notion
of derivation, i.e. term graph rewriting. And the resulting classes of
cells starting from a generic element t_a always form a pad.
Finally, a last argument if favour of 2-categories is also given by the use
of more general structures, namely double-categories (both 2-categories and
double-categories can be considered as internal categories in Cat), as
suitable models of concurrent systems. As shown in [G96] and expecially in
[GM96], these structures are used to decribe the (truly concurrent)
semantics of process algebras.
Let me end this little detour simply stressing that, in my opinion,
2-categories are more suited than sesqui-categories as a model for term
rewriting and that, in general terms, their application (and the
application of internal categories as a whole) to computer science is a
field that should be further explored.
[CGM95] Corradini - Gadducci - Montanari, Relating Two Categorical Models
of Rewriting, RTA'95, LNCS 914
[CGM96] Corradini - Gadducci - Montanari, An Algebraic Description of Term
Graphs, draft
[G96] Gadducci, On the Algebraic Approach to Concurrent Term rewriting,
Ph.D. thesis, report TD 2-96, University of Pisa
[GM96] Gadducci - Montanari, The Tile Model, report TR 96-27, University of
Pisa, submitted for publication
[J93] Jacobs, Semantics of Weakening and Contraction, Annals of Pure and
Applied Logic, 69
[M92] Meseguer, Conditional Rewriting Logic as a Unified Model of
Concurrency, Journal of Theoretical Computer Science 96
[P89] Power, An Abstract Formulation for Rewrite Systems, CTCS'89, LNCS 389
[RS87] Rydeheard - Stell, Foundations of Equational Deduction, CTCS'87, LNCS 283
+ "No man is poor who can do what he likes to do once in a while" Carl Barks +
Fabio Gadducci gadducci@di.unipi.it +--------------------------+
Dipartimento di Informatica Home : +39 50 541725 | "The weight of the world |
Corso Italia, 40 Office: +39 50 887268 | is love." |
I - 56125 Pisa - ITALY Fax : +39 50 887226 | Allen Ginsberg |
http:\\www.di.unipi.it\~gadducci\gadducci.html +--------------------------+
+ "I keep my feeling buried inside a sea urchin" Ezra Pound +
Date: Mon, 21 Oct 1996 14:16:47 -0300 (ADT)
Subject: Re: 2-categories without the interchange law
Date: Mon, 21 Oct 1996 17:30:24 +0100
From: John G. Stell
On the question of what to call `2-categories without interchange':
Shouldn't we agree to call `2-categories without interchange'
`one and a half categories' and use `sesqui-categories' for
the analogously weakened notion of bicategory?
I think it was John Power who first suggested this to me.
John Stell
Date: Tue, 22 Oct 1996 20:40:23 -0300 (ADT)
Subject: Re: 2-categories without the interchange law
Date: Mon, 21 Oct 96 20:40:00 -0700
From: Art Stone
Locally, here, we've been using "one-and-a-half-categories" for 2-categories
that in their 2-cell structure are pre-ordered sets -- for the last decade
and more. (But this has never been formal, or in print.)
Art Stone.