The Library
Nets with tokens which carry data
Tools
Lazic, Ranko, Newcomb, Tom, Ouaknine, Joel, Roscoe, A. W. and Worrell, James (2007) Nets with tokens which carry data. In: Kleijnen, J. and Yakovlev, A., (eds.) Petri Nets and Other Models of Concurrency – ICATPN 2007 : 28th International Conference on Applications and Theory of Petri Nets and Other Models of Concurrency, ICATPN 2007, Siedlce, Poland, June 25-29, 2007. Proceedings. Lecture Notes in Computer Science, Volume 4546 . Heidelberg : Springer Verlag, pp. 301-320. ISBN 9783540730934
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
We study data nets, a generalisation of Petri nets in which tokens carry data from linearly-ordered infinite domains and in which whole-place operations such as resets and transfers are possible. Data nets subsume several known classes of infinite-state systems, including multiset rewriting systems and polymorphic systems with arrays.
We show that coverability and termination are decidable for arbitrary data nets, and that boundedness is decidable for data nets in which whole-place operations are restricted to transfers. By providing an encoding of lossy channel systems into data nets without whole-place operations, we establish that coverability, termination and boundedness for the latter class have non-primitive recursive complexity. The main result of the paper is that, even for unordered data domains (i.e., with only the equality predicate), each of the three verification problems for data nets without whole-place operations has non-elementary complexity.
Item Type: | Book Item | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Series Name: | Lecture Notes in Computer Science | ||||
Journal or Publication Title: | Petri Nets and Other Models of Concurrency - ICATPN 2007 | ||||
Publisher: | Springer Verlag | ||||
Place of Publication: | Heidelberg | ||||
ISBN: | 9783540730934 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Petri Nets and Other Models of Concurrency – ICATPN 2007 : 28th International Conference on Applications and Theory of Petri Nets and Other Models of Concurrency, ICATPN 2007, Siedlce, Poland, June 25-29, 2007. Proceedings | ||||
Editor: | Kleijnen, J. and Yakovlev, A. | ||||
Official Date: | 2007 | ||||
Dates: |
|
||||
Volume: | Volume 4546 | ||||
Number of Pages: | 20 | ||||
Page Range: | pp. 301-320 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | 28th International Conference on Applications and Theory of Petri Nets | ||||
Type of Event: | Conference | ||||
Location of Event: | Siedlce, Poland | ||||
Date(s) of Event: | 25-29 Jun 2007 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |