@techreport{
    US-FMI-HS04,
    author = "Heljanko, Keijo and Stefanescu, Alin",
    institution = "Institute of Formal Methods in Computer Science, University of Stuttgart",
    title = "Complexity Results for Checking Distributed Implementability",
    url = "http://users.ics.tkk.fi/kepa/publications/",
    abstract = "We consider the distributed implementability problem as: Given a labeled transition system TS together with a distribution $\Delta$ of its actions over a set of processes, does there exist a distributed system over $\Delta$ such that its global transitions system is `equivalent' to TS? We consider the distributed systems modeled as synchronous products of transitions systems [Arn94], respectively as asynchronous automata [Zie87]. In this paper we provide complexity bounds for the above problem with three interpretations for `equivalent' as transition system isomorphism, language equivalence, and bisimilarity. In particular, we solve problems left open in [Mor99,CMT99]. We also describe a logic programming implementation which complements the implementation for the synthesis of asynchronous automata initiated in [SEM03].",
    year = "2004",
    number = "05/2004",
    month = "October",
    juforank = "NA",
    corerank = "NA",
    flags = "SA-53695",
    address = "Stuttgart, Germany",
    keywords = "synthesis, distributed systems",
    pages = "37"
}