The existence and the construction of a specification morphism between two algebraic specifications is a crucial step in modular system design and in the reusability of software. The problem of determining the existence of a signature morphism between two algebraic signatures is analyzed and proved to be NP-complete by reducing the well known 3SAT problem. As a consequence, the problem of finding a specification morphism is at least as hard as that of verifying its existence.

On the complexity of specification morphisms

CICERONE, SERAFINO;
1997-01-01

Abstract

The existence and the construction of a specification morphism between two algebraic specifications is a crucial step in modular system design and in the reusability of software. The problem of determining the existence of a signature morphism between two algebraic signatures is analyzed and proved to be NP-complete by reducing the well known 3SAT problem. As a consequence, the problem of finding a specification morphism is at least as hard as that of verifying its existence.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/6812
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact