Observational Equivalences for Timed Stable Event Structures

Issue title: SPECIAL ISSUE ON CONCURRENCY SPECIFICATION AND PROGRAMMING (CS&P 2005) Ruciane-Nide, Poland, 28–30 September 2005

Article type: Research Article

Authors: Andreeva, Maria V. | Virbitskaite, Irina B.

Affiliations: A.P. Ershov Institute of Informatics Systems Siberian Division of the Russian Academy of Sciences 6, Acad. Lavrentiev avenue 630090, Novosibirsk, Russia. E-mails: maria_and1@yahoo.com; virb@iis.nsk.su

Abstract: The intention of the paper is to develop a framework for weak observational equivalences in the setting of a real-time partial order model. In particular, we introduce a family of equivalences of linear time – branching time spectrum based on interleaving, causal tree and partial order semantics, in the setting of a dense time extension of stable event structures with internal actions. We study the relationships between the equivalences showing, on one hand, the discriminating power of the approaches of the spectrum and, on the other hand, the coincidence of some semantics in a concrete approach. Furthermore, when dealing with particular subclasses of the model under consideration, there is no difference between more concrete and more abstract observations.

Keywords: Real-Time Systems, Comparative Concurrency Semantics, Observational Equivalences, Timed Event Structures

Journal: Fundamenta Informaticae, vol. 72, no. 1-3, pp. 1-19, 2006