TCS / Research / Publications / Stubborn Sets for Priority Nets
Helsinki University of Technology, 
     Laboratory for Theoretical Computer Science

Stubborn Sets for Priority Nets


Kimmo Varpaaniemi. Stubborn sets for priority nets. In Cevdet Aykanat, Tuğrul Dayar, and İbrahim Körpeoğlu, editors, Computer and Information Sciences — ISCIS 2004, 19th International Symposium, Kemer-Antalya, Turkey, October 27–29, 2004, Proceedings, volume 3280 of Lecture Notes in Computer Science, pages 574–583. Springer-Verlag, Berlin, Germany, 2004. Springer-Verlag Berlin Heidelberg 2004.


Partial order methods, such as the stubborn set method and the priority method, reduce verification effort by exploiting irrelevant orders of events. We show how the stubborn set method can be applied to priority nets. By applicability we mean that for a given priority net, the stubborn set method constructs a reduced reachability graph that sufficiently represents the full reachability graph of the priority net. This work can also be considered as a combination of the stubborn set method and the priority method, to be used in ``complete or moderated incomplete'' verification when the original models are unprioritised nets.


reachability analysis, stubborn sets, priority nets

Suggested BibTeX entry:

    author = {Kimmo Varpaaniemi},
    booktitle = {{C}omputer and Information Sciences --- {I}{S}{C}{I}{S} 2004, 19th International Symposium, {K}emer-{A}ntalya, {T}urkey, {O}ctober 27--29, 2004, Proceedings},
    editor = {Cevdet Aykanat and Tu{\u{g}}rul Dayar and {\.{I}}brahim K{\"{o}}rpeo{\u{g}}lu},
    note = { Springer-Verlag Berlin Heidelberg 2004},
    pages = {574--583},
    publisher = {Springer-Verlag, Berlin, Germany},
    series = {Lecture Notes in Computer Science},
    title = {{S}tubborn Sets for Priority Nets},
    volume = {3280},
    year = {2004},

See ...

[TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
Latest update: 19 January 2010.