Title :
Complexity results for checking distributed implementability
Author :
K. Heljanko;A. Stefanescu
Author_Institution :
Lab. for Theor. Comput. Sci., Helsinki Univ. of Technol., Finland
fDate :
6/27/1905 12:00:00 AM
Abstract :
We consider the distributed implementability problem: Given a labeled transition system TS together with a distribution /spl Delta/ of its actions over a set of processes, does there exist a distributed system over /spl Delta/ such that its global transition system is ´equivalent´ to TS? We work with the distributed system models of synchronous products of transition systems (Arnold, 1994) and asynchronous automata (Zielonka, 1987). In this paper we provide complexity bounds for the above problem with three interpretations of ´equivalent´: as transition system isomorphism, as language equivalence, and as bisimilarity. In particular, we solve problems left open in Castellani et al. (1999) and Morin (1999).
Keywords :
"Automata","Computer science","Computational complexity","Petri nets","Laboratories","Upper bound","Testing","Polynomials","Hardware","Concurrent computing"
Conference_Titel :
Application of Concurrency to System Design, 2005. ACSD 2005. Fifth International Conference on
Print_ISBN :
0-7695-2363-3
DOI :
10.1109/ACSD.2005.7