On the Complexity of Reconfiguration in Systems with Legacy Components

Jacopo Mauro 1, 2 Gianluigi Zavattaro 1, 2
1 FOCUS - Foundations of Component-based Ubiquitous Systems
CRISAM - Inria Sophia Antipolis - Méditerranée , DISI - Dipartimento di Informatica - Scienza e Ingegneria [Bologna]
Abstract : 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.
Document type :
Reports
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-01160369
Contributor : Jacopo Mauro <>
Submitted on : Friday, June 5, 2015 - 11:25:25 AM
Last modification on : Wednesday, October 10, 2018 - 10:09:16 AM
Long-term archiving on : Tuesday, April 25, 2017 - 3:19:37 AM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01160369, version 1

Collections

Citation

Jacopo Mauro, Gianluigi Zavattaro. On the Complexity of Reconfiguration in Systems with Legacy Components. [Technical Report] INRIA Sophia Antipolis. 2015. ⟨hal-01160369⟩

Share

Metrics

Record views

320

Files downloads

103