Technischer Bericht TR-2004-05

Bibliograph.
Daten
Heljanko, Keijo; Stefanescu, Alin: Complexity results for checking distributed implementability.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Technischer Bericht Informatik Nr. 2004/05.
37 Seiten, englisch.
CR-Klassif.D.1.6 (Logic Programming)
D.2.4 (Software Engineering Software/Program Verification)
F.1.3 (Complexity Measures and Classes)
Keywordssynchronous products; asynchronous automata; logic programming; synthesis; computational complexity; concurrency
Kurzfassung

We consider the distributed implementability problem as: Given a labeled 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.

Volltext und
andere Links
PDF (332723 Bytes)
PostScript (779482 Bytes)
Kontaktstefanan@fmmi.uni-stuttgart.de
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Sichere und Zuverlässige Softwaresysteme
Eingabedatum9. November 2004
   Publ. Institut   Publ. Informatik