Boreale M., Trevisan L. On the complexity of bisimilarity for value-passing processes. In: Foundations of Software Technology and Theoretical Computer Science (Bangalore, India, 18-20 december 1995). Proceedings, pp. 294 - 308. ES. Thiagarajan (ed.). (Lecture Notes in Computer Science, vol. 1026). Springer, 1995. |

Abstract (English) |
We study the complexity of deciding bisiiuilarity between non-deterministic processes with explicit primitives for manipulating data values. In particular, we consider a language with value-passing (input/output of data) and parametric definitions of processes. We distinguish the case in which data cannot be tested and the case in which a simple equality test over data is permitted. In the first case, our main result shows that the problem is PSPACEhard We study the complexity of deciding bisimilarity between non-deterministic processes with explicit primitives for manipulating data values. In particular, we consider a language with value-passing (input/output of data) and parametric definitions of processes. We distinguish the case in which data cannot be tested and the case in which a simple equality test over data is permitted. In the first case, our main result shows that the problem is PSPACE-hard for the full calculus. In the second case, we first show that the problem is coNP-complete in the fragment with value-passing and no parametric definitions. We then define a compositional polynomial-time translation of the full calculus to the fragment with parametric definitions but no value-passing. The translation preserves bisimilarity. This fact establishes the decidability of the full calculus and the PSPACE-hardness of the fragment without value-passing. In other words, once parametric definitions and equality test are allowed, the adding of value-passing does not increase neither the expressive nor the computational power. | |

DOI: | 10.1007/3-540-60692-0_56 | |

Subject | Value-passing processes B.8.1 Performance and Reliability: Reliability,Testing andFault.Tolerance |

1) Download Document PDF |

Open access Restricted Private