Isaac Newton Institute for Mathematical Sciences

Semantics of Computation

1 July - 31 December 1995

Organisers: S Abramsky (Imperial College, London), G Kahn (INRIA, Sophia-Antipolis), J C Mitchell (Stanford), A M Pitts (Cambridge)

Semantics of Computation Seminar

Wednesday August 2, 11:00 am

Checking Bisimilarity for Finitary History-Dependent Systems

Prof. Ugo Montanari, University of Pisa
(joint work with Marco Pistore}

History-Dependent (HD) systems refer to names and events generated in previous steps of the computation. Agents of pi-calculus or of CCS with localities or causality are HD since they can refer to names extruded in the past or to previous events from which the present transition depends via causality or locality links. Existing algorithms for deciding HD bisimilarity of finitary systems do not produce minimal realizations (as it is the case for ordinary LTS). Minimal realizations are useful since they can replace the original agents in any model checking activity. The talk introduces HD-automata and their bisimulations. They can be used for the efficient minimization of pi agents, CCS agents with localities or causality and Petri nets.

Copyright © Isaac Newton Institute