On the Complexity of Reconfiguration in Systems with Legacy Components

Jacopo Mauro 1, 2 Gianluigi Zavattaro 1, 2
2 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 reconfig-uration 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 :
Conference papers
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-01233482
Contributor : Jacopo Mauro <>
Submitted on : Wednesday, November 25, 2015 - 11:48:44 AM
Last modification on : Wednesday, October 10, 2018 - 10:08:49 AM
Long-term archiving on : Saturday, April 29, 2017 - 12:31:49 AM

File

main.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Jacopo Mauro, Gianluigi Zavattaro. On the Complexity of Reconfiguration in Systems with Legacy Components. MFCS, Aug 2015, Milan, Italy. pp.382--393, ⟨10.1007/978-3-662-48057-1_30⟩. ⟨hal-01233482⟩

Share

Metrics

Record views

139

Files downloads

68