16,929 research outputs found
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
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
Uso e sviluppo di concetti categoriali nell'informatica teorica
No full textConsiderazioni sull'uso dello strumento categoriale in informatica teorica
Gli oggetti matematici come "soluzioni"
No full textSi analizza la tecnica di definire gli oggetti matematici come soluzione universale di problemi
Costruzione del monoide dei quozienti in un topos elementare
No full textSi dà una costruzione universale categoriale dei numeri razionali a partire dai naturali e si generalizza al caso di un monoide
Fixed Points in Computer Science
No full textFixed points play a fundamental role in several areas of computer science and logic by justifying induction and recursive definitions. The construction and properties of fixed points have been investigated in many different frameworks. The aim of the workshop 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 operation in the different fields and formalisms.Previous workshops where held in 1998 in Brno and in 2000 in Paris
Categories with sums and right distributive tensor product
No full textModels for parallel and concurrent processes lead quite naturally to the study of monoidal categories (Inform. Comput. 88 (2) (1990) 105). In particular a category Tree of trees, equipped with a non-symmetric tensor product, interpreted as a concatenation, seems to be very useful to represent (local) behavior of non-deterministic agents able to communicate (Enriched Categories for Local and Interaction Calculi, Lecture Notes in Computer Science, Vol. 283, Springer, Berlin, 1987, pp. 57-70). The category Tree is also provided with a coproduct (corresponding to choice between behaviors) and the tensor product is only partially distributive w.r.t. it, in order to preserve non-determinism. Such a category can be properly defined as the category of the (finite) symmetric categories on a free monoid, when this free monoid is considered as a 2-category. The monoidal structure is inherited from the concatenation in the monoid. In this paper we prove that for every alphabet A, Tree(A), the category of finite A-labeled trees is equivalent to the free category which is generated by A and enjoys the afore-mentioned properties. The related category Beh(A), corresponding to global behaviors is also proven to be equivalent to the free category which is generated by A and enjoys a smaller set of properties. (C) 2002 Elsevier Science B.V. All rights reserved
Giustificazione ingenua dell'assiomatica di F.W.Lawvere
No full textViene commentata l'assiomatizzazione della categoria delle categorie dovuta a F.W. Lawver
On a categorical and logical model of data structures
No full textSi propopone un modello logico-categoriale per le strutture di dat
- …
