PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Latella D., Massink M., De Vink E. Bisimulation of labelled state-to-function transition systems coalgebraically. In: Logical Methods in Computer Science, vol. 11 (4) pp. 1 - 40. Technische Universitšt Braunschweig, Institute of Theoretical Computer Science, 2015.
 
 
Abstract
(English)
Labeled state-to-function transition systems, FuTS for short, are characterized by transitions which relate states to functions of states over general semirings, equipped with a rich set of higher-order operators. As such, FuTS constitute a convenient modeling instrument to deal with process languages and their quantitative extensions in particular. In this paper, the notion of bisimulation induced by a FuTS is addressed from a coalgebraic point of view. A correspondence result is established stating that FuTS-bisimilarity coincides with behavioural equivalence of the associated functor. As generic examples, the equivalences underlying substantial fragments of major examples of quantitative process algebras are related to the bisimilarity of specific FuTS. The examples range from a stochastic process language, PEPA, to a language for Interactive Markov Chains, IML, a (discrete) timed process language, TPC, and a language for Markov Automata, MAL. The equivalences underlying these languages are related to the bisimilarity of their specific FuTS. By the correspondence result coalgebraic justification of the equivalences of these calculi is obtained. The specific selection of languages, besides covering a large variety of process interaction models and modelling choices involving quantities, allows us to show different classes of FuTS, namely so-called simple FuTS, combined FuTS, nested FuTS, and general FuTS .
URL: http://www.lmcs-online.org/ojs/viewarticle.php?id=1902&layout=abstract
DOI: 10.2168/LMCS-11(4:16)2015
Subject Category Theory
Coalgebras
Stochastic Processes
Semantic Meta-models
H.1 MODELS AND PRINCIPLES
F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional