Subject: categories: revised preprint: A monadic approach to polycategories

From: J=FCrgen Koslowski <[email-masked]>
Date: Sun, 18 Jan 2004 11:21:07 +0100 (CET)

Dear Colleagues,

Belated best wishes for 2004!

A substantially revised (and improved ;-) version of my CTCS02 paper
"A monadic approach to polycategories" is available on my WEB-page:

http://www.iti.cs.tu-bs.de/TI-INFO/koslowj/RESEARCH/Moapp.ps.gz

The abstact is appended below.

-- Juergen Koslowski

%%  Abstract for: A monadic approach to polycategories

  Polycategories should form a rather natural generalization of
  multicategories: besides the domains also the codomains of morphisms
  are allowed to be strings of objects.  But while small
  multicategories can be elegantly characterized as monoids in a
  bicategory of set-spans with free set-monoids as domains, no
  such description of small polycategories seems to have been known so
  far.

  To address this problem, we first investigate distributive laws in
  the sense of Beck between cartesian monads S and T on a category X
  with pullbacks.  Some ot these can serve as tools for constructing
  new bicategories of S-T-spans over X, and monoids in such
  bicategories should be viewed as S-T-categories.  We identify a
  class of ``super-cartesian'' distributive laws that indeed produce
  such bicategories in a straightforward manner.  However, if S and T
  coincide with the free monoid monad (_)^* on set, there is no
  distributive law to get this construction off the ground.

  Since polycategories display a high degree of symmetry, a more
  symmetric substitute for distributive laws would be desirable.  If
  we decompose (_)^* into the free semigroup monad and the exception
  monad, a relation on (_)^{**} can be defined by means of three
  super-cartesian distributive laws that still allows us to construct
  a bicategory of (_)^*-}(_)^*-spans.  Its monoids turn out to be
  precisely the small planar polycategories.  General polycategories,
  as introduced by Szabo, require a different construction and a span
  instead of a relation.  However, only the notion of planar
  polycategory admits a 2-dimensional generalization, where objects
  are replaced by typed 1-cells.  The resulting ``fc polycategories''
  have essentially the same characterization as planar polycategories,
  but over the base grph rather than set.  In view of other
  shortcomings of Szabo's general concept this suggests that the
  planar variant of polycategories may be the ``correct''
  generalization of multicategories.

  One of the three distributive laws used in the construction above
  behaves like a ``complementation'' on the free semigroup monad and
  seems to be new.  We identify its algebras as associative double
  semigroups.  In fact, the free such structure on a set B can be
  extended from B^{++} to an associative double monoid structure on
  B^{**}.

  We then turn to the fundamental question, which spans between TS and
  ST correctly generalize (super-cartesian) distributive laws and
  provide an essentially associative composition for S-T-spans over X
  with canonical units.  This contrasts with Elisabeth Burroni's
  approach [BurroniE73], who weakened the notion of associativity for
  her notion of D-categories in order to encompass the non-cartesian
  power-set monad.  Our definition of (super-cartesian) generalized
  distributive law is best formulated in the fc-multicategory of
  spans and morphisms in [X,X]; this clarifies the notion of
  (super-cartesian) distributive law and justifies the added
  generality.

  Finally, we show how by first quotienting the bicategory X-spn the
  constructions outlined above can be used even for weakly cartesian
  monads .  In particular this applies to the free commutative monoid
  monad, which fails to be cartesian.  We than adapt the construction
  for planar polycategories to obtain symmetric polycategories in a
  similar fashion.

--=20
Juergen Koslowski               If I don't see you no more on this world
ITI, TU Braunschweig               I'll meet you on the next one
[email-masked]               and don't be late!
http://www.iti.cs.tu-bs.de/~koslowj      Jimi Hendrix (Voodoo Child, SR)