DocumentCode :
3619684
Title :
Complexity results for checking distributed implementability
Author :
K. Heljanko;A. Stefanescu
Author_Institution :
Lab. for Theor. Comput. Sci., Helsinki Univ. of Technol., Finland
fYear :
2005
fDate :
6/27/1905 12:00:00 AM
Firstpage :
78
Lastpage :
87
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"
Publisher :
ieee
Conference_Titel :
Application of Concurrency to System Design, 2005. ACSD 2005. Fifth International Conference on
ISSN :
1550-4808
Print_ISBN :
0-7695-2363-3
Type :
conf
DOI :
10.1109/ACSD.2005.7
Filename :
1508132
Link To Document :
بازگشت