Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://dx.doi.org/10.18419/opus-2545
Autor(en): | Heljanko, Keijo Stefanescu, Alin |
Titel: | Complexity results for checking distributed implementability |
Erscheinungsdatum: | 2004 |
Dokumentart: | Arbeitspapier |
Serie/Report Nr.: | 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 |
Zusammenfassung: | 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. |
Enthalten in den Sammlungen: | 05 Fakultät Informatik, Elektrotechnik und Informationstechnik |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
TR_2004_05.pdf | 324,92 kB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.