PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
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


Icona documento 1) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional