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.
Type de document :
Communication dans un congrès
Giuseppe F. Italiano and Giovanni Pighizzini and Donald Sannella. MFCS, Aug 2015, Milan, Italy. Springer, 9234, pp.382--393, 2015, Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part 〈10.1007/978-3-662-48057-1_30〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01233482
Contributeur : Jacopo Mauro <>
Soumis le : mercredi 25 novembre 2015 - 11:48:44
Dernière modification le : samedi 27 janvier 2018 - 01:31:37
Document(s) archivé(s) le : samedi 29 avril 2017 - 00:31:49

Fichier

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

Identifiants

Collections

Citation

Jacopo Mauro, Gianluigi Zavattaro. On the Complexity of Reconfiguration in Systems with Legacy Components. Giuseppe F. Italiano and Giovanni Pighizzini and Donald Sannella. MFCS, Aug 2015, Milan, Italy. Springer, 9234, pp.382--393, 2015, Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part 〈10.1007/978-3-662-48057-1_30〉. 〈hal-01233482〉

Partager

Métriques

Consultations de la notice

117

Téléchargements de fichiers

46