Games and logics for a noninterleaving bisimulation

Mogens Nielsen; Christian Clausen

Games and logics for a noninterleaving bisimulation

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avis › Tidsskriftartikel › Forskning › peer review

Abstract

A categorical definition of bisimulation, applicable to a wide range of models in concurrency with an accompanying notion af observations, was recently suggested by Joyal, Nielsen and Winskel. The definition is in terms of span of open maps, and it coincides with Park and Milner's strong bisimulation for the standard model of labelled transition systems with sequential observations. Here, we briefly present the general set-up, and discuss its applications. For the model of transition systems with independence and nonsequential observations, the associated notion of bisimulation was shown to be a slight strengthening of the history preserving bisimulations of Rabinovich and Trakhtenbrot. Furthermore, it turns out that this bisimulation has game theoretic and logical characterizations in the form of pleasantly simple modifications of well- known characterizations of standard strong bisimulation.

Originalsprog	Engelsk
Tidsskrift	Nordic Journal of Computing
Vol/bind	2
Nummer	2
Sider (fra-til)	221-249
ISSN	1236-6064
Status	Udgivet - 1995

Citationsformater

@article{8c2ab240f16a11dfa891000ea68e967b,

title = "Games and logics for a noninterleaving bisimulation",

abstract = "A categorical definition of bisimulation, applicable to a wide range of models in concurrency with an accompanying notion af observations, was recently suggested by Joyal, Nielsen and Winskel. The definition is in terms of span of open maps, and it coincides with Park and Milner's strong bisimulation for the standard model of labelled transition systems with sequential observations. Here, we briefly present the general set-up, and discuss its applications. For the model of transition systems with independence and nonsequential observations, the associated notion of bisimulation was shown to be a slight strengthening of the history preserving bisimulations of Rabinovich and Trakhtenbrot. Furthermore, it turns out that this bisimulation has game theoretic and logical characterizations in the form of pleasantly simple modifications of well- known characterizations of standard strong bisimulation. ",

author = "Mogens Nielsen and Christian Clausen",

year = "1995",

language = "English",

volume = "2",

pages = "221--249",

journal = "Nordic Journal of Computing",

issn = "1236-6064",

publisher = "University of Helsinki Department of Computer Science",

number = "2",

}

TY - JOUR

T1 - Games and logics for a noninterleaving bisimulation

AU - Nielsen, Mogens

AU - Clausen, Christian

PY - 1995

Y1 - 1995

N2 - A categorical definition of bisimulation, applicable to a wide range of models in concurrency with an accompanying notion af observations, was recently suggested by Joyal, Nielsen and Winskel. The definition is in terms of span of open maps, and it coincides with Park and Milner's strong bisimulation for the standard model of labelled transition systems with sequential observations. Here, we briefly present the general set-up, and discuss its applications. For the model of transition systems with independence and nonsequential observations, the associated notion of bisimulation was shown to be a slight strengthening of the history preserving bisimulations of Rabinovich and Trakhtenbrot. Furthermore, it turns out that this bisimulation has game theoretic and logical characterizations in the form of pleasantly simple modifications of well- known characterizations of standard strong bisimulation.

AB - A categorical definition of bisimulation, applicable to a wide range of models in concurrency with an accompanying notion af observations, was recently suggested by Joyal, Nielsen and Winskel. The definition is in terms of span of open maps, and it coincides with Park and Milner's strong bisimulation for the standard model of labelled transition systems with sequential observations. Here, we briefly present the general set-up, and discuss its applications. For the model of transition systems with independence and nonsequential observations, the associated notion of bisimulation was shown to be a slight strengthening of the history preserving bisimulations of Rabinovich and Trakhtenbrot. Furthermore, it turns out that this bisimulation has game theoretic and logical characterizations in the form of pleasantly simple modifications of well- known characterizations of standard strong bisimulation.

M3 - Journal article

SN - 1236-6064

VL - 2

SP - 221

EP - 249

JO - Nordic Journal of Computing

JF - Nordic Journal of Computing

IS - 2

ER -

Games and logics for a noninterleaving bisimulation

Abstract

Fingeraftryk

Citationsformater