Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2545
Authors: Heljanko, Keijo
Stefanescu, Alin
Title: Complexity results for checking distributed implementability
Issue Date: 2004
metadata.ubs.publikation.typ: Arbeitspapier
Series/Report no.: Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;2004,5
URI: http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-22272
http://elib.uni-stuttgart.de/handle/11682/2562
http://dx.doi.org/10.18419/opus-2545
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

Files in This Item:
File Description SizeFormat 
TR_2004_05.pdf324,92 kBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.