uu.seUppsala universitets publikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Handling Global Conditions in Parameterized System Verification
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi.
1999 (engelsk)Inngår i: Proc. 11th Int. Conf. on Computer Aided Verification / [ed] Nicolas Halbwachs, Doron Peled, Berlin: Springer Verlag , 1999, s. 134-145Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

We consider symbolic verification for a class of parameterized systems, where a system consists of a linear array of processes, and where an action of a process may in general be guarded by both local conditions restricting the state of the process about to perform the action, and global conditions defining the context in which the action is enabled. Such actions are present, e.g., in idealized versions of mutual exclusion protocols, such as the bakery and ticket algorithms by Lamport, Burn’s protocol, Dijkstra’s algorithm, and Szymanski’s algorithm. The presence of both local and global conditions makes the parameterized versions of these protocols infeasible to analyze fully automatically, using existing model checking methods for parameterized systems. In all these methods the actions are guarded only by local conditions involving the states of a finite set of processes. We perform verification using a standard symbolic reachability algorithm enhanced by an operation to accelerate the search of the state space. The acceleration operation computes the effect of an arbitrary number of applications of an action, rather than a single application. This is crucial for convergence of the analysis e.g. when applying the algorithm to the above protocols. We illustrate the use of our method through an application to Szymanski’s algorithm.

sted, utgiver, år, opplag, sider
Berlin: Springer Verlag , 1999. s. 134-145
Serie
Lecture Notes in Computer Science, ISSN 0302-9743 ; 1633
HSV kategori
Identifikatorer
URN: urn:nbn:se:uu:diva-40386DOI: 10.1007/3-540-48683-6_14ISBN: 3540662022 (tryckt)OAI: oai:DiVA.org:uu-40386DiVA, id: diva2:68287
Konferanse
Computer aided verification : 11th international conference ; CAV '99, Trento, Italy, July 6 - 10, 1999
Tilgjengelig fra: 2008-10-17 Laget: 2008-10-17 Sist oppdatert: 2018-01-11bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekst

Personposter BETA

Abdulla, Parosh Aziz

Søk i DiVA

Av forfatter/redaktør
Abdulla, Parosh Aziz
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 809 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf