Concurrency , Complexity , 1-safe Nets , Interaction Systems
Abstract:
Interaction systems are a formal model for component-based systems, where components are combined via connectors to form more complex systems. We compare interaction systems (IS) to the wellstudied model of 1-safe Petri nets (1SN) by giving a translation map1: 1SN → IS and a translation map2: IS → 1SN, so that a 1-safe Petri net (an interaction system) and its according interaction system (1-safe Petri net) defined by the respective mapping are isomorphic up to some label relation R. So in some sense both models share the same expressiveness. Also, the encoding map1 is polynomial and can be used to reduce the problems of reachability, deadlock and liveness in 1SN to the problems of reachability, deadlock and liveness in IS, yielding PSPACE-hardness for these questions.
Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.
![[img]](https://madoc.bib.uni-mannheim.de/style/images/fileicons/application_pdf.png)
Suche Autoren in