Reachability Analysis of Multithreaded Software with Asynchronous Communication
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F05%3A00012714" target="_blank" >RIV/00216224:14330/05:00012714 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Reachability Analysis of Multithreaded Software with Asynchronous Communication
Original language description
We introduce Asynchronous Dynamic Pushdown Networks (ADPN), a new model for multithreaded programs in which pushdown systems communicate via shared memory. ADPN generalizes both CPS (concurrent pushdown systems) [QR05] and DPN (dynamic pushdown networks)[BMOT05]. We show that ADPN exhibit several advantages as a program model. Since the reachability problem for ADPN is undecidable even in the case without dynamic creation of processes, we address the bounded reachability problem [QR05], which considersonly those computation sequences where the (index of the) thread accessing the shared memory is changed at most a fixed given number of times. We provide efficient algorithms for both forward and backward reachability analysis. The algorithms are basedon automata techniques for symbolic representation of sets of configurations.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2005
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 25th International Conference
ISBN
3-540-30495-9
ISSN
—
e-ISSN
—
Number of pages
12
Pages from-to
—
Publisher name
Springer-Verlag
Place of publication
Berlin, Heidelberg
Event location
Hyderabad, India
Event date
Jan 1, 2005
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000234885800028