Name
Abstract | ||
|---|---|---|
We consider the distributed implementability problem: 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 work with the distributed system models of synchronous products of transition systems (Arnold, 1994) and asynchronous automata (Zielonka, 1987). 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 Castellani et al. (1999) and Morin (1999). |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1109/ACSD.2005.7 | ACSD |
Keywords | Field | DocType |
complexity bound,system model,complexity results,implementability problem,transition system isomorphism,global transition system,language equivalence,transition system ts,asynchronous automaton,transition system,synchronous product,automata theory,concurrent computing,distributed system,hardware,automata,petri nets,concurrency,distributed processing,system modeling,computer science,computability,logic programming,computational complexity,upper bound,testing,polynomials | Transition system,Automata theory,Concurrency,Upper and lower bounds,Computer science,Computability,Theoretical computer science,Isomorphism,Equivalence (measure theory),Computational complexity theory | Conference |
ISSN | ISBN | Citations |
1550-4808 | 0-7695-2363-3 | 7 |
PageRank | References | Authors |
0.47 | 16 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Keijo Heljanko | 1 | 751 | 47.90 |
| Alin Stefanescu | 2 | 209 | 17.79 |