On the Complexity of Reconfiguration in Systems with Legacy Components - Archive ouverte HAL Access content directly
Reports (Technical Report) Year : 2015

On the Complexity of Reconfiguration in Systems with Legacy Components

(1, 2) , (1, 2)
1
2

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.
Fichier principal
Vignette du fichier
main.pdf (472.96 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01160369 , version 1 (05-06-2015)

Identifiers

  • HAL Id : hal-01160369 , version 1

Cite

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

Share

Gmail Facebook Twitter LinkedIn More