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
Verification of Asynchronous Programs with Nested Locks
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
LIAFA, CNRS and University of Paris Diderot. (Modeling and Verification)
Chennai Mathematical Institute, Chennai, India.
TU Braunschweig, Germany.
2017 (engelsk)Inngår i: 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, December 11-15, 2017, Kanpur, India / [ed] Satya Lokam and R. Ramanujam, Dagstuhl, Germany, 2017, Vol. 93, s. 11:1-11:14Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

In this paper, we consider asynchronous programs consisting of multiple recursive threads running in parallel. Each of the threads is equipped with a multi-set. The threads can create tasks and post them onto the multi-sets or read a task from their own. In addition, they can synchronise through a finite set of locks. In this paper, we show that the reachability problem for such class of asynchronous programs is undecidable even under the nested locking policy. We then show that the reachability problem becomes decidable (Exp-space-complete) when the locks are not allowed to be held across tasks. Finally, we show that the problem is NP-complete when in addition to previous restrictions, threads always read tasks from the same state.

sted, utgiver, år, opplag, sider
Dagstuhl, Germany, 2017. Vol. 93, s. 11:1-11:14
Serie
Leibniz International Proceedings in Informatics (LIPIcs) ; 93
HSV kategori
Identifikatorer
URN: urn:nbn:se:uu:diva-337133OAI: oai:DiVA.org:uu-337133DiVA, id: diva2:1168358
Konferanse
37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017
Prosjekter
UPMARCTilgjengelig fra: 2017-12-20 Laget: 2017-12-20 Sist oppdatert: 2017-12-20

Open Access i DiVA

Fulltekst mangler i DiVA

Søk i DiVA

Av forfatter/redaktør
Atig, Mohamed Faouzi
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric

urn-nbn
Totalt: 124 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