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.
Type de document :
Rapport
[Technical Report] INRIA Sophia Antipolis. 2015
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01160369
Contributeur : Jacopo Mauro <>
Soumis le : vendredi 5 juin 2015 - 11:25:25
Dernière modification le : samedi 27 janvier 2018 - 01:31:37
Document(s) archivé(s) le : mardi 25 avril 2017 - 03:19:37

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

283

Téléchargements de fichiers

75