Published August 24, 2015 | Version v1
Conference paper Metadata-only

On the Complexity of Reconfiguration in Systems with Legacy Components

Mauro, Jacopo
Zavattaro, Gianluigi
Others:
Department of Computer Science and Engineering [Bologna] (DISI) ; Alma Mater Studiorum Università di Bologna [Bologna] (UNIBO)
Foundations of Component-based Ubiquitous Systems (FOCUS) ; Inria Sophia Antipolis - Méditerranée (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Dipartimento di Informatica - Scienza e Ingegneria [Bologna] (DISI) ; Alma Mater Studiorum Università di Bologna [Bologna] (UNIBO)-Alma Mater Studiorum Università di Bologna [Bologna] (UNIBO)
Giuseppe F. Italiano and Giovanni Pighizzini and Donald Sannella

Description

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.

Abstract

International audience

Additional details

Identifiers Origin repository
Created:
March 25, 2023
Modified:
November 29, 2023