Interaction Systems and 1-safe Petri Nets

Preview

PDF
Interaction Systems and 1-safe Petri Nets.pdf - Published
Download (169kB)

URL:	https://ub-madoc.bib.uni-mannheim.de/1409
URN:	urn:nbn:de:bsz:180-madoc-14092
Document Type:	Working paper
Year of publication:	2007
The title of a journal, publication series:	None
Publication language:	English
Institution:	School of Business Informatics and Mathematics > Sonstige - Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik
MADOC publication series:	Veröffentlichungen der Fakultät für Mathematik und Informatik > Institut für Informatik > Technical Reports
Subject:	004 Computer science, internet
Subject headings (SWD):	Berechnungskomplexität , Nebenläufigkeit
Keywords (English):	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.

BASE: Minnameier, Christoph ; Majster-Cederbaum, Mila

Google Scholar: Minnameier, Christoph ; Majster-Cederbaum, Mila

Downloads per month over past year

You have found an error? Please let us know about your desired correction here: E-Mail

Show item