323,585 research outputs found
Conduché property and Tree-based categories
No full textThis 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, T r e e, is obtained from it. We consider Conduché T r e e-based categories, where enrichment reflects factorisation of objects in the base category. We prove that a form of Conduché's theorem holds for Conduché T r e e-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. © 2009 Elsevier B.V. All rights reserved
Generalising Conduché's theorem
No full textIn a previous paper (Kasangian and Labella, J Pure Appl Algebra, 2009) we proved a form of Conduché's theorem for LSymcat-categories, where L was a meet-semilattice monoid. The original theorem was proved in Conduché (CR Acad Sci Paris 275:A891-A894, 1972) for ordinary categories. We showed also that the "lifting factorisation condition" used to prove the theorem is strictly related to the notion of state for processes whose semantics is modeled by LSymcat-categories. In this note we resume the content of Kasangian and Labella (J Pure Appl Algebra, 2009) in order to generalise the theorem to other situations, mainly arising from computer science. We will consider PSymcat-categories, where P is slightly more general than a meet-semilattice monoid, in which the lifting factorisation condition for a PSymcat-functor still implies the existence of a right adjoint to its corresponding inverse image functor. © 2009 Springer Science+Business Media B.V
Observational trees as models for concurrency
No full textGiven an automaton, its behaviour can be modelled as the sets of strings over an alphabet A that can be accepted from any of its states. When considering concurrent systems, we can see a concurrent agent as an automaton, where non-determinism derives from the fact that its states can offer a different behaviour at different moments in time. Non-deterministic computations between a pair of states can then no longer be described as a ‘set’ of strings in a free monoid. Consequently, between two states we will have a labelled structured set of computations, where the structure describes the possibility of two computations parting from each other while maintaining the same observable steps. In this paper, we shall consider different kinds of observation domains and related structured sets of computations. Structured sets of computations will be organised as a category of generalised trees built over a meet-semilattice monoid formalizing the observation domain. Theorems allowing us to introduce the usual concurrency operators in the models and relating different models will then be obtained by first considering ordinary functors (on and between the observation domains), and then lifting them to the categories of structured sets of computations
On continuous time agents
No full textContinuous time agents are studied in an enriched categorical framework that allows for a comprehensive treatment of both the interleaving and the true concurrent paradigms in parallelism. The starting point is a paper by Cardelli, where actions have a duration in a (dense) time domain. More recent works are also briefly considered and some possible directions towards timed ldquotrue concurrentrdquo processes are indicated
Theoretical Informatics and Applications April 2002 - Volume 36 - Issue 02 (Fixed Points in Computer Science (FICS'01))
No full textThe papers included in this special issue are among the more representative ones presented
at the workshop Fixed Points in Computer Science (FICS’01) which took place in
Florence on September 2001, as a satellite event of PLI’ 01. This was the third workshop
of a series the aim of which is to provide a forum for researchers to present their results
to those members of the computer science and logic communities who study or apply the
fixed point operations in the different fields and formalisms. Previous workshops where
held in 1998 in Brno and in 2000 in Paris (Special issues of these events also appeared in
this journal). The Workshop was sponsored by Dipartimento di Sistemi ed Informatica
of Universita‘di Firenze and Gruppo Nazionale per il Calcolo Scientifico of CNR.
The scientific program of the workshop consisted of 5 invited lectures given by
J. Adamek, Z. ́Esik, I. Guessarian, C. Stirling and R.F.C. Walters, as well as of 12 presentations
chosen, after formal refereeing by the program committe members.
The Program Committee was formed by: J. Adamek, R. Backhouse, S. Bloom,
R. De Nicola, Z. ́Esik, I. Guessarian, W. Kuich, A. Labella, M. Mislove, D. Niwinski.
The papers published here, have been selected among the presented ones after a careful
refereeing by external, anonymous reviewers; I take the occasion to thank them all for
the precious work. The papers of this special issue present new and significant results at
least in two areas. On one hand in the algebraic theory of fixed point operators providing
an equational theory that allows to find the minimal solution for a fixed point equation
in a continuous idempotent semiring and the characterization in the category of sets of
the class of functors that are definable by mu-terms in terms of parity games. On the
other hand, we have a sophisticated example of construction of a categorical semantics
for a language, but also a characterization of categories which provide a general setting
for semantics in computer science with particular respect to fixed point operators
The topos of continuous trees as a model for distributed calculi
No full textDefining the topos of continuous time processes and its logi
Observers, experiments, and agents: a comprehensive approach to parallelism
No full textThe aim of this paper is to introduce an enriched categorical approach which provides a unifying theory for many notions of parallelism and concurrency. Our constructions are based on a concept of observational equivalence induced by a set of observers which perform experiments over agents. The outcome of those experiments is a set of computations together with an agreement information. This comprehensive framework is parametric with respect to the nature of the observers which may observe totally or partially ordered set of actions in a discrete or continuous manner
Algorithmic and geometric thought: the example of Campanus
No full textViene ripresa la (pseudo) assiomatizzazione dei naturali dovuta a Campano da Novara per mettere in risalto l'evoluzione del pensiero algoritmico
- …
