Constraint design rewriting

Roberto Bruni, Alberto Lluch Lafuente, Ugo Montanari

Research output: Contribution to journalJournal articleResearchpeer-review


Constraint networks are hyper-graphs whose nodes and hyper-edges respectively represent variables and relations between them. 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. © 2013 Elsevier B.V. All rights reserved.
Original languageEnglish
JournalScience of Computer Programming
Publication statusAccepted/In press - 2013
Externally publishedYes


  • Architectures
  • Constraints
  • Hierarchical graphs
  • Rewriting


Dive into the research topics of 'Constraint design rewriting'. Together they form a unique fingerprint.

Cite this