TY - GEN
T1 - Reachability for dynamic parametric processes
AU - Muscholl, Anca
AU - Seidl, Helmut
AU - Walukiewicz, Igor
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - In a dynamic parametric process every subprocess may spawn arbitrarily many, identical child processes, that may communicate either over global variables, or over local variables that are shared with their parent. We show that reachability for dynamic parametric processes is decidable under mild assumptions. These assumptions are e.g. met if individual processes are realized by pushdown systems, or even higher-order pushdown systems. We also provide algorithms for subclasses of pushdown dynamic parametric processes, with complexity ranging between NP and DEXPTIME.
AB - In a dynamic parametric process every subprocess may spawn arbitrarily many, identical child processes, that may communicate either over global variables, or over local variables that are shared with their parent. We show that reachability for dynamic parametric processes is decidable under mild assumptions. These assumptions are e.g. met if individual processes are realized by pushdown systems, or even higher-order pushdown systems. We also provide algorithms for subclasses of pushdown dynamic parametric processes, with complexity ranging between NP and DEXPTIME.
UR - http://www.scopus.com/inward/record.url?scp=85010669564&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-52234-0_23
DO - 10.1007/978-3-319-52234-0_23
M3 - Conference contribution
AN - SCOPUS:85010669564
SN - 9783319522333
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 424
EP - 441
BT - Verification, Model Checking, and Abstract Interpretation - 18th International Conference, VMCAI 2017, Proceedings
A2 - Bouajjani, Ahmed
A2 - Monniaux, David
PB - Springer Verlag
T2 - 18th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2017
Y2 - 15 January 2017 through 17 January 2017
ER -