Constraint networks are hyper-graphs whose nodes and hyper-edges represent variables and relations between them, respectively. The problem to assign values to variables by satisfying all constraints is NP-complete. We propose an algebraic approach to the design and transformation of constraint networks, inspired by Architectural Design Rewriting (ADR). The main idea is to exploit ADR to equip constraint networks with some hierarchical structure and represent them as terms of a suitable algebra, when possible. Constraint network transformations such as constraint propagations are then specified with efficient rewrite rules exploiting the network's structure provided by terms. The approach can be understood as (i) an extension of ADR with constraints, and (ii) an application of ADR to the design of reconfigurable constraint networks.
Constraint design rewriting
BRUNI, ROBERTO;MONTANARI, UGO GIOVANNI ERASMO
2015-01-01
Abstract
Constraint networks are hyper-graphs whose nodes and hyper-edges represent variables and relations between them, respectively. The problem to assign values to variables by satisfying all constraints is NP-complete. We propose an algebraic approach to the design and transformation of constraint networks, inspired by Architectural Design Rewriting (ADR). The main idea is to exploit ADR to equip constraint networks with some hierarchical structure and represent them as terms of a suitable algebra, when possible. Constraint network transformations such as constraint propagations are then specified with efficient rewrite rules exploiting the network's structure provided by terms. The approach can be understood as (i) an extension of ADR with constraints, and (ii) an application of ADR to the design of reconfigurable constraint networks.File | Dimensione | Formato | |
---|---|---|---|
pk65.pdf
Open Access dal 01/01/2018
Descrizione: Articolo principale
Tipologia:
Documento in Post-print
Licenza:
Creative commons
Dimensione
179.38 kB
Formato
Adobe PDF
|
179.38 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.