Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2545
|Title:||Complexity results for checking distributed implementability|
|Series/Report no.:||Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;2004,5|
|Abstract:||We consider the distributed implementability problem as: Given a labelled transition system TS together with a distribution D of its actions over a set of processes, does there exist a distributed system over D such that its global transition system is equivalent' to TS? We consider the distributed system models of synchronous products of transition systems and Zielonka's asynchronous automata. 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 two problems left open in the literature. We also describe a logic programming implementation which complements the existing implementation for the synthesis of asynchronous automata initiated by the second author.|
|Appears in Collections:||05 Fakultät Informatik, Elektrotechnik und Informationstechnik|
Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.