Result Details

Verification of parametric concurrent systems with prioritised FIFO resource management

VOJNAR, T.; HABERMEHL, P.; BOUAJJANI, A. Verification of parametric concurrent systems with prioritised FIFO resource management. FORMAL METHODS IN SYSTEM DESIGN, 2008, vol. 32, no. 2, p. 129-172. ISSN: 0925-9856.
Type
journal article
Language
English
Authors
Vojnar Tomáš, prof. Ing., Ph.D., DITS (FIT)
Habermehl Peter
Bouajjani Ahmed
Abstract

We consider the problem of parametric verification over a class ofsystems of processes competing for access to sharedresources. We suppose the access to the resources to be controlledaccording to a FIFO-based policy with a possibility of distinguishinglow-priority and high-priority resource requests. We propose a model ofthe concerned systems based on extended automata with queues. Over thismodel, we address verification of properties expressed in LTL\Xenriched with global process quantification and interpreted on finiteas well as fair behaviours of the given systems. In addition, weexamine parametric verification of process deadlockability too. Byreducing the parametric verification problems to finite-state modelchecking, we establish several decidability results for differentclasses of the considered properties and systems (including the specialcase of systems with the pure FIFO resource management). Moreover, weshow that parametric verification against formulae with local processquantification is undecidable in the given context.

Keywords

formal verification, parameterized concurrent systems, cut-offs

URL
Published
2008
Pages
129–172
Journal
FORMAL METHODS IN SYSTEM DESIGN, vol. 32, no. 2, ISSN 0925-9856
BibTeX
@article{BUT48165,
  author="Tomáš {Vojnar} and Peter {Habermehl} and Ahmed {Bouajjani}",
  title="Verification of parametric concurrent systems with prioritised FIFO resource management",
  journal="FORMAL METHODS IN SYSTEM DESIGN",
  year="2008",
  volume="32",
  number="2",
  pages="129--172",
  issn="0925-9856",
  url="http://www.springerlink.com/content/f234451821483p0j/fulltext.pdf"
}
Projects
Advanced Formal Approaches in the Design and Verification of Computer-Based Systems, GACR, Standardní projekty, GA102/07/0322, start: 2007-01-01, end: 2009-12-31, completed
Security-Oriented Research in Information Technology, MŠMT, Institucionální prostředky SR ČR (např. VZ, VC), MSM0021630528, start: 2007-01-01, end: 2013-12-31, running
Research groups
Departments
Back to top