uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Using Forward Reachability Analysis for Verification of Timed Petri Nets
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
2007 (English)In: Nordic Journal of Computing, ISSN 1236-6064, Vol. 14, no 1, 1-42 p.Article in journal (Refereed) Published
Abstract [en]

We consider verification of safety properties for concurrent real-timed systems modelled as timed Petri nets by performing symbolic forward reachability analysis. We introduce a formalism, called region generators, for representing sets of markings of timed Petri nets. Region generators characterize downward closed sets of regions and provide exact abstractions of sets of reachable states with respect to safety properties. We show that the standard operations needed for performing symbolic reachability analysis are computable for region generators. Since forward reachability analysis is necessarily incomplete, we introduce an acceleration technique to make the procedure terminate more often on practical examples. We have implemented a prototype for analyzing timed Petri nets and used it to verify a parameterized version of Fischer's protocol, Lynch and Shavit's mutual exclusion protocol and a producer-consumer protocol. We also used the tool to extract finite-state abstractions of these protocols.

Place, publisher, year, edition, pages
2007. Vol. 14, no 1, 1-42 p.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-10736OAI: oai:DiVA.org:uu-10736DiVA: diva2:38504
Available from: 2007-05-21 Created: 2007-05-21 Last updated: 2017-12-11Bibliographically approved

Open Access in DiVA

No full text

Authority records BETA

Abdulla, Parosh AzizNylén, Aletta

Search in DiVA

By author/editor
Abdulla, Parosh AzizNylén, Aletta
By organisation
Computer Systems
In the same journal
Nordic Journal of Computing
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 496 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf