This paper focuses on a property of enriched functors reflecting the factorisation of morphisms, used in concurrency semantics. According to Lawvere [F.W. Lawvere, State categories and response functors, 1986, Unpublished manuscript], a functor strictly reflecting morphism factorisation induces a notion of state on its domain, when it is considered as a control functor. This intuition works both in case of physical and computing processes [M. Bunge, M.P. Fiore, Unique factorisation lifting functors and categories of linearly-controlled processes, Math. Structures Comput. Sci. 10 (2) 2000 137 163; M.P. Fiore, Fibered models of processes: Discrete, continuous and hybrid systems, in: Proc. of IFIP TCS 2000, in: LNCS, vol. 1872, 2000, pp. 457 473]. In this note we investigate a more general property in the family of models we proposed elsewhere for communicating processes, and we assess their bisimulation relations [S. Kasangian, A. Labella, Observational trees as models for concurrency, Math. Structures. Comput. Sci. 9 (1999) 687 718; R. De Nicola, D. Gorla, A. Labella, Tree-Functors, determinacy and bisimulations, Technical Report, 02/2006, Dip. di Informatica, Univ. di Roma ``La Sapienza'' (Italy), 2008 (submitted for publication), http://www.dsi.uniroma1.it/%7Egorla/papers/DGL-TR0206.pdf]. Hence, we adapt the notion of ``Conduché condition'' [F. Conduché, Au sujet de l'existence d'adjoints à droîte aux foncteurs image reciproque dans la catégorie des catégories, C. R. Acad. Sci. Paris 275 (1972) A891 894] to the context of enriched category theory. This notion, weaker than the original ``Moebius condition'' used by Lawvere, seems to be more suitable for the description of the concurrency models parametrised w.r.t. a base category via the mechanism of change of base, actually. The base category is a monoidal 2-category; a category of generalised trees, Tree, is obtained from it. We consider Conduché Tree-based categories, where enrichment reflects factorisation of objects in the base category. We prove that a form of Conduché's theorem holds for Conduché Tree-functors.We also show how the Conduch é condition plays a crucial role in modelling concurrent processes and bisimulations between them. The notions of ``state preservation'' and ``determinacy'' [R. Milner, Communication and Concurrency, Prentice Hall International, 1989] are formally characterised.
Conduché property and Tree-based categories / S. Kasangian, A. Labella. - In: JOURNAL OF PURE AND APPLIED ALGEBRA. - ISSN 0022-4049. - 214:3(2010 Mar), pp. 221-235. [10.1016/j.jpaa.2009.05.008]
Conduché property and Tree-based categories.
S. KasangianPrimo
;
2010
Abstract
This paper focuses on a property of enriched functors reflecting the factorisation of morphisms, used in concurrency semantics. According to Lawvere [F.W. Lawvere, State categories and response functors, 1986, Unpublished manuscript], a functor strictly reflecting morphism factorisation induces a notion of state on its domain, when it is considered as a control functor. This intuition works both in case of physical and computing processes [M. Bunge, M.P. Fiore, Unique factorisation lifting functors and categories of linearly-controlled processes, Math. Structures Comput. Sci. 10 (2) 2000 137 163; M.P. Fiore, Fibered models of processes: Discrete, continuous and hybrid systems, in: Proc. of IFIP TCS 2000, in: LNCS, vol. 1872, 2000, pp. 457 473]. In this note we investigate a more general property in the family of models we proposed elsewhere for communicating processes, and we assess their bisimulation relations [S. Kasangian, A. Labella, Observational trees as models for concurrency, Math. Structures. Comput. Sci. 9 (1999) 687 718; R. De Nicola, D. Gorla, A. Labella, Tree-Functors, determinacy and bisimulations, Technical Report, 02/2006, Dip. di Informatica, Univ. di Roma ``La Sapienza'' (Italy), 2008 (submitted for publication), http://www.dsi.uniroma1.it/%7Egorla/papers/DGL-TR0206.pdf]. Hence, we adapt the notion of ``Conduché condition'' [F. Conduché, Au sujet de l'existence d'adjoints à droîte aux foncteurs image reciproque dans la catégorie des catégories, C. R. Acad. Sci. Paris 275 (1972) A891 894] to the context of enriched category theory. This notion, weaker than the original ``Moebius condition'' used by Lawvere, seems to be more suitable for the description of the concurrency models parametrised w.r.t. a base category via the mechanism of change of base, actually. The base category is a monoidal 2-category; a category of generalised trees, Tree, is obtained from it. We consider Conduché Tree-based categories, where enrichment reflects factorisation of objects in the base category. We prove that a form of Conduché's theorem holds for Conduché Tree-functors.We also show how the Conduch é condition plays a crucial role in modelling concurrent processes and bisimulations between them. The notions of ``state preservation'' and ``determinacy'' [R. Milner, Communication and Concurrency, Prentice Hall International, 1989] are formally characterised.File | Dimensione | Formato | |
---|---|---|---|
conduche jpaa.pdf
accesso aperto
Tipologia:
Publisher's version/PDF
Dimensione
1.14 MB
Formato
Adobe PDF
|
1.14 MB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.