Complexity results for checking distributed implementability

We consider the distributed implementability problem: Given a labeled transition system TS together with a distribution ∆ of its actions over a set of processes, does there exist a distributed system over ∆ such that its global transition system is ‘equivalent ’ to TS? We work with the distributed system models of synchronous products of transition systems [1] and asynchronous automata [18]. 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 [4, 10]. 1