SEMANTICS OF TIMED CONCURRENT SYSTEMS

Article type: Research Article

Authors: Dembiński, Piotr

Affiliations: Institute of Computer Science of the Polish Academy of Sciences, ul. Ordona 21, 01-237 Warsaw, Poland, e-mail:piotrd@ipipan.waw.pl

Abstract: A truly concurrent and timeless semantics is proposed for a composition of sequential, non-deterministic processes with asynchronous communication. It is shown when this semantics differs from simple interleaving. Implementation-dependent time constraints determine a subset of all computations of the timeless semantics. This set is precisely characterized for given constraints. It is shown how the same set may be generated by a timed transition system, i.e., how to simulate time-constrained and concurrent computations by sequential, non-deterministic system. The paper includes a proof of the correctness of such simulation.

DOI: 10.3233/FI-1997-291202

Journal: Fundamenta Informaticae, vol. 29, no. 1-2, pp. 27-50, 1997