Undecidability of accordance for open systems with unbounded message queues |
| |
Authors: | Richard Müller Christian Stahl Walter Vogler |
| |
Affiliation: | 1. Institut für Informatik, Humboldt-Universität zu Berlin, Germany;2. Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, The Netherlands;3. Institut für Informatik, Universität Augsburg, Germany |
| |
Abstract: | We study asynchronously communicating open systems modeled as Petri nets with an interface. An accordance preorder describes when one open system can be safely replaced by another open system without affecting some behavioral property of the overall system. Although accordance is decidable for several behavioral properties if we assume a previously known bound on the maximal number of pending messages, we show that it is not decidable without this assumption. |
| |
Keywords: | Petri nets Open nets Accordance preorder Theory of computation |
本文献已被 ScienceDirect 等数据库收录! |