Bild mit Unilogo
homeicon university sucheicon search siteicon sitemap kontakticon contact impressicon legal notice
unilogo University of Stuttgart 
Institute of Formal Methods in Computer Science

SZS - Publications - Complexity results for checking distributed implementability

 

Reference:

Keijo Heljanko and Alin Stefanescu. Complexity results for checking distributed implementability. Technical Report 05/2004, Universität Stuttgart, 2004.

Abstract:

We consider the distributed implementability problem as: 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 consider the distributed system models of synchronous products of transition systems [Arn94] and asynchronous automata [Zie87]. 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 [CMT99,Mor99].

Suggested BibTeX entry:

@techreport{HS04,
    author = {Keijo Heljanko and Alin Stefanescu},
    institution = {Universit{\"a}t Stuttgart},
    number = {05/2004},
    title = {Complexity results for checking distributed implementability},
    year = {2004}
}

PDF (324 kB)
Slides