https://www.mdu.se/

mdu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • 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
Model Checking Timed Automata with Priorities using DBM Subtraction
Aalborg University, Denmark.
Mälardalen University, Department of Computer Science and Electronics. Uppsala University, Sweden.
Mälardalen University, Department of Computer Science and Electronics. Aalborg University, Denmark.
Mälardalen University, Department of Computer Science and Electronics. Uppsala University, Sweden.ORCID iD: 0000-0003-4040-3480
2006 (English)In: Lecture Notes in Computer Science, vol 4202, 2006, p. 128-142Conference paper, Published paper (Refereed)
Abstract [en]

In this paper we describe an extension of timed automata with priorities, and efficient algorithms to compute subtraction on DBMs (difference bounded matrices), needed in symbolic model-checking of timed automata with priorities. The subtraction is one of the few operations on DBMs that result in a non-convex set needing sets of DBMs for representation. Our subtraction algorithms are efficient in the sense that the number of generated DBMs is significantly reduced compared to a naive algorithm. The overhead in time is compensated by the gain from reducing the number of resulting DBMs since this number affects the performance of symbolic model-checking. The uses of the DBM subtraction operation extend beyond timed automata with priorities. It is also useful for allowing guards on transitions with urgent actions, deadlock checking, and timed games.

Place, publisher, year, edition, pages
2006. p. 128-142
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 4202
National Category
Computer Systems
Identifiers
URN: urn:nbn:se:mdh:diva-6985DOI: 10.1007/11867340_10ISBN: 978-3-540-45026-9 (print)OAI: oai:DiVA.org:mdh-6985DiVA, id: diva2:236995
Conference
4th International Conference on Formal Modelling and Analysis of Timed Systems (FORMATS'06), Paris, France, September 2006
Available from: 2009-09-25 Created: 2009-09-25 Last updated: 2015-09-15Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records

Pettersson, Paul

Search in DiVA

By author/editor
Pettersson, Paul
By organisation
Department of Computer Science and Electronics
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 173 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • 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