Detailseite
Projekt Druckansicht

Rule-based specification, analysis and implementation of propagation algorithms for global constaints

Fachliche Zuordnung Theoretische Informatik
Förderung Förderung von 2006 bis 2011
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 18899577
 
Erstellungsjahr 2011

Zusammenfassung der Projektergebnisse

We have investigated rule-based propagation algorithms for global constraints that can be used to solve constraint satisfaction problems. These included solvers for first-order constraints, the lexicographic order constraint, as well as rules for the preflow-push algorithm necessary for the alldifferent and cardinality constraints. We have proved correctness of the implemented rules. Moreover, since the specification and correct implementation of such propagation algorithms required substantial expertise, we developed algorithms that can correctly generate the rules given the definition of the constraint. The algorithms covered constraints given by their logical definition as well as those described by automata. The automatic generation algorithms were shown to yield solvers that are correct. Furthermore, we provided new means for analyzing CHR programs by investigating similarities with Petri nets, Transaction Logic, and Term Rewriting.

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

Textvergrößerung und Kontrastanpassung