TY - GEN
T1 - On the complexity of reconfiguration in systems with legacy components
AU - Mauro, Jacopo
AU - Zavattaro, Gianluigi
PY - 2015/1/1
Y1 - 2015/1/1
N2 - In previous works we have proved that component reconfiguration in the presence of conflicts among components is non-primitive recursive, while it becomes poly-time if there are no conflicts and under the assumption that there are no components in the initial configuration. The case with non-empty initial configurations was left as an open problem, that we close in this paper by showing that, if there are legacy components that cannot be generated from scratch, the problem turns out to be PSpace-complete.
AB - In previous works we have proved that component reconfiguration in the presence of conflicts among components is non-primitive recursive, while it becomes poly-time if there are no conflicts and under the assumption that there are no components in the initial configuration. The case with non-empty initial configurations was left as an open problem, that we close in this paper by showing that, if there are legacy components that cannot be generated from scratch, the problem turns out to be PSpace-complete.
U2 - 10.1007/978-3-662-48057-1_30
DO - 10.1007/978-3-662-48057-1_30
M3 - Article in proceedings
AN - SCOPUS:84943651414
SN - 9783662480564
T3 - Lecture Notes in Computer Science
SP - 382
EP - 393
BT - Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Proceedings
A2 - Pighizzini, Giovanni
A2 - Italiano, Giuseppe F.
A2 - Sannella, Donald T.
PB - Springer
T2 - 40th International Symposium on Mathematical Foundations of Computer Science, MFCS 2015
Y2 - 24 August 2015 through 28 August 2015
ER -